关于 haskell 的一些笔记

国庆学了个爽，把记录的一些东西贴一下。

data 关键字定义新的 type，其形如这种形式——

1	`data Bool = True \| False`

这里的 Bool 即为类型，True 和 False 称为Value Constructor，其列出了该类型所有可能的值。

就“列出所有可能的值”这一点来说，我们可以这样定义 Int——

1	`data Int = -2147483648 \| -2147483647 \| ... \| -1 \| 0 \| 1 \| 2 \| ... \| 2147483647`

仅仅是一种比喻而已，实际并非如此。

自己定义的类型则必须基于已有的六种基本类型。比如这里定义一个 Shape，那些 Float 代表这些形状各边的长度。

data Shape = Circle Float Float Float | Rectangle Float Float Float Float
{-
>>> :t Circle
Circle :: Float -> Float -> Float -> Shape
>>> :t Rectangle
Rectangle :: Float -> Float -> Float -> Float -> Shape
-}

data Shape = Circle Float Float Float | Rectangle Float Float Float Float，这段的意思应当理解为，定义了一个名为 Shape 的 type，其包含 Circle 和 Rectangle 两个 Value Constructor（同时，Circle 和 Rectangle 是 Shape 的值……我不懂为什么），其中 Circle 包含三个字段——xy 坐标，半径，Rectangle 包含四个字段——左上和右下点的坐标（喂，没有旋转嘛！），都为 Float 类型。

可以看到，Value Constructor就像构造函数一样的存在。但是就语义来说，其应当被连带参数（字段）当作一个整体，即像(Circle 1 2 3)这样看待。这种情况实际上是因为——其文字形式表述和其定义形式是一致的。

这么来说，对所有(Circle a b c)，其中 a，b，c 都为 Float，其都是 Shape，或者都属于 Shape 这个 type。(Circle a b c)之于 Shape，就像 True 之于 Bool——就像字面量，只不过 Shape 在三个方向或四个方向上能够很大地延展下去罢了（指能取很多值）。

自定义的 type 也可以被模式匹配，下面展示了求形状的面积的函数——

1
2
3

surface :: Shape -> Float
surface (Circle _ _ r) = pi * r ^ 2
surface (Rectangle x0 y0 x1 y1) = abs $ (x0 - x1) * (y0 - y1)

我们写不出fn :: Circle -> Float这样的函数，因为 Circle 不是 Type，Shape 才是，正如我们不能写出True -> Int的函数，不能写出1 -> Int的函数。

type 当然也是可以层层抽象的……而且 Haskell 会聪明地帮我们进行模式匹配（再多几层怎么办？用 where 吧……）

data Point = Point Float Float deriving Show
data Shape = Circle Point Float | Rectangle Point Point deriving Show

surface :: Shape -> Float
surface (Circle (Point _ _ )  r) = pi * r ^2
surface (Rectangle (Point x0 y0) (Point x1 y1)) = abs $ (x0 - x1) * (y0 - y1)

考虑到 Value Constructor 也是函数，可以利用其定义一些其他函数用来生成 Shape……比如来一个在原点的圆！

centerCircle = Circle $ Point 0 0 
{-
>>> centerCircle 5
Circle (Point 0.0 0.0) 5.0
-}

data Person = Person {
    firstName :: String,
    lastName :: String,
    age :: Int,
    height :: Float,
    phoneNumber :: String,
    flavor :: String
} deriving (Show)

为字段命名，这种形式称为record，haskell 会为每一个字段生成“getter”。

同时，构造 Person 时，可以使用被称为Record Construction的语法——

1	`Person {firstName="rua",lastName="www",age=12,height=170,phoneNumber="1111111111",flavor="wtf"}`

这种构造必须给定全部字段，有遗漏的会有 error。

We usually use type parameters when the type that’s contained inside the data type’s various value constructors isn’t really that important for the type to work.

如上，当我们对 type 所包含的某个值的具体 type 不在意，即其的 type 对我们并不造成影响时，我们就用 type parameter。

比如，Map 的 k 和 v 就是应该应用 type parameter 的时候。

Functor 代表越过容器对内容进行操作的能力，Applicative 代表合并两个容器内容的能力。

Lisp 厨欢喜！

data List a = Empty | Cons a (List a) deriving (Eq, Show, Read, Ord)

car :: List a -> a
car Empty = error "cao!"
car (Cons a _) = a

cdr :: List a -> List a
cdr Empty = Empty
cdr (Cons _ a) = a

将 Cons 中置，我们就得到了：，而 Empty 就是 []——

1	lst = 1 `Cons` (2 `Cons` (3 `Cons` Empty))

可以定义中置运算符——必须为全符号且指定优先级——

1
2
3

infixl 5 **** --- 这个签名称为 fixity，这里的 infixl 表示中置左结合
(****) :: Num a => a -> a -> a
a **** b = a * b * b * b

在定义 data 时可以使用中置运算符作为 Value Constuctor——

infixr 5 :-:
data List a = Empty | a :-: (List a) deriving (Eq, Show, Read, Ord)
{-
>>> 3 :-: 4 :-: 5 :-: Empty
3 :-: (4 :-: (5 :-: Empty))
-}

这玩意着实有点 geek。

模式匹配匹配的是什么？Value Constructor！这样的话，对数字，对 char 进行匹配就非常有趣了——丘奇数！

对 List 进行模式匹配时，能够使用(x:xs)这种形式也是符合逻辑的——:就是一个值构造器！只不过是中缀函数的形式罢了！所以也可以这么使用——

1
2
3

sum' :: Num p => [p] -> p
sum' [] = 0
sum' ((:) x xs) = x + sum' xs  -- 就像 Cons 的使用法

[]也同理——它也是值构造器。不得不感叹，Haskell 的设计太好了。

将 type 作为 typeclass 的实例的时候，对于带类型参数的 type constructor，有一些东西需要注意。

考虑data Either a b = Left a | Right b，它是一个 Functor 的实例。fmap 对其表现在于对 Left 则无作用，对 Right 则返回Right $ f r，其中 r 为(Right r)。因此 haskell 建议使用 Left 包装错误，使用 Right 包装值。

这是 Either 对 Functor 的实现。

1
2
3

instance Functor (Either a) where
    fmap f (Right r) = Right $ f r
    fmap _ (Left l) = Left l

这里为什么使用·EIther a？考虑 fmap 的签名——

1	`fmap :: Functor f => (a -> b) -> f a -> f b`

这里的 f 是实现了 fmap 的 type，从签名中可以看到，f 应当是一个接受单参数的 type constructor。

于是，Either a 就能够解释了——对 Either 进行偏调用，获取一个接受单参数的 type constructor——可以说 fmap 的函数签名可以这样表示——

1	`fmap :: Functor f => (a -> b) -> (Either c) a -> (Either c) b`

这里的 c 其具体类型是无关紧要的——对 fmap，它不可见。

于是这就加上了一个限制——对实现 fmap 的 type，只有最右边的 type parameter 是可以在 fmap 中被改变的（从 a 到 b），而前面的 c 是改不了的，无论是它的 type 还是 value（type 不可变是因为这在函数签名中已经限定，value 不可变是因为该方法无法获取关于 c 的任何信息，任何操作）。比如，我们想用 Left 来存数据，想用 Right 来存错误，这就是不可行的——Left 没得变。真坏！

然后是 kind 概念……

如果说 type 是 value 的标签的话，kind 就是 type 的标签。type 标识一个 value 的集合，kind 标识一个 type 的集合。

kind 的形式化表述很像 type 构造器的签名——

-- >>> :k Either
Either :: * -> * -> *

-- >>> :k Either Int 
Either Int :: * -> *

-- >>> :k Either Int String
Either Int String :: *

*表示具体类型（just type， concrete type， star type），可以看到 Either 接受两个具体类型，返回一个具体类型。

使用：t 来获取 value 的 type，使用：k 获取 type 的 kind。

haskell 的错误提示里 type 是 data constructor

关于 Functor 的例子，用 kind 的形式来说，Functor 接受一个* -> *的 type，而 Either 是一个* -> * -> * 的 type，因此需要进行一个偏调用。

一个问题——:k 对 typeclass 也有效吗？看这签名，好像是根据 kind 生成约定的样子。

事情变得抽象了——type parameter 可以是具体类型，也可以是 type constructor（显然这两样是同质的，之后一概以 type 称呼，顶多分成具体 type 和抽象 type）

1	`data Frank a b = Frank {frankField :: b a} deriving (Show)`

根据其 body，b 是一个* -> *，a 是一个*，于是 Frank 是——

1	`Frank :: * -> (* -> ) -> `

卧槽！

请问这样奇怪的 type 哪个 typeclass 愿意收呢（恼

1 2	`class Tohu t where tofu :: j a -> t a j`

这里的 Tohu typeclass，其中的 j 就是* -> *，t 的类型根据 t a j 能够推导出来——* -> (* -> *) -> *

一个重点是去了解函数/类型签名和函数体的关系——签名再怎么花哨也行，对函数体不会有影响。

kind 能够形式化表述 type 的类型参数，type declaration 形式化表述 function 和 value 的参数。

haskell 中的 Unit 使用 () 即空的 tuple 表示。

return 将值包装成 Monad。这可以用在 IO Monad 里，name <- return xxx来绑定值到……名字上，也可以用在其他 Monad 里，比如return 1 :: Maybe Int，能拿到一个Just 1。但是没必要。

Don’t think of a function like putStrLn as a function that takes a string and prints it to the screen. Think of it as a function that takes a string and returns an I/O action.

不要把带副作用的函数看作接受参数并进行操作的“过程”，而是将这些函数看作接受参数，返回 IO action 的函数！这种看法是为了更好的组合操作，把代码/过程当作数据来看待……

随机数是有副作用的——对同一个获取随机数的函数，每次调用都是不同结果。

但这只是表面上的——随机数是通过某种显式或隐式的状态生成的。

haskell 允许通过一个整数（作为种子）来生成一个随机数生成器——

--- >>> gen = mkStdGen 42
StdGen {unStdGen = SMGen 9297814886316923340 13679457532755275413}

--- >>> random gen :: (Integer, StdGen)
(1275548033995301424,StdGen {unStdGen = SMGen 4530528345362647137 13679457532755275413})

--- >>> random gen :: (Integer, StdGen)
(1275548033995301424,StdGen {unStdGen = SMGen 4530528345362647137 13679457532755275413})

--- >>> random gen :: (Integer, StdGen)
(1275548033995301424,StdGen {unStdGen = SMGen 4530528345362647137 13679457532755275413})

--- >>> random gen :: (Double, StdGen)
(0.930852402521634,StdGen {unStdGen = SMGen 4530528345362647137 13679457532755275413})

可见，无论多少次，这玩意都返回同样结果，是纯函数。

然后就是有趣的地方——haskell 不止返回了随机数的值，也返回了一个（或者说下一个）随机数生成器，这下一个的值也是一样的……

于是，函数式的随机数解决方案来了！把生成随机数所需的状态作为参数传递嘛！太聪明了！这样的话只需要在生成最初的生成器的时候要求外界输入了！

这也可以看作是一种妥协方案……当然也可以在 IO 里进行随机数的生成。

同时，考虑到每次都要拿新的种子生成器很麻烦，可以整一个获取随机数列表的函数（haskell 有原生实现，randoms）——

1 2	`randoms gen = value : randoms nextGen --- 没有边界条件，显然是个利用懒求值的无限流 where (value, nextGen) = random gen`

模式匹配匹配的是值的形式（也就是值构造器）而非值的内容（值本身），所以模式这个词非常符合。

小小的感受——对那些只被模块内部使用的函数，且能够清晰规划出哪些情况将会被使用，那些情况将不会的情况下，使用 error 标识不可能的情况是合理的（当然，如果这个函数仅被使用过 1 次，考虑将其放到 where 子句中。

函数有着自己的 type constructor——(->)。这是一个中缀的 Type Constructor。

可以认为，通过 fmap 的偏调用，可以把一个 (a -> b) 的函数转换成 (f a -> f b) 的函数——稍微重新诠释一下 fmap 函数的签名即可——

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

自定义 type 要成为 Functor 的实例，有两条规则需要遵守，第一条是——

1	`fmap id = id`

比如， fmap id (Just 1) == id (Just 1)

第二条是——

1	`fmap (f . g) = fmap f . fmap g`

比如对 Maybe 的 Just 的推导如下——

fmap f . fmap g $ Just x
    = fmap f $ Just (g x)
    = Just (f (g x))
fmap (f . g) $ Just x
    = Just ((f . g) x)
    = Just (f (g x))

一个不合理的 Functor 的实例 type 如下，其中 C 意为 Counter，该 type 试图保存至今为止被映射的次数——

data CMaybe a = CNothing | CJust Int a deriving (Show)  
instance Functor CMaybe where
    fmap _ CNothing = CNothing
    fmap f (CJust counter a) = CJust (counter + 1) $ f a

这个实现不符合第一条规则——

1 2	`fmap id (CJust 0 10) == CJust 1 10 id (CJust 0 10) == CJust 0 10`

If a type obeys the functor laws, we know that calling fmap on a value of that type will only map the function over it, nothing more.

也可以理解为，Functor 是在一个特定的上下文中对值进行映射/修改。这个上下文不止包括数据所对应的 value Constructor，还可以包括更多东西，比如对 IO，它包括整个世界。（这里的上下文 context 指的是计算上下文 computation context 吗？）

Applicative 全称是 Applicative Functor，这意味着一个 type 如果是 Applicative，则它必然也是 Functor，这可见于 Applicative 的定义——

1
2
3

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

pure 函数之所以名叫 pure，是因为该函数将其放入了一个特定的，最小化的，默认的上下文（也就是那个“box”，可以认为像 Maybe，Either 这样的 Functor 实际上是定义了一个盒子来保存一定的东西，这个盒子也就是一定的上下文）。默认，default，也叫 pure。

最小化体现在哪里？pure 42 :: [Int]会得到[42]。这显然不是真正最小的——那是[]，可是[]是无法储存值的，就如 Maybe 的 Nothing 一样，所以最小在这里指单例的列表。

A better way of thinking about pure would be to say that it takes a value and puts it in some sort of default (or pure) context—a minimal context that still yields that value.

<*>就是 Applicative 的“业务”函数，它的签名值得和 fmap 对比看——fmap :: (a -> b) -> f a -> f b。

查看 Monad 的定义，发现更加有趣的事实，感情 Monad 是 Functor 一步一步“增强”的结果。

Prelude> :i Monad
type Monad :: (* -> *) -> Constraint
class Applicative m => Monad m where
  (>>=) :: m a -> (a -> m b) -> m b
  (>>) :: m a -> m b -> m b
  return :: a -> m a
  {-# MINIMAL (>>=) #-}
      -- Defined in ‘GHC.Base’

把值放在 Functor 里容易，取出来却不容易。比如 IO Monad（当然，它也是 Functor），它持有的值是拿不出来的。~~除非使用 unsafe 的方式~~。这是为了保证副作用不扩散。

Applicative functors and the applicative style of doing pure f <*> x <*> y <*> … allow us to take a function that expects parameters that aren’t necessarily wrapped in functors and use that function to operate on several values that are in functor contexts.

pure 和<*>结合使用，能达到这样的效果——使原本用于一般的值的函数能够应用在 functor 的上下文中，比如下面展示了对 Maybe（Just）中包裹的元素进行操作。

1 2	`Prelude> pure div <> Just 5 <> Just 2 -- 对一般的值，是 div 5 2 Just 2`

也可以认为pure f <*> x等价于fmap f x，于是对于pure f <*> x <*> y <*> ...，可以表示为fmap f x <*> y <*> ...。而 haskell 提供了<$>函数——f <$> x = fmap f x。

于是对pure div <*> Just 5 <*> Just 2，可以将其表示为 fmap div (Just 5) <*> Just 2 ，或者div <$> Just 5 <*> Just 2 ，显然最后的形式是最合适，最易懂的，它就像普通的函数调用中间插入一些奇怪玩意。

对 List，它的 Applicative 的定义是这样的——

1
2
3

instance Applicative [] where  
    pure x = [x]  
    fs <*> xs = [f x | f <- fs, x <- xs]

List 的<*>的行为很奇怪，做了个“笛卡尔积”，如果认为[1,2,3]这种形式表示某个值的可能取值为 1，2，3，则该操作符表达了所有可能的结果——[(+) 1,(+) 2, (+) 3]和[4,5,6]这两个“非确定”的值组合得到的“非确定”的结果。使用<*>能在一定程度上替代 List 推导式。

1 2	`Prelude> (+) <$> [1,2,3] <*> [4,5,6] [5,6,7,6,7,8,7,8,9]`

对 IO，它的 Applicative 的实现为——

instance Applicative IO where  
    pure = return  
    a <*> b = do -- <*> :: IO (a -> b) -> IO a -> IO b
        f <- a  
        x <- b  
        return (f x)

本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 协议，转载请注明出处！

关于 lambda 演算上一篇

关于 haskell 的.和$运算符下一篇