Haskell 学习小记

Language

September 08, 2024

origin written at 2020-11-01

纯函数

Haskell 是 纯函数 语言，语义实现的全过程都在于形式演算，而非传统的值计算。¹

形式化简

阿尔法化简（$\alpha$-conversion）

通过变量名重命名来做等价变换:²

\[\lambda x \rightarrow \lambda y \rightarrow x + y \equiv \lambda a \rightarrow \lambda y \rightarrow a + y\]

贝塔化简（$\beta$-reduction）

用实际的函数体替换掉参数。

伊塔化简（$\eta$-reduction）

冗余简化:

\[\lambda x \rightarrow f(x) \equiv f\]

柯里化（currying）

函数都是单参数的，多参函数，是通过柯里化方式转换成单参数：

\x1 x2 ... xn -> f(x1 x2 ... xn) 的实际形式是 \x1 -> \x2 ->...xn -> f(x1 x2 ... xn)。

或者说，函数参数是右结合的。

举个例子:

> let add = \x -> \y -> x + y
> add 1 2
3
> let add' = \x y -> x + y
> add' 1 2
3

不动点（fixed point）

本身的概念是满足 $f(x) = x$ 的 $x$ ，这里用作递归的形式演算 fix f = f (fix f) 。

比如牛顿法开方：

-- 迭代次数 -> 根值 -> 结果
-- Normal Bad Version
sqrtNB 0 x = x
sqrtNB n x = (sqrtNB(n - 1)x + x / sqrtNB(n - 1)x) / 2

-- 性能很差
> sqrtNB 20 5
2.23606797749979
(1.81 secs, 914,438,408 bytes)

使用不动点为：

sqrtFix n x = fix (\f n t ->
    if n <= 0
        then t
        else f  (n - 1)
                ((t + x/t) / 2))
    n x

> sqrtFix 20 5
2.23606797749979
(0.01 secs, 93,688 bytes)

` fix` 实际实现里：

fix f = let x = f x in x  -- `in` 限制了 `let` 绑定的作用域

函子

在这里我们不讨论这些接口的范畴论（category theory）相应概念的起源，也许有一天我研究了范畴论后，可以在函数式语言的进阶讨论中讨论这些概念，而现在这至少与我们理解这些接口的实际工作无关。

另一方面范畴论属于哲学数学，可以这么地在抽象地抽象上看问题，但这样有特别的意义吗，它好像还缺乏一个能特别证明它价值的领域。

所谓函子（Functor）

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

函子提供了一种在上下文 f ³⁴里进行函数操作的方式。

从名字上它叫函子不叫函数，就是暗示它支持把一般函数作为一个组件，带入上下文里（进行函数操作）。

class Functor 只有一个必须实现的接口函数 fmap ，它的签名也很好地反映了函子的本质：接受一个函数 a->b ，把它应用在上下文 f 里，使得 f a 变为 f b 。

（标准库）还为函子的 fmap 导出了等价的中缀操作符 <$> ⁵

infixl 4 <$>

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

此外，class Functor 提供了一个有默认实现⁶的 (<$) ⁷。

其中，. 有 (.) f g = \x -> f (g x) ，const 有

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

可以手工（形式演算）推出 (<$) 的类型签名：

fmap . const = a -> f1 (g a) ，展开 .

g = a->b->a => (g a) = (b->a)，展开 const
f1 = (a -> b) -> f2 a -> f2 b ，展开 fmap
f1 (g a) = f1 (b->a) = f1 b -> f1 a ，规约替换 (g a) 和 f1
a -> f1 (g a) = a -> f1 b -> f1 a ，规约替换 f1 (g a)
fmap . const = a -> f b -> f a ，重命名 f1 = f

应用函子（Applicative）

class Functor f => Applicative f where
    {-# MINIMAL pure, ((<*>) | liftA2) #-}

    pure :: a -> f a

    (<*>) :: f (a -> b) -> f a -> f b
    (<*>) = liftA2 id

    liftA2 :: (a -> b -> c) -> f a -> f b -> f c
    liftA2 f x = (<*>) (fmap f x)

    (*>) :: f a -> f b -> f b
    a1 *> a2 = (id <$ a1) <*> a2

    (<*) :: f a -> f b -> f a
    (<*) = liftA2 const
    
-- ...

infixl 4 <$
infixl 4 <*>

应用函子的设计是在上下文里为同一个函数连接多个参数。

class Applicative 最小实现需要实现 1. pure ，2. (<*>) 与 liftA2 中任意一个 ⁸。

`pure`

pure :: Applicative f => a -> f a

把一个参数装进上下文 f 中。⁹¹⁰

`<*>` 和 `liftA2`

Applicative f => f (a -> b) -> f a -> f b

因为 <*> 与 liftA2 分别有以对方为基础的默认实现，所以接口只需实现其中任意一个，让我们看下它们的函数签名和默认实现。

(<*>) :: Applicative f => f (a -> b) -> f a -> f b
(<*>) = liftA2 id

liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
liftA2 f x = (<*>) (fmap f x)

相比于前面的 <$> ， <*> 是说把 a -> b 也放进上下文 f 里，这样做的好处是可以利用函数柯里化，在上下文里连接多个参数，这也是应用函子的本质。

比如有一个多参函数 a -> b -> c -> d ，那么可以结合 <$> 操作符，用 (a -> b -> c -> d) <$> f a <*> f b <*> f c 的形式在上下文里传参。¹¹

而 liftA2 则像是多一个参数的 <$> 。

再来看看 <*> 的默认实现，按照形参实参一一对应的原则有：

id :: a -> a

liftA2 id 
=> (a -> (b -> c))      -> f a -> f b -> f c
=> ((b -> c) -> b -> c) -> f (b -> c) -> f b -> f c
                        => (<*>)

<*> 的默认实现就有点儿隐晦了，至于 liftA2 的默认实现，那更是神中神，直接不演了，表明定义的实质就是模式匹配：

liftA2 :: (a -> b -> c) -> f a -> f b -> f c
(<*>)  :: f (a -> b) -> f a -> f b
fmap   :: (a -> b) -> f a -> f b

            liftA2 f x = (<*>) (fmap f x)
(a -> (b -> c)) -> f a = (<*>) ((a -> (b -> c)) -> f a)
             fb -> f c = (<*>) f (b -> c)
                     _ = f b -> f c

注意函数实现里的实参是单独的，而函数签名里的形参则与它所在的 class 同名对应。

`<` 和 `>`

在上下文的环境里，分别只保留左边参数和只保留右边参数

infixl 4 <*, *>,

(<*) :: f a -> f b -> f a
(<*) = liftA2 const

(*>) :: f a -> f b -> f b
a1 *> a2 = (id <$ a1) <*> a2

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

Applicative 实例

[]

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

Maybe

instance Applicative Maybe where  
    pure = Just  
    Nothing <*> _ = Nothing  
    (Just f) <*> something = fmap f something

> (fmap (+) (Just 3)) <*> Just 2
> Just 5

> pure (+) <*> Just 3 <*> Nothing
> Nothing

Alternative

应用函子的一个继承

infixl 3 <|>
class Applicative f => Alternative f where
	empty :: f a
    (<|>) :: f a -> f a -> f a

下面举一个最常见的例子：

instance Alternative Maybe where
    empty :: forall a. Maybe a
empty = Nothing
    Nothing <|> r = r
    l       <|> _ = l

> Nothing <|> Nothing <|> Just 1 <|> Just 2
> Just 1

单子应用（Monad）

醋来了，可以说整篇学习笔记就是为了搞明白 Monad 是什么而包的饺子。

经常地，在某个新生的编程语言的相关论坛上，当提到函数式特别是纯函数式的编程语言范式的时候，总会有一些人，不问自答、不清自来地问：“ xx（该编程语言）能从 Haskell 的 Monad 里学到什么？”，每次看到这儿我就会想，这个 Monad 到底是什么，怎么来不来的就要从它那儿学什么东西。

而找的一般教程总是把 Monad 搞得玄而又玄，并不清楚明白，于是有了这个学习笔记，于是来到了这里。

Monad ¹² 和 Alternative 一样，它也是对应用函子的一个继承。

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

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

    return      :: a -> m a
    return      = pure
    
infixl 1  >>, >>=

从定义上也看出来了，class Monad 主要就是 >>= 的实现，是从一个上下文里的值 m a，传一个从内部值变换到另一个内部值并把它包装回上下文的函数 a -> m b，最后得到一个上下文的值 m b。

从 >>= 的函数签名上很容易发现，它的返回类型和首参类型是一样，这必然意味着必然可以有 M a >>= f1 >>= f2 >>= 2 ... >>= fn 这样的形式。

如果说 <*> 是在上下文环境里连接多个参数，那么 Monad 提供的 >>= 就是在上下文里连接多个操作。

>>= 也有个 Haskell 里的名字叫 “bind” ，相对地 >> 是忽略之前上下文的值。

Haskell 里有个特殊语法 do 用来简化这种 Monad 上下文的函数连接。

do
	m a
	f1
	f2
	f3

还可以用特殊语法 x <- f1 来从某一步的上下文里取值。

还有一个常用的工具 guard ，功能如其名：

guard           :: (Alternative f) => Bool -> f ()
guard True      =  pure ()
guard False     =  empty

empty 是 Alternative 实现时定义的，是一个明确的表示失败的值。

从 `Monad` 里学到什么

与其说从 Monad 里学到什么，不如说从 Functor 里学到什么，这一系列都是在探讨在某个上下文环境里做操作的语义。

对于纯函数式语言来说，有其在具体实现上的普遍意义。

而我关心的是非纯函数式语言（的设计）能从中获得什么意义？

应该是提供一种在非确定性上下文里操作的语义。

首先，明确下非确定性上下文的特征，它应该有成功的，可以继续执行下去的结果；和一种或多种失败的，没有继续执行下去意义的结果。就像经典的 IO 操作，如果前面操作没有成功，那么后面继续也就没有意义；或者连续查询的操作，如果前面是空的，后面在空集上继续查询也没有意义。

这么看来 Rust 的 Result 和 ? 机制已经把这个语义利用得到位了，也不能指望更多了。

在编写编译器的 parser 部分，就大量使用到这种语义，使得我们的代码只需要呈现主要的逻辑，也为程序员节省宝贵的精力。

fn parse_fn() -> Result<Fn, SomeError> {    
    Ok(Fn {
        name: parse_fn_name()?,
        params: parse_fn_params()?,
        ret: parse_fn_ret()?,
        body: parse_fn_body()?
    })
}

而普通程序就要写如下

func parse_fn() (Fn, error) {
    name, name_err = parse_fn_name()
    
    if name_err != nil {
        return .., name_err
    }
    
    params, params_err = parse_params()
    
    if params_err != nill {
        return .., params_err
    }
    
    ret, ret_error = parse_ret()
    
    if ret_err != nill {
        return .., ret_err
    }
    
    body, body_err = parse_body()
    
    if body_err != nil {
        return .., body_err
    }
    
    return Fn {
        name,
        params,
        ret,
        body
    }
}

还有一个关于 Haskell使用 bind 而不是 kleisli-构成的进阶讨论，回答很深入，但只是标记在这里，不做进一步讨论。

注解

相比之下，作为函数式语言的另一个分支，Lisp家族，以 CommonLisp 为例，实际上广泛地使用可变的数据结构和有副作用的函数。 ↩
当然前提是不能有命名冲突。 ↩
f 是单参的类型构造器（一种特殊的函数），不过正如前面讲的，Haskell 多参函数的本质都是柯里化的单参函数 ↩
按照官方文档的说法， f a 也可以叫做 action ↩
infixl 关键字规定中缀操作符是（向）左结合的，并指定它的优先级，给的数字越大优先级越高，类似地还有指定右结合的 infixl 和不指定结合性的 infix （此时，只能通过括号显式指定结合性）；并且不显式指定结合性和优先级，那么默认是左结合，优先级为最高（最高为 $9$ ）。 ↩
文档里也支持自己实现更高效的版本 ↩
从命名规律上讲，不妨称之为：“左偏刀”，还有 <$> ，可以称之为 “全刀”，后面还有一些特殊符号的运算符：<*> ，<* 和*>可以依次称之为 “全星”，“左偏星” 和“右偏星” ↩
或者两个都实现，只要二者不发生矛盾 ↩
=> 前面是类型约束 ↩
在非纯函的语言看来，这个函数签名简直莫名其妙，这个 f 它从哪儿来的，怎么绑定的？这都不知道，唯一好像可以类比得是闭包里捕获的自由变量，但完全没有类比意义，基本上在 Haskell 里需要完全抛弃基于值的非纯函的编程模型，只考虑形式演算的问题，在这种前提下，我们就知道 f 会在形式演算的过程中根据签名匹配出来。 ↩
<$> 和 <*> 虽然优先级相同，但都是左结合 ↩
注意和名字相近的 Monoid 的区别，二者只是在范畴论上有单子可以作为 Monoid 的范化概念的关系，但从编程实际来看，二者没什么直接关系，只是名称有点儿容易搞混。Monoid 本身是一个经典代数结构，指的是有“幺元”的半群，在 Haskell 里也是一个接口（class），继承了另一个接口 semigroup 。 ↩

Haskell 学习小记

纯函数

形式化简

阿尔法化简 （$\alpha$-conversion）

贝塔化简 （$\beta$-reduction）

伊塔化简 （$\eta$-reduction）