Haskell 乐派与数学题

《Haskell 乐派》(The Haskell School of Music)是一本…… Haskell 语言教程?计算机音乐教程?

呃…… 反正我都没学会(划)。

Paul 的前作《Haskell 表现学派》(The Haskell School of Expression)似乎也是很优秀的教程呢,不过并没有读过。

Donya 接手完成出版的实体书是 2018 年末的新鲜产物,目前只有一个花式 TBD 的 draft book 可以看看…… 期待学校图书馆订购的实体书到了之后前去围观~

Update 2019-06-03: 今日份的快乐!我爱文图!

需要有程序设计基础以及少量音乐背景知识,所以不算是程序设计或者计算机音乐的入门教程。配合其它 Haskell 书籍共同食用效果更佳。

Draft book 的小 bug 就不抓啦,然而直接改 tempo 实现连音这种操作真的好嘛 = =

做了不少习题,没有刻意设置难度,但有不少「创造性」任务(写曲子),也有一些比较杂的题。写出来的东西都太菜啦,所以只放了两道有意思的「数学题」在这儿。当然在 dalao 看来也都是 trivial 的 > <


习题 5.3(Y Combinator)

问题

  1. 给出下面函数的主要类型。

    1
    fix f = f (fix f)
  2. fix 函数重写下面的函数,使之成为非递归形式。

    1
    2
    remainder :: Integer -> Integer -> Integer
    remainder a b = if a < b then a else remainder (a - b) b

解答

假设 fix f 的类型是 t

由于等式右端的 f 接收了一个类型为 t 的参数,可设其类型为 t -> u。那么等式右端的类型即为 u

又因为等式左右类型相同,故 t = u,即

f   :: t -> t
fix :: (t -> t) -> t

不妨将一个 f :: Integer -> Integer 代入 fix

fix f x = f (f (f (f (... (fix f x)))))

此时不难意识到:对于一元函数 ffix f = ⊥

要使 fix f 停机,需要使得某个特定条件下 fix f x 能够停机。也就是说,fix f 这个函数应当在 x 满足某些条件的情形下短路,使得 fix f 不被继续递归求值。

不妨假想一个栗子:

fix f :: Integer -> Integer
fix f x = if x < 0 then x else fix f (x - 1)

当然,这里的 f 类型为 (Integer -> Integer) -> (Integer -> Integer)。而这个 fix fx < 0 时短路,而且在任何输入上都停机。

怎么通过 fix f 找到这个 f 呢?回到 fix 的定义:

fix f x = f (fix f) x

所以可以这样构造:

f f' x = if x < 0 then x else f' (x - 1)

现在有了一个一元函数的例子,回到原题的二元函数就很容易啦。

remainder = fix r
fix r a b = if a < b then a else fix r (a - b) b
r r' a b = if a < b then a else r' (a - b) b
remainder = fix r

当然也可以用 Lambda 表达式写成一行:

1
remainder = fix (\r' a b -> if a < b then a else r' (a - b) b)

通过这一方式,可以将所有递归函数转写成含有 fix 的 Lambda 表达式。也就是说,我们在没有定义递归的 Lambda 演算系统中构造了递归……

…… 可是 fix 是递归定义的来着?

它要也能写成非递归形式该多好,不如尝试一下!也就是对于任意一个 f,找到下面这个 f'

fix f x = f (fix f) x
f'    x = f f'      x

好像有点困难啊?

几年前的一本书《暗时间》当中提到过这个,翻出来看看……(读书人的事能叫作弊嘛!

只见书上赫然写着几个大字:self

self?记得是个把「面向过程」变成「面向对象」的方法…… 难不成它也能把「非递归」变成「递归」??这么说,只要构造一个 g,它接收一个 self,满足……

g self x = f (g g) x

那么 g g 就是我们所寻求的 fix f!于是自然有了这个 ——

g self x = f (self self) x
f' = g g

换言之……

fix f = g g  where g self = f (self self)
fix = \f -> (\self -> f (self self)) (\self -> f (self self))
    = \f -> (\g -> f (g g)) (\g -> f (g g))

成功啦!非递归的不动点函数!

它有个炫酷的名字叫做 Y combinator。(对对对就是 Hacker News 那家公司)

不过 GHC 并不吃这一套。

• Occurs check: cannot construct the infinite type: t0 ~ t0 -> t
  Expected type: t0 -> t
    Actual type: (t0 -> t) -> t

这是因为 GHC 的类型系统无法如此表示 fix 函数的主要类型。推导一下就能发现一些类似 t0 -> tt 相同的限制,所以会产生如上所述的 infinite type。

虽说有一些 workaround 让 GHC 接受类似形式的定义(比如 定义递归类型),不过在 Haskell 里面并没有什么必要 —— 毕竟 Haskell 支持函数递归。可如果有一门不支持递归的动态类型函数式语言,这样的定义就能大显身手了叭 乁| ・ 〰 ・ |ㄏ

这个看上去超级简单自然的推导还是归功于天上掉下来的 fixself 啦,当初 Y combinator 被创造出来的心路历程大概也是很艰难呢~

习题 5.5(Currying, Composition)

问题

有类型 ABCD,以及函数 fg

要求用函数 fg 表示函数 h,使得 h x y = f (g x y),并且仅通过函数的组合完成,即表达式只包含函数的运算,不出现参数和 Lambda 表达式。

三个函数的类型如下。

f :: C -> D
g :: A -> B -> C
h :: A -> B -> D

解答

如果能找到一个类型为 (C -> D) -> (A -> B -> C) -> (A -> B -> D) 的函数 t,再把 fg 作为参数塞进去,问题就解决了。(废话

考虑一个简化问题:(C -> D) -> (A -> C) -> (A -> D)。容易看出答案是 (.)

(.) :: (C -> D) -> (A -> C) -> (A -> D)

作代换 C/(B -> C)D/(B -> D),可得 (.) :: ((B -> C) -> (B -> D)) -> (A -> B -> C) -> (A -> B -> D)

距离答案近了好多的样子?把已得和所求对比一下:

(.) :: ((B -> C) -> (B -> D)) -> (A -> B -> C) -> (A -> B -> D)
t   ::               (C -> D) -> (A -> B -> C) -> (A -> B -> D)

如果有一个下面这样的函数 r,是不是就可以得到所求的 t 了呢?

r   :: (C -> D) -> ((B -> C) -> (B -> D))

不难看出 t = (.) . r。所以只需找出 r,原问题便迎刃而解。

可达鸭眉头一皱,发现 r 也是 (.)。于是愉快代回:

t :: (C -> D) -> (A -> B -> C) -> (A -> B -> D)
t = (.) . (.)

h :: A -> B -> D
h = t f g

等等等登!

h = ((.) . (.)) f g

顺带一提,这个形式对于更多参数的情形也都是正确的。

(.) . (.) . (.)
  :: (b -> c) -> (a1 -> a2 -> a3 -> b) -> a1 -> a2 -> a3 -> c

还有把 h 写成下面这样可以显得更玄一些……(x

h = (.) (.) (.) f g
作者:Shiqing
链接:https://kawa.moe/2019/02/hsom-exercises/
版权:文章在 CC BY-NC-SA 4.0 许可证下发布。转载请注明来自 quq