Haskell笔记

总论

Haskell是一种函数式语言，其运行的过程就是给函数传递参数，然后进行执行。

这里的函数指的是数学上的函数，如

下面是这个函数对应的haskell代码：

sqr x = x * x

在GHCi环境中，我们将这行代码输入，即完成了该函数的定义。然后我们输入

sqr 5

即可获得25。

haskell的最大的优点在于简洁，易读，如以下为一段C++代码：

int ans=0;
for(int i=1;i<=n;i++)
    ans=ans+i;

而用haskell实现就极为简洁易懂：

sum [] = 0
sum (x:xs) = x + sum xs

再如以下为haskell实现的快排：

qsort [] = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger
               where
               smaller = [y|y<-xs,y<x]
               larger = [y|y<-xs,y>=x]

基础语法

变量和函数

作为函数式语言，haskell中的函数是一等公民(first class citizen)，在任何地方都能够定义函数，并将函数作为一个参数和返回值。

作为函数式语言，haskell中的变量一经赋值即不能改变。

用于条件判断的语法

if&else

haskell中if和else必须同时出现。if后要加then。

abs :: (Num a) => a -> a
abs x = if x > 0 then x
        else -x

pattern matching

通过写出一个函数在不同情况下的值来定义一个函数。

sum :: (Num a) => [a] -> a
sum [] = 0
sum (x:xs) = x + sum xs

fact :: (Integeral a) => a -> a
fact 0 = 1
fact n = n * fact (n - 1)

guards

类似于switch。

sgn :: (Num a) => a -> Int
sgn x | x > 0     = 1
      | x < 0     = -1
      | otherwise = 0

case_of

就是switch。

sum ys = case ys of
         []     -> 0
         (x:xs) -> x + sum xs

let_in & where

有时，我们需要一些临时变量和函数，这时就要用let_in和where。

merge_sort :: (Ord a) => [a] -> [a]
merge_sort [x] = [x]
merge_sort xs = merge (merge_sort l) (merge_sort r) -- 假装有merge
    where
        (l,r) = splitAt (length xs `div` 2) xs

merge_sort [x] = [x]
merge_sort xs = let (l,r) = splitAt (length xs `div` 2) xs in
                merge (merge_sort l) (merge_sort r)

Haskell 类型

在Haskell中，每个表达式，自变量，函数都有自己的类型。Haskell语言中用::表示类型，如：

True :: Bool
not False :: Bool
not :: Bool -> Bool

基本数据类型

Int 表示整数，范围与long long同。

Integer 表示的整数无取值范围。

Int & Integer 统称为 Integral

Float 单精度浮点型

Double 双精度浮点型

Float & Double 统称为Floating

Char 表示字符

Bool 用于判断

类型类

可以理解为一个类型的集合。在一个类型类（类族）中的类型都必须支持某一个或某些函数。

Eq 所有能判断相等的类型

Ord 所有有序的类型

Show 所有能输出的类型

Read 所有能输入的类型

Num 所有数字

Integral 所有整数

Floating 所有浮点数

定义类型和类族

最简单的定义是type定义，作用类似于typedef。最典型的例子：

type String = [Char]

如果要定义新的数据类型，要用到data，如：

data Bool = True | False

这表示Bool类型是由True和False两种情况构成的。True和False称为constructor，类似于函数，这两个constructor都是没有参数的，下面是两个有参数的例子：

data Maybe a = Nothing | Just a
data Tree a  = Leaf a | Node (Leaf a) (Leaf a) a

其中，Tree a的定义中运用了它本身，即为递归数据类型。而type定义时不能构造递归数据类型。

data的功能强大，但是会影响效率，而type功能一般，但效率较好，于是有一个折中的解决方案：newtype。

newtype使用时与前两者相似，不同点在于，编译时其被视为data，而运行时其与type较为接近，这样既保留了data的一部分功能，又兼有type的效率。

定义类族：

定义类族时只要定义一些所有类型都要满足的函数即可，如：

class Myclass a where
    foo1 :: a -> a
    foo2 :: a -> [a]
    ...

如果要使一种数据类型被包含在该类族中，则要给出这些函数的实现，如：

instance Myclass Int where
    foo1 = ...
    foo2 = ...
    ...

类族中的类型也可以是一些含参数的类型，如：

class Myclass f where
    foo1 :: f a -> f b
    foo2 :: Num a => f a -> b
    ...
    
instance Myclass Maybe where
    foo1 = ...
    foo2 = ...
    ...

定义类族时，可以限定该类族中的类型必须属于某一个类族：

class Myclass1 a => Myclass2 b where
    ...
    
class (Myclass1 a, Myclass3 f) => Myclass4 f a where
    ...

此外，定义的类型可以自动加载某些类族，如：

data Tree a = Leaf a | Node (Tree a) (Tree a) a
    deriving (Show,Eq)

这样，Tree a类型就属于Show和Eq类族了。

列表和元组

List为列表，写做[a]，如，[1,1,2,3,5]、[1..100]类型都是[Int]，['a','b','c']类型是[Char]/这个也写作"abc"/，[True,True,False]类型是[Bool]。一个列表内的元素类型必须相同。

列表还可以嵌套，如[[1,1,2,3,5],[],[1..100]]类型就是[[Int]]。这里列表中的元素类型是[Int]，而[]类型为[a]，其中的a可以是任何元素，因此这里的写法是没有问题的。

同时，两个列表可以进行连接，如['a','b'] ++ ['c','d','e'] => ['a','b','c','d','e']。

还可以将一个元素加到列表的开头，如a:[b,c,...] => [a,b,c,...]

其实列表定义就是a:b:c:...:[]，即列表的构造方式。

haskell中的列表是一个链表，每一个元素都会记三个东西：构造方法（这里是：）、值或值的指针、下一个元素的地址。

haskell中的另一个特色就是list comprehension。考虑集合的记法：\(\{x|x\in A,f(x) = True\}\)，其中f(x)是一个Bool型的函数，这个记法可以自然地扩展到列表上：[x | x <- A, f x]

例如：

[x | x <- [1..], even x]
[x | x <- [1..], odd  x]
-- 分别构造了偶数和奇数列表
[x | x <- [1..n], n `mod` x == 0]
-- n的所有因子
primes = filterPrime [2..]
    where filterPrime (p:xs) =
        p : filterPrime [x | x <- xs, x `mod` p /=0]
-- O(n^2)的素数筛法

实际上，list comprehension是一个syntax sugar，实际上可以转化为一个do表达式，而这个do表达式实际上是list Monad的一个syntax sugar，其存在的意义并不是引入新的东西，而是让程序更加简洁，提高易读性。

Tuple为元组，写作(a,b,..)，如，(1,2)类型是(Int,Int)，而(True,'a')类型是(Bool,Char)。这里元组中的元素类型可以是不一样的，元组中的元素可以是元组和列表，同样，列表中的元素也可以是元组。

函数类型

Haskell中，函数也被认为是一个值，这个值也有自己的类型，比如下面函数的类型：

sqrt :: Floating -> Floating  --接受一个Floating，返回一个Floating
length :: [a] -> Int          --接受一个List，返回一个Int
take :: Int -> [a] -> [a]     --接受一个Int和一个List，返回和前面的List类型相同的List

注意最后一个函数可以理解为接受一个Int，返回一个[a]->[a]的函数。这里函数作为返回值返回。

比如我们可以这样定义：take3 = take 3，这样，take3就是一个[a]->[a]的函数。

与其他的值一样，函数也可以放在列表和元组中，放在列表中的函数类型也必须相同，如。

[tail,take 3,drop 5]     --正确，列表中的元素类型都是[a]->[a]
[head,sum,reverse]       --错误，head、sum类型是[a]->Int，而reverse类型是[a]->[a]

如果一个函数有两个参数，那么就能将其看做一个运算符，例如：

div x y     --这是函数
x `div` y   --这是运算符

同样，运算符也能转化为函数，如

a + b       --这是运算符
(+) a b     --这是函数

高阶函数

高阶函数是指以函数为参数或以函数为返回值的函数，如函数map f xs表示将f作用于序列xs的各个元素上；又如下面的函数:

fix :: ((a,b) -> c) -> a -> b -> c
fix f x y = f (x,y)

new_fst = fix fst

可以将一个作用于Tuple上的函数变成一个作用于两个变量上的函数，而fix f返回的是一个函数。

有两个重要的高阶函数：foldr , foldl。

要求一个序列之和，可以这样：

sum :: (Num a) => [a] -> a
sum [] = 0
sum (x:xs) = x + sum xs

这样就得到了一个sum函数，我们可以用foldr进行改写：

sum = foldr (+) 0

foldl与foldr恰好相反，foldr为右结合，foldl为左结合。使用foldl可以达到与for loop类似的效果。

foldl和foldr作用的对象必须属于Foldable类。

foldl :: (Foldable t) => (a -> b -> a) -> a -> t b -> a
foldr :: (Foldable t) => (a -> b -> b) -> b -> t a -> b
-- 下面是foldl和foldr作用到list上的实例

-- foldl :: (Foldable t) => (a -> b -> a) -> a -> [b] -> a
foldl f v [] = v
foldl f v (x:xs) = foldl f (f v x) xs

-- foldr :: (Foldable t) => (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)

其他

有理数，即分数，由两个Integral组成，叫做Ratio Integer，表示法如

使用时要import Data.Ratio

重要内置函数

head x             --取序列x的第一个元素                
tail x             --去除x中第一个元素并返回剩余序列        
take x y           --取序列y的前x项                        
drop x y           --去除序列y的前x项并返回剩余序列        
(!!) x y           --取序列x中的第y个元素        
length x           --返回序列x的长度                
sum x              --返回序列x中所有元素之和                  
product x          --返回序列x中所有元素之积
reverse x          --翻转序列
(++) x y           --将x,y两个序列连接成一个
fst (x,y)          --返回x
snd (x,y)          --返回y
zip x y            --将两个序列x,y转为Tuple的序列
concat x           --将一个序列的序列中的元素合并为一个序列
map f x            --对序列x中的每一个元素应用函数f，返回结果序列
filter f x         --取出序列x中使f为True的元素组成序列

fromIntegral  x    --Integral x -> Floating x
float2Double x     --Float x -> Double x
double2Float x     --Double x -> Float x
ceilint x          --下取整 Integral -> Floating
floor x            --上取整
round x            --四舍五入
truncate x         --去掉小数部分

(/=) x y           --不等于，==、>、>=、<、<=均不变
(^) x y            --x^y，+、-、*均不变。注意这里x和y是整数，实数时写作x**y
div x y            --x/y，这里的xy均为整数，直接写x/y时x、y必须是实数
mod x y            --x%y

-- import Data.Char
chr x              --将数字转为字符
ord x              --将字符转为数字
isAscii x          --判断一个字符是否是ASCII字符
isAlpha x          --判断一个字符是否是字母
isLatin x          --判断一个字符是否属于Latin1
isLower x          --判断一个字符是否是小写字母
isUpper x          --判断一个字符是否是大写字母
isDigit x          --判断一个字符是否是数字
isOctDigit x       --判断一个字符是否是八进制数字
isHexDigit x       --判断一个字符是否是十六进制数字
isAlphaNum x       --isAlpha || isDigit
isControl x        --判断一个字符是否是'\n'、'\t'等
isSpace x          --判断一个字符是否是空白字符
isPrint x          --判断一个字符能否打印
toUpper x          --小写转大写
toLower x          --大写转小写
intToDigit x       --一位数字转为一个字符
digitToInt x       --一个字符转为一位数字

Functor , Applicative , Monad

Functor

考虑要用映射，那么对于序列有：

map (+1) [1,3,4] = [2,4,5]

现在我们考虑扩展其范围，不仅限于map，于是就有了Functor:

class Functor f where
    fmap :: (a -> b) -> f a -> f b
	
instance Functor [] where
    fmap = map

data Tree a = Leaf a | Node (Tree a) (Tree a)

instance Functor Tree where
    -- fmap :: (a -> b) -> Tree a -> Tree b
    fmap f t = case t of
               Leaf x -> Leaf (f x)
               Node l r -> Node (fmap f l) (fmap f r)
               
data Maybe a = Nothing | Just a

instance Functor Maybe where
    -- fmap (a -> b) -> Maybe a -> Maybe b
    fmap f Nothing = Nothing
    fmap f (Just x) = Just (f x)
			   
-- Functor Laws: 
-- fmap id x = x
-- fmap (f.g) = fmap f . fmap g
-- notes:
-- f <$> x = fmap f x

Applicative

Applicative是Functor的扩展，用于处理一些要映射多个函数或者映射后仍为函数的情况。

考虑有下面这些函数：

fmap0 :: a -> f a
fmap1 :: (a -> b) -> f a -> f b
fmap2 :: (a -> b -> c) -> f a -> f b -> f c
fmap3 :: (a -> b -> c -> d) -> f a -> f b -> f c

要这样一个一个定义会非常麻烦，那么我们引入了Applicative:

class (Functor f) => Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

那么上面原来的四个函数就能写成：

fmap0 = pure
fmap1 f a = pure f <*> a
fmap2 f a b = pure f <*> a <*> b
fmap3 f a b c = pure f <*> a <*> b <*> c

下面是几个Example:

instance Applicative [] where
    pure x = [x]
    fs <*> xs = [f x | f <- fs , x <- xs]
	
instance Applicative Tree where
    -- pure :: a -> Tree a
    pure x = Leaf x
	
    -- (<*>) :: Tree (a -> b) -> Tree a -> Tree b
    ft <*> xt = case ft of
                Leaf f -> fmap f xt
                Node l r -> Node (l <*> xt) (r <*> xt)
                
instance Applicative Maybe where
    -- pure :: a -> Maybe a
    pure x = Just a
    
    -- (<*>) :: Maybe (a -> b) -> Maybe a -> Maybe b
    fm <*> xm = case fm of
                Nothing -> Nothing
                (Just f) -> fmap f xm

-- Applicative Laws:
-- pure id <*> x = x
-- pure g <*> pure x = pure (g x)
-- x <*> pure y = pure (\g -> g y) <*> x
-- x <*> (y <*> z) = (pure (.) <*> x <*> y) <*> z

Monad

Monad是Applicative的加强版。

Functor解决的是一个将pure的函数作用到一个effective的数据上，并得到一个effective的结果，而Applicative是将Functor进行了一般化。

如果函数本身就是由pure到一个effective的函数，那么就要用Monad：

class Monad m where
    return :: a -> m a
    (>>=) :: m a -> (a -> m b) -> mb
    (>>) :: m a -> m b -> m b
    x >> y = x >>= \_ -> y
    fail :: String -> m a
    fail msg = error msg

instance Monad [] where
    return = pure
    xs >>= f = concat (fmap f xs)
    
instance Monad Tree where
    -- return :: a -> Tree a
    return = pure
    
    -- (>>=) :: Tree a -> (a -> Tree b) -> Tree b
    xs >>= f = case xs of
               Leaf x = f x
               Node l r = Node (l >>= f) (r >>= f)

instance Monad Maybe where
    -- return :: a -> Maybe a
    return = pure
    
    -- (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
    xm >>= f = case xm of
               Nothing -> Nothing
               Just x -> f x

-- Monad Laws:
-- return x >>= f = f x
-- mx >>= return = mx
-- (mx >>= f) >>= g = mx >>= (\x -> (f x >>= g))

运用Monad，haskell构建了一个pure的函数和effective的函数的桥梁，使两者能够在一定的限制下进行交换数据。

另外，有了Monad，就可以用do结构。实际上，do结构就是一个Monad的语法糖。

m1 >>= \x1 ->
m2 >>= \x2 ->
.
.
.
mn >>= \xn ->
f x1 x2 ... xn

do
    x1 <- m1
    x2 <- m2
    .
    .
    .
    xn <- mn
    f x1 x2 ... xn

有了Monad，我们还可以使用一些能够作用于所有的Monad上的Generic Function：

-- import Control.Monad
fmapM :: (Monad m) => (a -> m b) -> [a] -> m [b]
fmapM f [] = return []
fmapM f (x:xs) = do
    y <- f x
    ys <- fmapM f xs
    return (y:ys)
    
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)
    
join :: (Monad m) m (m a) -> m a
join xss = do
    xs <- xss
    x <- xs
    return x

Alternative

可以进行选择，在Control.Applicative中定义：

class Applicative f => Alternative f where
    empty :: f a
    (<|>) :: f a -> f a -> f a
    -- 3 laws:
    -- x <|> empty = x
    -- empty <|> x = x
    -- x <|> (y <|> z) = (x <|> y) <|> z
    some  :: f a -> f [a]
    some x = pure (:) <*> x <*> many x
    many  :: f a -> f [a]
    many x = some x <|> pure []
    -- 这显然是死循环。。。
    -- 至于具体为什么可以这样，下面就解释了

定义Maybe:

instance Alternative Maybe where
    empty = Nothing
    Nothing <|> x = x
    x <|> _ = x

不难想到，就像计算(||)时一样，haskell计算(<|>)时是惰性的，即如果计算出左边不是empty，那么就直接返回左边，不必再计算右边。这样就能解释前面的some和many了。

some表示至少要有一个x，而many则表示不一定有多少个x。但是在对x进行作用时，可能对x的值进行了改变，这显然是违背了函数式语言的原则，但是有时有的情况使得我们不得不如此，也正因此，haskell引入了Applicative和Monad，来将这一类的变量和纯的函数式分隔开，只能通过个别的函数从这一类函数中读入或输出。

下面是一个例子，也是一类极为重要的Monad。

State Monad

定义某个数据类型为State。

定义State Transformer为从一个State到另一个State的函数，简记为ST。

定义ST a = State -> (a, State)。

type State = Int
newtype ST a = S (State -> (a, State))

app :: ST a -> State -> (a,State)
app (S st) x = st x 

instance到Functor,Applicative,Monad上。

instance Functor ST where
    -- fmap :: (a -> b) -> ST a -> ST b
    fmap f st = S (\s -> let (x, s') = app st s in (f x, s'))
    
instance Applicative ST where
    -- pure :: a -> ST a
    pure x = S (\s -> (x, s))
    
    -- (<*>) :: ST (a -> b) -> ST a -> ST b
    stf <*> stx = S (\s -> let (f, s') = app stf s
                               (x, s'') = app stx s' in
                               (f x, s''))
                               
instance Monoad ST where
    -- return :: a -> ST a
    return = pure
    
    -- (>>=) :: ST a -> (a -> ST b) -> ST b
    stx >>= f = S(\s -> let (x, s') = app stx s in app (f x) s')

这样，我们就完成了所有基本的定义。

而我们知道，haskell中的IO类型为IO a :: World -> (a world)，就是一个ST Monad。

下面是另一个例子：

对树进行重新标注，即在树中遍历，第一个遇到的叶子标为一号，第二个标为二号……

我们可以很容易地写出如下程序：

data Tree a = Leaf a | Node (Tree a) (Tree a)
    deriving Show
    
relabel :: Tree a -> Int -> (Tree Int, Int)
relabel (Leaf x) n = (Leaf n, n + 1)
relabel (Node l r) n = (Node ll rr, n3)
    where
        (ll, n2) = relable l n
        (rr, n3) = relable r n2

而我们注意到，relabel的类型就是Tree a -> ST (Tree Int)，所以我们可以用ST Monad进行改写：

fresh :: ST Int
fresh = (\x -> (x, x + 1))

alabel :: Tree a -> ST (Tree Int)
alabel (Leaf x) = pure Leaf <*> fresh
alabel (Node l r) = pure Node <*> alabel l <*> alabel r

relabel :: Tree a -> Tree Int
relabel t = fst (app (alabel t) 0)

上面的用到了Applicative，而我们还能用Monad：

alabel :: Tree a -> ST (Tree Int)
alabel (Leaf x) = do
    n <- fresh
    return (Leaf n)
alabel (Node l r) = do
    ll <- alabel l
    rr <- alabel r
    return (Node ll rr)

（是不是越来越像命令式语言了\xyx）

例子2： Monadic Parser

Parser即为句法分析器，用于编译过程中将各个部分分离出来。我们可以用ST Monad实现一个Parse：

newtype Parser a = P (String -> [(a, String)])

返回值用List是为了体现出不合法的情况（返回值为空）。

parse :: Parser a -> String -> [(a,String)]
parse (P p) inp = p inp

item :: Parser Char
item = P (\inp -> case inp of
                  [] -> []
                  (ch:cs) -> [(ch,cs)])

item为从一个字符串中取出第一个字符的Parser。

下面定义Functor,Applicative,Monad：

instance Functor Parser where
    -- fmap :: (a -> b) -> Parser a -> Parser b
    fmap f pa = P (\inp -> case parse pa inp in
                           [] -> []
                           [(x, inp')] -> [(f x, inp')])
                           
instance Applicative Parser where
    -- pure :: a -> Parser a
    pure x = P (\inp -> [(x, inp)])
    
    -- (<*>) :: Parser (a -> b) -> Parser a -> Parser b
    pf <*> pa = P (\inp -> case parse pf inp in
                           [] -> []
                           [(f, inp')] -> parse (fmap f pa) inp')
            
instance Monad Parser where
    -- return :: a -> Parser a
    return = pure
    
    -- (>>=) :: Parser a -> (a -> Parser b) -> Parser b
    pa >>= f = P (\inp -> case parse pa inp of
                          [] -> []
                          [(x, inp')] -> parse (f x) inp')

为了让Parser能发挥更大的功能，我们将它搞到Alternative上：

instance Alternative Parser where
    -- empty :: Parser a
    empty = return []
    
    -- (<|>) :: Parser a -> Parser a -> Parser a
    p <|> q = P (\inp -> case parse p inp in
                         [] -> parse q inp
                         [(x, inp')] -> [(x, inp')])

定义一个函数，判断一个字符串的首个字符是否符合一定条件：

sat :: (Char -> Bool) -> Parser Char
sat p = do
    ch <- item
    if p ch then
        return ch
    else
        empty
        
digit = sat isDigit
lower = sat isLower
upper = sat isUpper
alpha = sat isAlpha
alphanum = sat isAlphaNum
char x = sat (== x)

string :: String -> Parser String
string [] = empty
string (x:xs) = do
    char x
    string xs
    return (x:xs)
-- parse (string "abc") "abcdef" = [("abc","def")]
-- parse (string "abc") "abdef"  = []

space :: Parser ()
space = do
    many (sat isSpace)
    return ()
    
nat :: Parser Int
nat = do
    xs <- some digit
    return (read xs)

ident :: Parser String
ident = do
    x <- lower
    xs <- many alphanum
    return (x:xs)
    
int :: Parser Int
int = do
    char '-'
    n <- nat
    return (-n)
  <|> nat
  
token :: Parser a -> Parser a
token p = do
    space
    x <- p
    space
    return x
    
identifier = token ident
natural = token nat
integer = token int
symbol xs = token (string xs)

nats :: Parser [Int]
nats = do
    symbol "["
    x <- natural
    xs <- many (do symbol ","; natural)
    symbol "]"
    return (x:xs)

应用：表达式求值

简化问题：只有加，乘，括号的表达式进行求值：

expr -> term ("+" expr | empty)
term -> factor ("*" term | empty)

用前面定义过的东西可以这样写：

expr :: Parser Int
expr = do
    t <- term
    do
        symbol "+"
        e <- expr
        return (t + e)
      <|> return t
      
term :: Parser Int
term = do
    f <- factor
    do
        symbol "*"
        t <- term
        return (f * t)
      <|> return f
      
factor :: Parser Int
factor = do
    symbol "("
    e <- expr
    symbol ")"
    return e
  <|> integer
 
eval :: String -> Int
eval str = (fst . head) (parse expr str)

Monoid,Foldable,Traversal

Monoid（幺半群）

即有幺元（单位元）的半群。

半群是最简单的代数结构，由集合S和定义在集合S上满足结合律的一个二元运算组成。如果在一种数据上进行的一种运算满足结合律，且有单位元，那么我们可以将该数据和运算instance到Monoid上。

下面是Monoid的定义：

class Monoid a where
    mempty :: a -- 单位元
    mappend :: a -> a -> a -- 二元运算
    
    mconcat :: [a] -> a
    mconcat = foldr mappend mempty

List Monoid:

instance Monoid [a] where
    mempty = []
    mappend = (++)

Maybe Monoid:（一种实现）

instance (Monoid a) => Monoid Maybe a where
    mempty = Nothing
    Nothing `mappend` x = x
    x `mappend` Nothing = x
    (Just x) `mappend` (Just y) = Just (x `append` y)

另一种实现：

instance (Monoid a) => Monoid Maybe a where
    mempty = Just mempty
    Nothing `mappend` x = Nothing
    x `mappend` Nothing = Nothing
    (Just x) `mappend` (Just y) = Just (x `append` y)

可见，一种数据上定义的Monoid的并不是唯一的，满足条件的运算不同，定义出的Monoid也就不同。如果我们想同时定义多种Monoid，可以这样定义：

newtype Sum a = Sum a

instance (Num a) => Monoid (Sum a) where
    mempty = 0
    mappend = (+)

newtype Product a = Product a

intance (Num a) => Monoid (Product a) where
    mempty = 1
    mappend = (*)

`mappend`这种写法太麻烦了，于是可以写成<>，这两者是完全等价的。

notes:

实际上上面的Monoid的定义在现在的标准中是不对的，现在的标准中，Monoid的定义如下：

class Semigroup a => Monoid a where
    mempty :: a
    mappend :: a -> a -> a
    mappend = (<>)
    mconcat :: [a] -> a
    mconcat = foldr mappend empty

其中Semigroup意为半群，而(<>)则是半群上的运算符。

Foldable

前面提到过，foldl和foldr都是定义在Foldable上的，而Foldable的定义也和Monoid有关。

我们已经实现了Monoid，那么考虑如何将一个结构上的所有的数据通过mappend来连接起来，于是就有了fold：

class Foldable t where
    fold :: Monoid a => t a -> a
    foldMap :: Monoid b => (a -> b) -> t a -> b
    foldl :: (a -> b -> a) -> a -> t b -> a
    foldr :: (a -> b -> b) -> b -> t a -> b

List的定义显然：

instance Foldable [] where
    fold [] = mempty
    fold (x:xs) = x `mappend` fold xs
    
    foldMap _ [] =mempty
    foldMap f (x:xs) = f x `mappend` foldMap f xs
    
    foldr _ v [] = v
    foldr f v (x:xs) = f x (foldr f v xs)
    
    foldl _ v [] = v
    foldl f v (x:xs) = foldl f (f v x) xs

我们还能定义一个树：

data Tree a = Leaf a | Node (Tree a) (Tree a)

instance Foldable Tree where
    fold (Leaf x) = x
    fold (Node l r) = fold l `mappend` fold r
    
    foldMap f (Leaf x) = f x
    foldMap f (Node l r) = foldMap f l `mappend` foldMap f r
    
    foldl f v (Leaf x) = f v x
    foldl f v (Node l r) = foldl f (foldl f v l) r
    
    foldr f v (Leaf x) = f x v
    foldr f v (Node l r) = foldr f (foldr f v r) l

此外，Foldable上同样也有一些Generic Function：

null    :: t a -> Bool
length  :: t a -> Int
elem    :: Eq a => a -> t a -> Bool
maximum :: Ord a => t a -> a
minimum :: Ord a => t a -> a
sum     :: Num a => t a -> a
product :: Num a => t a -> a
foldr1  :: (a -> a -> a) -> t a -> a
foldl1  :: (a -> a -> a) -> t a -> a
toList  :: t a -> [a]

这些都可以用foldr来定义，甚至foldMap, fold, foldl也可以由foldr定义：

foldMap f = foldr (\x y -> f x `mappend` y) mempty
fold = foldr mappend mempty
foldl f v x = foldr (\x r -> (\v -> r (f v x))) id x v
toList = foldr (:) []

notes:

预加载的库中的Foldable没有fold函数，如要定义并使用该函数，需import Data.Foldable

Traversals

利用map和fmap，我们完成了将一个结构中的数据整体进行转换，而这种转换时使用的函数是pure的。如果我们需要一个effectful的转换，例如下例：

traverse :: (a -> Maybe b) -> [a] -> Maybe [b]
traverse g [] = pure []
traverse g (x:xs) = pure (:) <*> g x <*> traverse g xs

dec :: Int -> Maybe Int
dec 0 = Nothing
dec n = Just (n-1)

traverse dec [1,3,4] = Just [0,2,3]
traverse dec [2,1,0] = Nothing

那么我们定义一个class：

class (Functor t, Foldable t) => Traversable t where
    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

将List定义到这个class中：

instance Traversable [] where
    -- traverse :: Applicative f => (a -> f b) -> [a] -> f [b]
    traverse f [] = pure []
    traverse f (x:xs) = pure (:) <*> f x <*> traverse f xs

Tree:

instance Traversable Tree where
    -- traverse :: Applicative f => (a -> f b) -> Tree a -> f (Tree b)
    traverse f (Leaf x) = pure Leaf <*> f x
    traverse f (Node l r) = pure Node <*> traverse f l <*> traverse f r

另外，Traversable类中还有其他的函数：

sequenceA :: Applicative f => t (f a) -> f (t a)
sequenceA = traverse id

-- example : sequenceA [Just 1,Just 2] = Just [1,2]
--           sequenceA [Just 1,Nothing] = Nothing
-- traverse f = sequenceA . fmap g

mapM :: Monad m => (a -> m b) -> t a -> m (t b)
mapM = traverse
sequence :: Monad m => t (m a) -> m (t a)
sequence = sequenceA
-- 所有的Monad都是Applicative