haskell 小记

Part1 类型与类簇

一些基础类型：Bool, Int …

注意 Int 定长 $[-2^{63},2^{63}-1]$ ，而 Integer 不定长

Word 和 Natural 都是无符号整数，但 Word 定长，Natural 不定长

List 类型: 可以看做 []:type->type，[T] 代表一些 T 的元素构成的 list

Tuple 类型：比如 (A,B,C)

注意不存在 1 元 tuple，但1存在 0 元 tuple () 。

=> 一般代表类型类约束 例如 (+) 的类型是 Num a=>a->a->a

一些基础函数：head 是取出 list 第一个元素，tail 是取出第一个元素后余下的元素，last 是取出最后一个元素

一些基础类簇：Eq,Ord,Num

比如 == 的类型是 Eq a=>a->a->Bool ，< 的类型是 Ord a=>a->a->Bool

Part2 定义函数

条件表达式

abs :: Int -> Int
abs n  =  if n >= 0 then n else -n

Guarded Equation

abs :: Int -> Int
abs n | n >=    0  =   n
      | otherwise  =  -n

模式匹配 (Pattern Matching)

(&&) :: Bool -> Bool -> Bool
True  && True  = True
_     && _     = False

序列模式 (List Pattern)

记住 (a:xs) 表示一个 list，是 a 这个元素和 xs 这个序列拼起来。(xs:a) 是不允许的

一个例子：

head :: [a] -> a
head (x:_)  =  x

元组模式 (Tuple Pattern)

fst :: (a, b) -> a
fst (x, _)  =  x

λ 表达式 (Lambda Expression)

比如

odds n = map f [0..n-1]
where
    f x = x * 2 + 1

可以写作

odds n = map (\x -> x * 2 + 1) [0..n-1]

Part3 列表推导式

类似数学中 $\{a^2|a\in [0,1]\}$ 的描述，haskell 中也有类似的方式，能从已有 list 出发构造新的 list。

注：String 是 [Char] ，所以下面的方法能直接用在 String 上

Generator

[ (x, y) | x <- [1, 2, 3], y <- [4, 5] ]

我们称 x <- [1, 2, 3] 和 y<- [4,5] 是 generator

后面的 generator 可以依赖前面的 generator，比如

[ (x, y) | x <- [1..3], y <- [x..3] ]

Guard

可以对 generator 生成的值进行过滤，比如

[ x | x <- [1..10], even x ]

Zip

Prelude 中存在一个函数 zip 类型是 [a]->[b]->[(a,b)] ，大概就是把两个序列逐位合并，比如 zip([1,2],[3,4,5])=[(1,3),(2,4)]

Part4 递归函数

fac :: Int -> Int
fac 0 = 1
fac n = n * fac (n-1)

当然，List 上也能定义递归函数

product :: Num a => [a] -> a
product []  =  1
product (n:ns)  =  n * product ns

多重递归：定义一个函数时，对函数自身进行了多次递归调用。比如求斐波那契

互递归：几个函数相互调用对方进行定义

even :: Int -> Bool
even 0 = True
even n = odd (n-1)

odd :: Int -> Bool
odd 0 = False
odd n = even (n-1)

Part5 高阶函数

指这个函数的某个参数或返回值是一个函数。

我们来看一些常见的 Prelude 中的高阶函数

map：把一个序列中的元素同时进行某种变换

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

filter：按照一个谓词筛选一些函数

filter :: (a -> Bool) -> [a] -> [a]
filter pred xs  =  [x | x <- xs, pred x]

foldr：给定一种运算和一个初始值，在序列上从右往左进行 “累加”

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

例如 sum = foldr (+) 0

另一个例子，表示拼接两个类型相同的 list：

(++) :: [a] -> [a] -> [a]
(++) xs ys = foldr (:) ys xs

(.) 表示函数复合

(.) :: (b -> c) -> (a -> b) -> a -> c
(.) f g = \x -> f $ g x

例如

odd :: Int -> Bool
odd = not . even

all 表示一个结构中的所有元素是否都满足一个谓词

all :: (a -> Bool) -> [a] -> Bool
all p xs = and [p x | x <- xs]

any 一个结构中的所有元素中是否存在至少一个满足谓词

any :: (a -> Bool) -> [a] -> Bool
any p xs = or [p x | x <- xs]

takeWhile 持续取出一个 list 中的元素，直到遇到第一个不满足指定条件的元素

dropWhile 与 takeWhile 相反，dropWhile 函数持续地忽略一个 list 中的元素，直到遇到第一个不满足指定条件的元素

注：这一节中 foldr/foldl/all/any 并不是在 List 上定义的，而是 Prelude 中的一个类型类 Foldable ，代表一系列能 “折叠” 的 Type->Type

Part6 声明类型和类簇

类型别名的声明

通过 type 关键字。

type Position = (Int, Int)

有点像 c++ 里的 typedef

注意这里不能递归，比如不能说 type Tree = (Int,Tree)

类型的声明

可以通过 data 关键字声明新的类型。

data Bool = False | True

其中 Bool 是一个平凡的 Type Constructor 。

True 和 False 是平凡的 Data Constructor

Data Constructor 可以具有参数。

data Shape = Circle Float | Rect Float Float

Type Constructor 可以具有参数

data Maybe a = Nothing | Just a

递归类型

data Nat = Zero | Succ Nat

Nat 具有无穷多个值：Zero, Succ Zero, Succ (Succ Zero), Succ (Succ (Succ Zero)) …

newtype 声明

如果：一个类型仅具有一个 Data Constructor，且 这个 Data Constructor 仅具有一个参数。那么可以使用 newtype 对这种类型进行声明。

例：

newtype Nat = N Int

虽然它和 data Nat = N Int 行为相同，但效率更优

类簇及其实例的声明

类簇声明

class Eq a where
    (==), (/=) :: a -> a -> Bool
    x /= y = not (x == y)
    x == y = not (x /= y)
    {-# MINIMAL (==) | (/=) #-}

注意这里 {-# MINIMAL (==) | (/=) #-} 的作用是：“只要实现 (==) 或者 (/=) 中的任意一个，这个实例就算完整了。”

声明某类型是类簇的实例：

instance Eq Bool where
  False == False =  True
  True  == True  =  True
  _     == _     =  False

当然，这个类型首先要通过 data 或 newtype 声明，才能够成为类簇的实例

这里为了方便理解，给一个作业题：

定一个二叉树类型 Tree a，其中： 叶节点的 Constructor 名为 Leaf，它构造出只包含一个 a 类型值的二叉树。非叶节点的 Constructor 名为 Node，它构造出一个包含两个二叉树的二叉树

答案：

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

Part7 IO 动作

可以认为 type IO a = WORLD -> (a, WORLD)

首先是 Prelude 提供的若干 IO 动作

getChar :: IO Char

读入用户通过键盘输入的一个字符，将这个字符输出到屏幕上，将这个字符作为返回值

putChar :: Char -> IO ()

该函数具有如下行为：接收一个字符 c 作为输入参数，然后进行一个动作：该动作向屏幕输出字符 c。返回一个零元组 ()

return :: a -> IO a

接收一个 a 类型的参数 x

返回一个动作：该动作不产生任何副作用，直接返回 x

do

我们可以用关键字 do，表达 “顺序执行若干动作”。后面我们可以知道， do 其实是基于 Monad 的语法糖，IO 只是 Monad 的一个例子

act :: IO (Char, Char)
act = do x <- getChar
         getChar
         y <- getChar
         return (x, y)

这份代码表示读入三个字符，把第一个，第三个拼起来

另一个例子：

putStr :: String -> IO ()
putStr []     = return ()
putStr (x:xs) = do putChar x
                   putStr xs

为了方便理解，给一个作业题：

在屏幕输入一个整数 n，接下来输入 n 个整数，输出它们的和

代码如下

module HW9 where

getDigit :: IO Int
getDigit = do
    input <- getLine
    return (read input)

calc :: Int -> IO Int
calc 0 = return 0
calc n = do 
    xs <- getDigit
    res <- calc(n-1)
    return (xs + res)


adder :: IO ()
adder = do
    putStr "How many numbers? "
    xs <- getDigit
    sum <- calc xs
    putStr "The total is "
    putStrLn (show(sum))

Part8 Monad and More

是个难点。“在没学过范畴论的情况下，这一部分的学习属于盲人摸象”

Functor (函子)

把适用于 [] 的 map 函数推广到任何一个与 [] 具有相同类型的 Type Constructor

具体的，在 Prelude 中 Functor 如此定义：

class Functor f where

   fmap :: (a -> b) -> f a -> f b

   (<$) :: b -> f a -> f b
   (<$)  =  fmap . const

const :: b -> a -> b
const x _  =  x

Functor 很好理解：就是广义的 map ，可以把 [] 这个 type constructor 替换成其他东西

一个例子：

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

instance Functor Tree where
    fmap g (Leaf x)   = Leaf $ g x
    fmap g (Node l r) = Node (fmap g l) (fmap g r)

当然这个 fmap 不能乱定义，它有一些 law 在里面，这些 law 的解释需要范畴论

Prelude 对于一个定义好的 Functor 实例提供了一个符号 <$> 我们有 <$>=fmap

Applicative Functor

首先我们得做一个感性理解：我们想进一步拓展 fmap，比如

fmap2 :: (a -> b -> c) -> [a] -> [b] -> [c]

我们直接写的话，可能得写成

fmap2 f la lb=[f x y|x<-la,y<-lb]

现在给出 Applicative 的定义（简化版本）：

class Functor f => Applicative f where
    -- Lift a value
    pure :: a -> f a

    -- Sequential application.
    (<*>) :: f (a -> b) -> f a -> f b

我们构造一下 List 的 Applicative 实例：

instance Applicative [] where
    pure :: a -> [a]
    pure x = [x]

    (<*>) :: [a -> b] -> [a] -> [b]
    gs <*> xs = [g x | g <- gs, x <- xs]

可以试一下 pure (*) <*> [1,2] <*> [3,4] ，发现它等于 [3,4,6,8] 。

我们有 fmap2 f la lb=pure f <*> la <*> lb

更进一步，我们可以定义一个经典的函数 SequenceA

sequenceA :: Applicative f => [f a] -> f [a]
sequenceA []     =  pure []
sequenceA (x:xs) =  pure (:) <*> x <*> sequenceA xs

还是以 List 的情况举例，我们有 sequenceA([1,2],[3,4])=[[1,3],[1,4],[2,3],[2,4]]

当 applicative 的定义也有一些 law。

我们到底如何感性理解 applicative？我的理解：Functor 是一个函数作用于一个容器，Applicative 是一个装着函数的容器，这些函数会并行地作用于另一个容器，然后把结果并起来。

Monad

最难理解的来了。

先给出它的定义：

class Applicative m => Monad m where
    (>>=) :: m a -> (a -> m b) -> m b

    (>>) :: m a -> m b -> m b
    m >> k = m >>= \_ -> k

    return :: a -> m a
    return = pure

要把一个 Type Constructor 声明为 Monad 的实例，仅需实现方法 >>=

我们还是拿 List 举例

instance Monad [] where
    xs >>= f = [y | x <- xs, y <- f x]

当然最典的还是 IO。

我们有 ma>>=mb 等价于：

do a<-ma
   mb a

感性理解一下 Monad 在干嘛。啊，我想到了更好的解释：

Functor 其实定义了元素和集合之间的运算（作用）

Application 很像笛卡尔积 Monad 则更像幂次

比如对于表达式 Expr a，在它上面构造的 Monad 其实就是把表达式树的叶子的那些类型为 a 的元素替换成了一个 Expr b。

一个更好的例子是解释器。我们定义类簇： type Parser a = String -> (a,String)，表示按照某种法则对一个前缀做分析，返回解析的结果和字符串剩余的部分

在 Parser 上面就能构造 Monad 的实例了，由于 IO a 是 World -> (a,World) ，你发现我们完全可以仿照 IO 来构造。

instance Functor Parser where

 -- fmap :: (a -> b) -> Parser a -> Parser b
    fmap g p = P $ \program -> case app p program of
                       []         -> []  -- 遇到失败，则传播/返回失败
                       [(v, out)] -> [(g v, out)]
instance Applicative Parser where

 -- pure :: a -> Parser a
    pure v = P $ \program -> [(v,program)]

 -- <*> :: Parser (a -> b) -> Parser a -> Parser b
    pg <*> px = P $ \program -> case app pg program of
                    []         -> []  -- 遇到失败，则传播/返回失败
                    [(g, out)] -> app (g <$> px) out
instance Monad Parser where

 -- (>>=) :: Parser a -> (a -> Parser b) -> Parser b
    p >>= f = P $ \program -> case app p program of
                      []         -> []
                      [(v, out)] -> app (f v) out

比方说设 ma,mb 的类型都是 Parser T,那么

mc :: Parser T
mc = do x <- ma 
     mb x 
     return x

(注意这里 return x=pure x=\st -> (x,st) )

就代表对串 $S$ 按过程 $ma$ 解析得到结果 $x$ 和剩余部分 $S_1$ ，再对 $S_1$ 按 $mb$ 做解析得到剩余部分 $S_2$ ，返回值是 $(x,S_2)$