BMF

semigroup: 有结合律，如

monoid: semigroup + 左右单位元，如

homomorphism 的定义：

即 到 的一个同态变换

map 记为 ，reduce 记为 ，如 ，

表示 fordl， 表示 scanl

Join rules: ，

是 homomorphism from to 当且仅当满足，

为 homomorphism

一个 homomorphism 当且仅当可以写为 。

1)

2)

inits ，inits =
tails ，tails =

segs =

Accumulation Lemma:

Horner’s Rule

满足，若有

证明：

最后一步是归纳假设，最后再证一个引理就好了

使用 BMF 证明 Max Segment Sum

即证

length, sort 等都是 homomorphism

证明 是 homomorphism：。

运算

是一个 homomorphism

是 homomorphism

中间有一步 ，即分配律。

fusion，我理解起来就是除去无用计算，例如 ，怎么通过这个来演算到更快的程序，，怎么通过这个变到线性。

fusion lemma

在 max 的例子中， （从插入排序开始推导），这样就找到了

在reverse 的例子中，记

有

那么就找到了

这样 可以写成一个 forlr，即 ，即找到了线性做法。

用 fusion 做一些证明

we have

therefore

we have

thereforre

Tupling，感觉就是在 fold 的时候多记一些东西避免重复操作

，记成 “pair”，就可以只有一个 。