Things I Learned

近期计划开这个系列的坑，内容大多都是“Purely Functional Data Structures”内容加一点自己的理解（改一张牌就是我的了:），算是打磨文笔？ 数据结构是什么 当我们在讨论数据结构的时候，我们在讨论什么。常见的介绍有“数据结构是一种数据组织、管理和存储的格式，它可以帮助我们实现对数据高效的访问和修改，更准确地说， 数据结构是数据值的集合，可以体现数据值之间的关系，以及可以对数据进行应用的函数或操作”。然而到更具体的场景，数据结构的概念还能够细化，比如我们经常会 讨论函数栈怎么怎么样，这里的“函数栈”也是数据结构，但它是一个泛指，是一个在程序执行过程中存在的概念，或者叫标识。Okasaki在他的“Purely Functional Data Structures”里指出，数据结构这一概念通常有四种含义： 抽象，即抽象数据类型(abstract data type，可以用Java中的interface理解)，即表示数据的类型和一组适用于该类型的函数； 实现，即对应于ADT的一个具体实现，通常是指对于该ADT做的具体设计； 实例，即在程序运行中对应于一个数据类型的具体实例； 泛指，即在程序运行中一个泛指的概念，不涉及具体的实例，例如上文提到的函数栈。 本系列将使用Haskell作为描述语言，则其中class可对应抽象的概念，data可对应实现的概念。具体到Java，可以用interface对应抽象的概念，用class对应实现 的概念。 函数式强调的是什么 抛开函数式编程本身强调的函数以外（不然就没法讲了），函数式编程通常还强调不可变（immutable）。因此，当我们说一个数据结构符合函数式的特性的时候主要在讨论不可变， 或者说持久性（persistence）。换句话说，在更新一个函数式的数据结构之后，它更新前的版本我们仍然能够访问到。这意味着所有有着破坏式更新的数据结构都不符合这一性质， 同时也表明相较于能够进行破坏式更新的数据结构，函数式数据结构的性能可能会更差，通常会有一个对数阶的更新代价在里面。实现持久性的方式非常简单，只需要将原有的数据结构 复制一遍，然后在复制后的数据结构上更新，由于没有破坏式的更，可以通过共享不变的部分来减少开销。下面讨论在函数式编程中经典的list。 List list在任何编程语言中都是非常常见的存在，函数式编程对其讨论则更多，著名的Lisp就取自“LISt Processor”。我们首先来看广泛的list定义 1 2 3 4 5 6 7 class List t where empty :: t a isEmpty :: t a -> Bool cons :: a -> t a -> t a -- error if the list is empty. head :: t a -> a tail :: t a -> t a 这里可以考虑将head和tail的结果包装一个Maybe，使之适合空的list，在这种情况下isEmpty就不再需要，因为head ls = Nothing或 tail ls = Nothing已经暗含isEmpty ls = true。本文为了偷懒就没用这种定义）。有了这些，我们就可以实现list上的各种“更高级的” 操作，例如经典的map： 1 2 3 4 map :: List t => (a -> b) -> t a -> t b map f ls = if isEmpty ls then emptll else cons (f $ head ls) (map f $ tail ls) 从这个定义上可以直接看出，这个List是不支持随机访问的。因此，我们额外定义支持“按下标”随机访问的class： ...

Memoization是动态规划(Dynamic Programming)中自顶向下处理问题采用的策略, 其基本想法是通过将子问题的解保存起来避免重复计算来优化算法. 这个概念本身很简单, 在其他有明显mutable语义的语言中, 实现起来也非常简单. 但是在Haskell中问题就变的复杂了不少, 对于一个原始的函数f :: a -> b你如果要用ref, 比如说IORef, 你必须要把它放到IO monad中, 你的memoize函数就变成了... -> IO (a -> b). 我们希望是能够找到一个memoize :: ... -> (a -> b), 这样memoize之后得到的和原函数类型是一致的. 为了讨论的方便, 我们主要关注两个例子的memoization, 一个是经典的Fibonacci数列: 1 2 3 4 fib :: Int -> Integer fib 0 = 0 fib 1 = 1 fib n = fib (n - 2) + fib (n - 1) 另一个则是动态规划(自底向上)中典型的最小编辑距离的问题, 所谓的最小编辑距离就是一个字符串通过增加, 删除, 替换的操作得到另一个字符串所需要的操作次数: 1 2 3 4 5 6 minEditDist :: String -> String -> Int minEditDist [] [] = 0 minEditDist s [] = length s minEditDist [] s = length s minEditDist (x:xs) (y:ys) | x == y = minEditDist xs ys | otherwise = 1 + minimum [minEditDist xs ys, minEditDist xs (y:ys), minEditDist (x:xs) ys] Memoizing with specific problem 首先来看fib的问题, wiki给出了一个非常elegant的解(就fib本身而言, 还有更经典的解, fib = (fibs !!) where fibs = 0 : 1 : zipWith (+) fibs (tail fibs)): ...

Pearl 2: 给定一个长度大于1的列表, 计算其元素的最大surpasser count, 要求算法复杂度 $O(n log n)$. Type: msc: Ord a => [a] -> Int “Pearls of functional algorithm design"的第二章, 我们先来看surpasser的定义 Definition surpasser: 称列表中$X[j]$是$X[i]$的surpasser, 如果$X[i] < X[j]$且$i < j$. 因此一个元素的surpasser count就是其surpasser的数目. 同样, 一个naive的实现很容易: 1 2 3 4 msc :: Ord a => [a] -> Int msc xs = maximum [scount z zs | z:zs <- tails xs] scount :: Ord a => a -> [a] -> Int scount x xs = length $ filter (> x) xs 同时也很容易看到, 这个实现的时间复杂度是 $O(n^2)$, 不符合要求的 $O(n log n)$. 为了达到 $O(n log n)$ 的时间复杂度, 我们希望有个函数f能够递归的处理xs = us ++ vs, 并且存在一个线性复杂度的函数join, 使得f xs = join (f us) (f vs), 这样整体的复杂度满足 $T(n)=2 T(n/2)+O(n)=O(n log n)$. 原文中, 作者利用分治的思想通过一步步地推导获得了线性时间的join, 这里也仅仅是类似于复读的"再解释”. ...

Pearl 1: 给定一个自然数的有限集X, 计算不属于X的最小自然数. X表示为不包含重复元素的无序列表. 时间复杂度要求$O(n)$. Type: minfree :: [Int] -> Int(也可以额外的定义自然数类型, 不过这不是我们的重点) “Pearls of Functional Algorithm Design"的第一章, 其描述了一个分治的算法和一个基于array的算法, 这里按个人的思路讲解一下基于分治的算法, 基于array的算法具体可以查阅原文. 首先拿到这个问题, 我觉得最直接的想法就是 Base Solution: minfree xs = head $ [0..] \\ xs 然而这和要求的线性时间复杂度不符. 第二个想法就是设计一个fold的函数遍历一遍列表, 这样时间复杂度符合要求. 但是越来越多的边界条件让我意识到思路不对. 看了原文才发现忽略了解题的一个重要条件. Fact: [0..n]中的所有自然数不可能都在X(xs)中, 其中n = length xs. 这也很容易证明, 因为$ n + 1 = length\ [0..n] > n $, 因此不属于集合X的最小自然数就是[0..n]中不属于X的最小自然数. 至此,该问题很容易解决, 只需要一个marked的array来表示[0,,n]中的自然数是否在X中即可. 下面描述基于分治的算法, 首先给出一个基本的结论. Theorem: (as ++ bs) \\ (us ++ vs) == (as \\ us) ++ (bs \\ vs), 如果as \\ vs == as && bs \\ us == bs. ...

之前在"Essentials of Programming Languages"中学习过CPS(Continuation Passing Style), 而笔记在blog改版后被丢弃, 故在这篇文章中重新详细的探讨下CPS以及尾递归, 就当是温故而知新. Continuation 在理解什么是"Continuation Passing Style"之前, 我们首先需要定义Continuation(惭愧的是我都不知道中文叫啥, 查了下好像是"续延"). Continuation是计算机程序控制状态的抽象表示, 换言之, 其就是一种表示程序执行中间某一计算步骤的控制上下文的数据结构, 即表示某一计算的未来. 一个形象的例子是阶乘函数: 1 2 3 4 let rec fact n = if n = 0 then 1 else n * (fact (n - 1)) 当我们计算(fact 4)时, 其执行过程为(用lisp的形式是因为更加形象): 1 2 3 4 5 6 7 8 9 10 (fact 4) => (* 4 (fact 3)) => (* 4 (* 3 (fact 2))) => (* 4 (* 3 (* 2 (fact 1)))) => (* 4 (* 3 (* 2 (* 1 (fact 0))))) => (* 4 (* 3 (* 2 (* 1 1)))) => (* 4 (* 3 (* 2 1))) => (* 4 (* 3 2)) => (* 4 6) => 24 这过程中, (* 4 #)就是一个continuation, 是(fact 3)的控制上下文, 等待着(fact 3)的计算结果传入我们的"#", (* 4 (* 3 #))也是一个continuation. 容易看到的是在这样一个计算过程中, continuation在不断增长, 因为调用栈在不断增长, 程序不得不保存*的左操作数, 计算右操作数. 接下来, 我们来看fact的尾递归版本, 所谓的尾递归(tail recursion)指的是递归函数的递归调用部分只有函数调用, 即: ...

近来想于函数式编程中寻找类似与双向链表的数据结构, 结果找到了Zipper. Zipper中文为拉链, 泛指一类常在函数式编程中使用的聚合数据结构, 其加强了原有的数据结构, 使得能够遍历或更新原有数据结构的任意部分. zipper的关键思想是将目前需要处理的部分和不需要处理的部分分开, 同时保存目前不需要的部分, 也可以将其形象的理解为光标. 本文首先介绍了如何在list的基础上构建zipper, 随后将其扩展到二叉树上. list的例子 定义zipper list或者说是单向链表, 是函数式编程中最负盛名的结构, 其既简单又实用. 当我们需要修改list中的一部分时, 例如将[1 2 3 4 5]中的[3 4 5]替换为[5 6], list就带来了问题. 这时候一个简单的做法是: 1 2 3 4 5 6 let rec changeTailOfList l1 idx l2 = match l1 with | [] -> l2 // 忽略了idx大于0的情况 | x::xs -> if idx = 0 then l2 else x :: (changeTailOfList xs (idx - 1) l2) changeTailOfList [1; 2; 3; 4; 5] 2 [5; 6] // [1; 2; 5; 6] 看起来好像挺不错, 而这时候如果我们想要修改刚刚添加的内容, 例如在上面的例子中, 我们把5替换为[7 8], 这时候同样可以采取和changeTailOfList一样的做法, 从头开始遍历列表, 在目标位置进行更改. 显而易见, 在需要频繁修改某一部分的场合下, list是不适用的(虽然list本身就不是为了频繁修改某一部分而设计的). 然而, 这种需求是确实存在的, 在可变的条件下, 我们很容易想到双向链表, 设定一个指针指向我们当前操作的位置便可以方便的进行前向或后向修改. 那我们要如何在不可变的条件下满足这一需求呢? zipper正是为了解决这一类问题. 首先我们来定义list上的zipper: 1 2 3 type 'a ListZipper = ListZipper of 'a list * 'a list let zipper l1 = ListZipper (l1, []) 对于list而言, 我们需要处理的部分总是位于某个子列表的头部, 而需要保存的部分则是目标位置前面的部分, 因此我们可以用俩个列表, 一个表示目前正在处理的部分, 另一个表示之前的部分. ...

Bitwise tricks 近来翻到一本"Hackers Delight"的书, 其主要介绍基于二进制运算的算法. 初读来大感震撼, 其结果之巧妙,过程之精简, 于仅仅是了解计算机数是用补码所表示, 并未深入了解过二进制运算的人而言不可谓不精美. 正如Dijkstra所言, 计算机程序是集逻辑美感与机械实现的矛盾体. 本文姑且将其中的一些皮毛摘录如下, 以便日后之使用, 目前倒是难以得到应用. 使最右位的1变成0 1 2 3 // 01011000 -> 01010000 // if no one then return 0 x & (x - 1) 上式也可以用来判断一个无符号的整数是否是$ 2^n $的形式. 使最右位的0变成1 1 2 3 // 10100111 -> 10101111 // if no zero then return -1 x | (x + 1) 使尾部的1变成0 1 2 3 // 10100111 -> 10100000 // if no trailing 1s then identity x & (x + 1) 上式也可以用来判断一个无符号的整数是否是$ 2^n - 1 $的形式. ...

Value Restriction是什么？ Value restriction是用于控制类型推断能否对值声明进行多态泛化的规则（MLton原文：“The value restriction is a rule that governs when type inference is allowed to polymorphically generalize a value declaration.”）。常出现在ML系的语言中，如SML，OCaml，F#中，其实value restriction产生的本质原因是为了保证类型系统在结合参数多态与命令式特性（imperative feature，如ref）时候的可靠性（soundness）。一个典型的例子就是： 1 2 3 4 5 6 // 如果没有value restriction let x = ref None // 'a option ref let y: int option ref = x // type checked let z: string option ref = x // type checked let () = y := Some 2 // type checked let v: string = !z // 破坏了类型安全 限制了什么？ 简单来讲，value restriction限制了类型泛化只能发生在表达式的右边是句法意义上的值。那么什么是句法意义上的值呢，SML的语言规范上明确给出了什么样的表达式是句法意义上的值（准确来说是non-expansive）: 常量，如13，"string" 变量，如x,y 函数，如fn x => e 除了ref以外的构造函数在值上的调用，如Foo v 类型上受约束的值，如v: t 每一个元素都是值的tuple, 如(v1, v2, v3) 每一个字段都是值的record, 如{l1 = v1, l2 = v2} 每一个元素都是值的list, 如[v1, v2, v3] 确切的来讲，只要是协变（covariant）的类型并且不和可变的特性相结合，那么它总是可以类型安全的泛化（OCaml manual原文：“As a corollary, covariant variables will never denote mutable locations and can be safely generalized.”）。即： ...