一些 haskell 的列表操作的实现

最近专注毕设，太久没写新东西了，该整点活了。

最近又开始去了解 haskell，之前学这语言觉得语法和之前学的差距太大因此弃坑（也或许是看得太快了），现在回过头来才发现，还挺有趣的。haskell 很有魔力，和之前学的语言又有很大差别，感觉又太过学术性……学起来确实是挺难的。

还是根据之前看的《Haskell 趣学指南》来学。这篇文章实现一下 haskell 的几个已有的函数。

replicate, repeat

replicate 接受一个整数 n 和一个元素，返回包含 n 个该元素的列表。

显然当 n 为 0 的时候返回空列表，这里约定 n 小于 0 的时候也返回空列表，明显地，这里已经获得递归的基线条件了。

1
2
3
4
replicate' :: (Ord t, Num t) => t -> a -> [a]
replicate' n elem
    | n <= 0 = []
    | otherwise = elem : replicate' (n - 1) elem

repeat 生成某元素的无限列表（牛逼啊……），实现非常容易。

1
2
repeat' :: a -> [a]
repeat' elem = elem:repeat' elem

take, reverse, elem

take 函数从列表中取出前 n 个元素。约定 n 小于等于 0 时取得空列表，列表为空的时候取得空列表。

1
2
3
4
5
take' :: (Ord t, Num t) => t -> [a] -> [a]
take' n _ 
    | n <= 0 = []
take' _ [] = []
take' n (x:xs) = x : take' (n - 1) xs

一个非常鬼畜的地方是，像take 3 []这样的函数调用时会报错的，haskell 抱怨到，它不知道这个列表里的元素究竟是什么类型（即使这是一个空列表！）。同理，[]在任何地方直接使用（不使用++和：，否则 haskell 能推断出类型，也不指定类型，如[] :: [Integer]，这是不会报错的）都会报这个错误，而且那错误提示还挺晦涩，挺迷惑人的。

elem 检测元素是否在列表中。遍历一遍，每次查头部即可，和 lisp 版的一样。

1
2
3
4
5
6
7
elem' :: Eq t => t -> [t] -> Bool
elem' a [] = False
elem' a (x:xs) = a == x || elem' a xs

-- 简化版
elem' :: Eq t => t -> [t] -> Bool
elem' a = foldr (\ x -> (||) (a == x)) False

reverse 的实现就不用多说了 8。

1
2
3
4
5
6
7
8
9
reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]

-- 使用折叠和 flip 的更加酷炫的实现
reverse' :: [a] -> [a]
reverse' [] = []
reverse' xs = 
    foldl (flip (:)) [] xs

zip, zipWith

zip 将两列表中对应位置元素一一组成元组列表，其长度为两列表中较小的一个。zipWith 方法接受一个函数和两个列表，将两列表中对应元素一一应用到函数并返回结果的列表。写起来其实和 zip 一样。

1
2
3
4
5
6
7
8
9
zip' :: [a] -> [b] -> [(a, b)]
zip' [] _ = []
zip' _ [] = []
zip' (x:xs) (y:ys) = (x,y):zip' xs ys

zipWith' :: (t1 -> t2 -> a) -> [t1] -> [t2] -> [a]
zipWith' _ [] _ = []
zipWith' _ _ [] = []
zipWith' f (x:xs) (y:ys) = f x y:zipWith' f xs ys

感叹，haskell 写起这个来比其他语言优雅多了。

fold, map, filter

折叠操作：一个列表生成一个值。

折叠操作能用来编写 map 和 filter，毕竟列表也是值嘛。就这方面来说，可以认为折叠操作是对列表的最广泛的操作：以源列表为输入，输出一个值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
foldl' :: (t1 -> t2 -> t1) -> t1 -> [t2] -> t1
foldl' _ a [] = a
foldl' f a (x:xs) = foldl' f (f a x) xs

foldl1' :: (p -> p -> p) -> [p] -> p
foldl1' _ [] = error "empty list"
foldl1' f (x:xs) = foldl' f x xs

map' :: (t -> a) -> [t] -> [a]
map' _ [] = []
map' f xs =
    foldl' (\ x y -> x ++ [f y]) [] xs

filter' :: (a -> Bool) -> [a] -> [a]
filter' _ [] = []
filter' f xs =
    foldl' (\ x y -> x ++ [y | f y]) [] xs

-- 不利用各种语法糖的写法
filter' :: (a -> Bool) -> [a] -> [a]
filter' _ [] = []
filter' fn (x:xs) = 
    if fn x then x : last else last
    where last = filter' fn xs

就写这些。haskell 虽然漂亮且优雅（以后要写伪代码的时候干脆就写 haskell 吧！），但是着实有点得劲。我还是先去学学 scala 吧……