莎莎荐书第二波
这书的记号和 haskell 高度统一。
补充：书里的代码是 Gofer，后来被 Hugs 取代，Hugs 是 Haskell 的字节码解释器。
sum 可以看作
foldl(0, plus)time = foldl(1，mult)
foldl 和 foldr 的区别。在把数字表示叠起来时视情况，从哪个方向叠就用哪个。
什么时候可以交换？当
f(x, y) = f(y, x)在 rs 里用
iter().fold() 和 .iter().rev().fold() 实现 foldl 和 foldr利用模式匹配自然地定义了树的遍历。还自动高阶函数了，太漂亮了。
在定义一种 datatype 时，顺便定义相应的 fold 函数。也就是一种形状变换的方法。于是一堆方法就全能用上了。（sicp 提到的高阶函数）
下面提到的定义一个 fold，再给它传入类型的定义，就能自动获得相应特化的 fold（不需要手动定义）.
rust 的 derive Debug。感觉有点
attr macro
或者用到反射。
如果把函数的参数元组看成一个状态, 那用模式匹配定义的其实是状态转移. 也就是初中学过的分段函数.
比如
f [] = 0f x: xs ⇒ (f xs) + 1发现这段内容在另一本书里也讲到了.
见 编程的修炼 P23 页
一个函数有 3 个要素, f , 定义域, 值域. 这三者包装成一个元组, 叫做范畴. 写作 (f, A, B)
(x : x < 2) ⇒ x - 1
(x : x < 3) ⇒ x-1
这两个函数是不一样的.
范畴描述了两个 set 中的对象之间的变化规则.
函子则描述了 范畴之间的变换规则.
所以函子是范畴的范畴. (verified by 莎莎)
用人话就是, 函数可以作为函数的传入对象.
P32 的
是状压 dp, 枚举所有子集.
P39
outl = car
outr = cdr
id = (car, cdr)
banana-split 我以前还真想过。就是那时我注意到 sum 可以当作 plus + plus 的零元。sum 一棵树可以把 plus 当 fold 的参数传进去。书里提到的 avg 一个 vec 要跑 2 次我其实也遇到过。就是 generator 会被消耗掉。需要 clone 但仅仅为了求长度。
所以可以用一个 fold 来单次遍历。（length, cur_sum）⇒ （length+1, cur_sum + next）解决。
![from typing import Iteratorgen = iter([1, 1, 1])def avg(g: Iterator) - Pastebin.com](https://www.notion.so/image/https%3A%2F%2Fpastebin.com%2Ffavicon.ico?table=block&id=a2ea6e69-69bf-42c9-870b-d46d3af66ff5&t=a2ea6e69-69bf-42c9-870b-d46d3af66ff5)
contravariant
穿脫原理
比如矩陣的逆/轉置
3
4
P98
rust 的
std::cmp::Ordering::then跳了很多，主要是看不懂。
中间讲了快速幂
还有尾递归优化
第 6 章
The function sort: list A<-list A sorts a list under a given connected preorder R: A«-A.
给定偏序和列表，得到结果。
后面严格定义了快排。大脑跟不上记号。
但是那个写法挺 trivial 的
7.1
最小值，最大值。
是我当初自己推出来的内容，但是我怎么就看不懂记号呢。。
min 的一些边界情况：
- 空列表没有 min
- 一个 not impl Ord 的只有一个元素的
- 一个只有一个 inf 元素的
8.4 背包问题
看这种书就看它是怎么分析我已经会了的问题的。
Binary thinning
这应该是二分法
这本书在分析常见的算法题时，和网上泛滥的博客不同。
- 先进行形式化定义
- 对形式化定义进行变换
- 把结果变成代码
所以这书名字叫 编程代数
9.2 最小编辑距离
