Haskell 函数式编程复习

以下几张表涵盖了一些 Haskell 中的一些常用函数；除末行 ord/chr 外均来自 Prelude。列表相关函数使用列表特化签名，省去 Foldable/Traversable 泛化；String = [Char]。之后还有一些平时做作业时零零散散记下来的踩过的坑。

列表：查询、切分、组合

函数	类型签名	用途 / 记忆
`elem`	`Eq a => a -> [a] -> Bool`	成员判断：`elem x xs`
`zip`	`[a] -> [b] -> [(a,b)]`	对应位置配对；到较短列表结束
`splitAt`	`Int -> [a] -> ([a],[a])`	一次得到前 n 个与其余部分
`take / drop`	`Int -> [a] -> [a]`	取 / 丢前 n 个；n≤0 时取空 / 不丢
`takeWhile / dropWhile`	`(a -> Bool) -> [a] -> [a]`	取 / 丢满足条件的连续前缀
`map`	`(a -> b) -> [a] -> [b]`	每个元素做变换
`filter`	`(a -> Bool) -> [a] -> [a]`	保留所有满足条件的元素
`concat`	`[[a]] -> [a]`	展平一层；`concat [[1,2],[3]] = [1,2,3]`
`all / any`	`(a -> Bool) -> [a] -> Bool`	全部 / 至少一个满足；空列表为 True / False
`replicate`	`Int -> a -> [a]`	重复 n 次；`replicate 3 'a' = "aaa"`
`iterate`	`(a -> a) -> a -> [a]`	无限 `[x,f x,f(f x),…]`，通常配合 take
`reverse`	`[a] -> [a]`	逆序
`sum / product`	`Num a => [a] -> a`	求和 / 求积；空列表结果为 0 / 1
`minimum / maximum`	`Ord a => [a] -> a`	最小 / 最大元素；要求非空

函数组合与折叠

函数	类型签名	用途 / 记忆
`flip`	`(a -> b -> c) -> b -> a -> c`	交换前两个参数：`flip f x y = f y x`
`(.)`	`(b -> c) -> (a -> b) -> a -> c`	`f . g`：先 g 后 f
`($)`	`(a -> b) -> a -> b`	`f $ x` 等于 `f x`；最低优先级、右结合
`curry`	`((a,b) -> c) -> a -> b -> c`	把元组参数拆成两个参数
`uncurry`	`(a -> b -> c) -> (a,b) -> c`	把两个参数合成元组；`map (uncurry (+))`
`const`	`a -> b -> a`	保留第一参数，忽略第二参数
`foldr`	`(a -> b -> b) -> b -> [a] -> b`	`foldr f z [x,y] = f x (f y z)`
`foldl`	`(b -> a -> b) -> b -> [a] -> b`	`foldl f z [x,y] = f (f z x) y`

计算的组合：Maybe、列表、IO、Parser

函数	类型签名	用途 / 记忆
`fmap / (<$>)`	`Functor f => (a -> b) -> f a -> f b`	将纯函数用于上下文中的结果
`pure`	`Applicative f => a -> f a`	包装纯值；Maybe 为 Just，列表为单元素列表
`(<*>)`	`Applicative f => f (a -> b) -> f a -> f b`	`g <$> x <*> y`：提升二参数函数
`(>>=)`	`Monad m => m a -> (a -> m b) -> m b`	取前一步结果，决定下一步计算
`sequence`	`Monad m => [m a] -> m [a]`	组合计算并收集结果；`[IO a] -> IO [a]`
`sequenceA`	`Applicative f => [f a] -> f [a]`	同类操作，但只要求 Applicative

sequence [Just 1,Just 2] = Just [1,2]；出现 Nothing 则失败。列表实例枚举组合：sequence [[1,2],[3,4]] = [[1,3],[1,4],[2,3],[2,4]]。

转换

函数	类型签名	用途 / 记忆
`fromIntegral`	`(Integral a, Num b) => a -> b`	整数转目标数值类型；整数长度参与小数除法
`read / show`	`Read a => String -> a` / `Show a => a -> String`	文字↔值；read 需确定目标类型，格式错误会异常
`ord / chr`	`Char -> Int` / `Int -> Char`	字符↔码点；例外：需 `import Data.Char (ord,chr)`

高频组合：zip xs [0..] 编号；zip xs (drop 1 xs) 相邻对；concat . map f 映射后展平；sum . map (uncurry (*)) $ zip xs ys 点积。

fold 模板：sum = foldr (+) 0；concat = foldr (++) []；reverse = foldl (flip (:)) []；length = foldr (\_ n -> n+1) 0。

别混淆：takeWhile 遇到第一个不满足就停，filter 会继续筛选；foldl 不是严格折叠；return 不会提前退出（作用同 pure，但要求 Monad）；(-1) 是负数，减一用 \x -> x-1。

注意模式匹配

以下错：empty 不会作为匹配第一个参数是否为“empty”，而被当成被绑定的变量名。同时函数是否相同无法直接比较。

  (<|>) empty q = q
  (<|>) p _ = p

以下正确。

  (<|>) p q = P $ \x -> case app p x of
    [] -> app q x
    res -> res

关于“数”类型

Num：最基础的数值运算，支持 + - *
Integral：整数类型的运算，支持 quot rem div mod
Fractional：支持除法，有典型实例 Float Double Rational(用p/q表示精确有理数) Complex Double(负数)
Floating：支持一般数学函数，有典型实例 Float Double，支持 exp、log、sqrt、**...
整数路径：Integral => Real => Num
字面量 10 是多态的，但 x :: Int x = 10 之后，x 不能参加与浮点数的运算。fromIntegral 可以将 Int 转成任意 Num，比如 Double、Rational、Integer

Type declaration

val3 :: [(Bool, Char)]
val3 = [(False, '0'), (True, '1')]

val4 :: ([Bool], [Char])
val4 = ([False, True], ['0', '1'])

second :: [a] -> a
second xs = head (tail xs)

Merge sort

-- Problem #2: merge ascending lists
merge :: Ord a => [a] -> [a] -> [a]
merge a [] = a
merge [] b = b
merge (a:as) (b:bs) | a < b  = a : merge as (b:bs)
                    | b < a  = b : merge (a:as) bs
                    | b == a = a : b : merge as bs
-- End Problem #2

-- Problem #3: merge sort
msort :: Ord a => [a] -> [a]
msort [] = []
msort [a] = [a]
msort a = merge (msort $ take ((length a) `div` 2) a) (msort $ drop ((length a) `div` 2) a)
-- End Problem #3

函数复合与函数应用

odd = not . even
(++) = flip $ foldr (:)
前者中，not接受的参数是一个值，而flip接受的第一个参数是一个函数
区分函数对象和函数值对象！
count x y = length $ filter (== x) y
count x = length . filter (== x)

takeWhile函数

ghci> takeWhile (/= ' ') "abc def"
"abc"

@

使用 @ 可以直接引用原来的数据结构，而不需要重新构造它。

dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile _ []  =  []
dropWhile p xs@(x:xs')
    | p x       =  dropWhile p xs'
    | otherwise = xs

惰性求值若干则

套路：zip + 无限iterate

type Bit = Int
-- 将 Bit 作为类型 Int 的别名

bin2int :: [Bit] -> Int
bin2int bits  =  sum [ w * b | (w, b) <- zip weights bits ]
   where weights = iterate (* 2) 1

-- iterate is defined in Prelude
iterate :: (a -> a) -> a -> [a]
iterate f x  =  x : iterate f (f x)

筛法求素数

primes = sieve [2..]
sieve (p:xs) = p : sieve [ x | x <- xs, x `mod` p /= 0 ]

Newton's square root


sqroot :: Double -> Double
sqroot n = snd $ head $ dropWhile (\(a, a') -> a - a' > 0.00001 || a - a' < -0.00001) aa's
  where aa's = (0, 1) : [ (a' , (a' + n / a') / 2) | (a, a') <- aa's ]

例子：投票程序

ghci> votes =  ["Red", "Blue", "Green", "Blue", "Blue", "Red"]

ghci> result votes
[(1,"Green"),(2,"Red"),(3,"Blue")]

ghci> winner votes
"Blue"

result :: Ord a => [a] -> [(Int, a)]
result vs  =  sort [ (count v vs, v) | v <- rmdups vs ]
-- The sort function is defined in Data.List

rmdups :: Eq a => [a] -> [a]
rmdups []  =  []
rmdups (x:xs)  =  x : filter (/= x) (rmdups xs)

count :: Eq a => a -> [a] -> Int
count x = length . filter (== x)

winner :: Ord a => [a] -> a
winner = snd . last . result

生成所有bool：活用map

bools :: Int -> [[Bool]]
bools 0 = [[]]
bools n = map (False :) bss ++ map (True :) bss
    where bss = bools $ n - 1

生成幂集

powerset :: [a] -> [[a]]
powerset []     = [[]]
powerset (x:xs) = xss ++ map (x:) xss
  where
    xss = powersetRec xs

-- 或：
import Control.Monad (filterM)

powerset :: [a] -> [[a]]
powerset = filterM (\_ -> [True, False])

-- 或：
powerset :: [a] -> [[a]]
powerset [] = [[]]
powerset (x:xs) =
  [zs | ys <- powerset xs, zs <- [ys, x:ys]]

去重函数：rmdups

rmdups (x:xs)  =  x : filter (/= x) (rmdups xs)
-- 下面这种就显得非常笨拙了
rmdups a = [ fst x | x <- zip a (iterate (+1) 0), not $ elem (fst x) (take (snd x) a)]

定义一棵树

data Tree a = Leaf a | Node (Tree a) (Tree a)
-- !! 不是 Node Tree Tree !!!!!

例子：计算将一个元素插入一个 list 中的所有可能方式：

interleave :: a -> [a] -> [[a]]
interleave x []     = [[x]]
interleave x (y:ys) = (x:y:ys) : map (y:) (interleave x ys) 

-- 注意不是：(x:y:ys) ++ y:interleave x ys。后者犯了几个错误？
-- 错误式把 [a] 与 [[a]] 混淆；应以 (:) 把一个完整列表放入结果列表，用 map (y:) 给每个递归结果加前缀。

ghci> interleave 1 [2, 3, 4]
[ [1,2,3,4], [2,1,3,4], [2,3,1,4], [2,3,4,1] ]

技巧：利用列表是否为空来表示"Maybe"

eval :: Expr -> [Int]
eval (Val n) = [n | n > 0]
eval (App o l r) =
  [apply o x y | x <- eval l, y <- eval r, valid o x y]

这里的列表不表示“一个表达式有很多计算结果”，而表示： [] ：表达式不合法 [n] ：表达式合法，结果是 n 这个设计的好处是：失败会自然传播。如果左子表达式非法，x <- eval l 就变成 x <- []。没有任何可选的 x，整个推导式自然得到 []。无需在每层写一套错误处理分支。

Foldable相关

toList = foldMap (\x -> [x])
> concat (Node (Leaf [1,2]) (Leaf [3]))
[1,2,3]

其它

函数应用优先级最高，改变顺序别忘了加括号！

定义函数时，别忘了写参数！

递归勿忘边界条件！(又惰性求值递归，边界为一开始的"0:1:"：fibs = 0 : 1 : [ x + y | (x, y) <- zip fibs (tail fibs) ])

不是 != ，是 /= ！

不是 a and b，是 a && b 或 and a b！

where 只能附加在函数定义后面（也允许带 guards 的函数，但是附加到整个定义而不是一条匹配）、case ... of 的某条分支后面、class、instance、module

不要漏写/漏看 Data Constructor！

注意 <*> 实现的过程中先解析左侧！