Haskell

近期计划开这个系列的坑，内容大多都是“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. ...

Monad是Haskell中讨论最多的结构, 需要更详细的探讨其相关内容, 即使它对于Haskell而言不是必须的:(. 参考: All about Monads Monad Support 除了之前介绍过的一些基本函数, Haskell本身定义了一些辅助函数配合Monad一起使用: sequence 1 2 3 4 -- 任意一个fail会导致整个fail sequence :: Monad m => [m a] -> m [a] sequence = foldr mcons (return []) where mcons p q = p >>= \x -> q >>= \y -> return (x : y) sequence_和sequence类似但其不返回值, 在只关心序列的副作用时其非常有用. 1 2 sequence_ :: Monad m => [m a] -> m () sequence_ = flodr (>>) (return ()) mapM其由sequence和map定义 1 2 mapM :: Monad m => (a -> m b) -> [a] -> m [b] mapM f as = sequence $ map f as mapM_, 类似的使用sequence_定义 1 2 mapM_ :: Monad m => (a -> m b) -> [a] -> m () mapM_ f as = sequence_ $ map f as =<<是>>=调换参数位置的版本 1 2 (=<<) :: Monad m => (a -> m b) -> m a -> m b f =<< x = x >>= f 上面提到的函数都是standard prelude中定义的, Haskell在Control.Monad模块中定义了更多函数. 下面是一些列表函数的Monad版本: foldM 1 2 3 foldM :: (Monad m) => (a -> b -> m a) -> a -> [b] -> m a foldM f a [] = return a foldM f a (x:xs) = f a x >>= \y -> foldM f y xs filterM 1 2 3 4 5 filterM :: Monad m => (a -> m Bool) -> [a] -> m [a] filterM p [] = return [] filterM p (x:xs) = do b <- p x ys <- filterM p xs return (if b then (x:ys) else ys) zipWithM和zipWithM_ ...

Semigroup 半群即一个集合以及在之上定义的一个满足结合律的二元运算, 在Haskell中定义为(部分): 1 2 3 class Semigroup where (<>) :: a -> a -> a {-# MINIMAL (<>) #-} Laws 1 2 -- associativity a <> (b <> c) = (a <> b) <> c Monoid “A monoid is a binary associative operation with an identity”, 在Haskell中定义为(部分): 1 2 3 4 5 6 class Monoid m where mempty :: m mappend :: m -> m -> m mconcat :: [m] -> m mconcat = foldr mappend mempty {-# MINIMAL mempty #-} Laws 1 2 3 4 5 6 7 8 -- left identity mappend menpty x = x -- right identity mappend x mempty = x -- associativity mappend x (mappend y z) = mappend (mappend x y) z 这和数学上带幺半群所满足的性质是一致的, 带幺半群即一个包含单位元的半群. ...