haskell - foldr1 的融合法则？

Question

对于 foldr我们有融合定律:如果 f很严格，f a = b ， 和
f (g x y) = h x (f y)为所有 x, y ，然后 f . foldr g a = foldr h b .

一个人如何发现/推导出 foldr1 的类似定律？ ? (显然它甚至不能采用相同的形式 - 考虑双方都对 [x] 采取行动的情况。)

Answer 1

您可以使用自由定理推导出诸如聚变定律之类的陈述。 Automatic generation of free theorems这对您有用吗？如果您输入 foldr1，它会自动得出以下语句或类型(a -> a -> a) -> [a] -> a .

如果 f严格和 f (p x y) = q (f x) (f y))为所有 x和 y你有 f (foldr1 p z) = foldr1 q (map f z)) .也就是说，与您关于 foldr 的声明相反你会得到一个额外的map f在右手侧。

还要注意 foldr 的自由定理比你的聚变定律更一般，因此看起来与 foldr1 的定律非常相似.即你有严格的功能g和 f如果 g (p x y) = q (f x) (g y))为所有 x和 y然后 g (foldr p z v) = foldr q (g z) (map f v)) .