又一个 Haskell 教程/类型基础/解答

简单类型

1. String 或 [Char]
2. 类型错误：列表是同质的
3. Num{a} => (a, Char)
4. Int
5. 类型错误：无法添加不同类型的值

多态类型

这些类型

1. (a,b) -> b
2. [a] -> a
3. [a] -> Bool
4. [a] -> a
5. [[a]] -> a

函数类型

函数参数

这些类型

1. a -> [a]。此函数接收一个元素并返回只包含该元素的列表。
2. a -> b -> b -> (a,[b])。第二个和第三个参数必须是相同类型，因为它们进入同一个列表。第一个元素可以是任何类型。
3. (Num a) => a -> a。由于我们将 (+) 应用于 a，它必须是 Num 的实例。
4. a -> String 或 a -> [Char]。这会忽略第一个参数，因此它可以是任何类型。
5. (Char -> a) -> a。在此表达式中，x 必须是一个函数，它接收 Char 作为参数。然而，我们不知道它会产生什么，所以我们称之为 a。
6. 类型错误。在这里，我们假设 x 的类型是 a。但是 x 应用于自身，所以它必须是 b -> c 类型。但然后它必须是 (b -> c) -> c 类型，然后它必须是 ((b -> c) -> c) -> c 类型，等等，导致无限类型。
7. (Num a) => a -> a。同样，由于我们将 (+) 应用于 a，它必须是 Num 的实例。

数据类型

对

定义类似于

data Triple a b c = Triple a b c

tripleFst (Triple x y z) = x
tripleSnd (Triple x y z) = y
tripleThr (Triple x y z) = z

带有类型签名的代码为

data Quadruple a b = Quadruple a a b b

firstTwo :: Quadruple a b -> [a]
firstTwo (Quadruple x y z t) = [x,y]

lastTwo :: Quadruple a b -> [b]
lastTwo (Quadruple x y z t) = [z,t]

我们注意到这里只有两个类型变量，a 和 b 与 Quadruple 相关联。

多个构造函数

代码

data Tuple a b c d = One a
                     | Two a b
                     | Three a b c
                     | Four a b c d

tuple1 (One   a      ) = Just a
tuple1 (Two   a b    ) = Just a
tuple1 (Three a b c  ) = Just a
tuple1 (Four  a b c d) = Just a

tuple2 (One   a      ) = Nothing
tuple2 (Two   a b    ) = Just b
tuple2 (Three a b c  ) = Just b
tuple2 (Four  a b c d) = Just b

tuple3 (One   a      ) = Nothing
tuple3 (Two   a b    ) = Nothing
tuple3 (Three a b c  ) = Just c
tuple3 (Four  a b c d) = Just c

tuple4 (One   a      ) = Nothing
tuple4 (Two   a b    ) = Nothing
tuple4 (Three a b c  ) = Nothing
tuple4 (Four  a b c d) = Just d

代码

fromTuple :: Tuple a b c d -> Either (Either a (a,b)) (Either (a,b,c) (a,b,c,d))
fromTuple (One   a      ) = Left  (Left  a        )
fromTuple (Two   a b    ) = Left  (Right (a,b)    )
fromTuple (Three a b c  ) = Right (Left  (a,b,c)  )
fromTuple (Four  a b c d) = Right (Right (a,b,c,d))

在这里，我们使用嵌套的 Either 来表示有四个（而不是两个）选项。

递归数据类型

代码

listHead (Cons x xs) = x
listTail (Cons x xs) = xs

listFoldl f y Nil = y
listFoldl f y (Cons x xs) = listFoldl f (f y x) xs

listFoldr f y Nil = y
listFoldr f y (Cons x xs) = f x (listFoldr f y xs)

二叉树

代码

elements (Leaf x) = [x]
elements (Branch lhs x rhs) =
  elements lhs ++ [x] ++ elements rhs

代码

treeFoldr :: (a -> b -> b) -> b -> BinaryTree a -> b
treeFoldr f i (Leaf x) = f x i
treeFoldr f i (Branch left x right) = treeFoldr f (f x (treeFoldr f i right)) left

elements2 = treeFoldr (:) []

或

elements2 tree = treeFoldr (\a b -> a:b) [] tree

第一个 elements2 只是第二个的更紧凑版本。

代码

treeFoldl :: (a -> b -> a) -> a -> BinaryTree b -> a
treeFoldl f i (Leaf x) = f i x
treeFoldl f i (Branch left x right) = treeFoldl f (f (treeFoldl f i left) x) right

elements3 t = treeFoldl (\i a -> i ++ [a]) [] t

延续传递风格

它既不完全模仿。它的行为最接近 foldr，但在初始值的处理上略有不同。我们可以在解释器中观察差异

示例

CPS> foldr (-) 0 [1,2,3]
2
CPS> foldl (-) 0 [1,2,3]
-6
CPS> fold  (-) 0 [1,2,3]
-2

很明显，它的行为不同。通过写下 fold 和 foldr 的推导，我们可以确切地看到它们在何处不同

     foldr (-) 0 [1,2,3]
==>  1 - foldr (-) 0 [2,3]
==>  ...
==>  1 - (2 - (3 - foldr (-) 0 []))
==>  1 - (2 - (3 - 0))
==>  2

     fold  (-) 0 [1,2,3]
==>  fold' (-) (\y -> 0 - y) [1,2,3]
==>  0 - fold' (-) (\y -> 1 - y) [2,3]
==>  0 - (1 - fold' (-) (\y -> 2 - y) [3])
==>  0 - (1 - (2 - 3))
==>  -2

本质上，主要的区别在于，在 foldr 的情况下，"初始值"在最后使用（替换 []），而在 CPS 的情况下，初始值在开头使用。

CPS 中的 map 函数

map' :: (a -> [b] -> [b]) -> [a] -> [b]
map' f [] = []
map' f (x:xs) = f x  (map' f xs)

map2 :: (a -> b) -> [a] -> [b]
map2 f l = map' (\x y -> f x : y) l

点消除

map2 f = map' (\x y -> (:) (f x) y)
map2 f = map' (\x -> (:) (f x))
map2 f = map' (\x -> ((:) . f) x)
map2 f = map' ((:) . f)

CPS 中的 filter 函数：（需要仔细检查）

filter' :: (a -> [b] -> [b]) -> [a] -> [b]
filter' f [] = []
filter' f (x:xs) = f x  (filter' f xs)

filter2 :: (a -> Bool) -> [a] -> [a]
filter2 f l = filter' (\x y -> if (f x) then x:y else y) l