折叠优化

Question

我很好奇是否有任何(仅限一阶多态)优化折叠.

对于地图,有砍伐森林:map g (map f ls) => map (g . f) ls和rev (map f ls) => rev_map f ls(在Ocaml中更快).

但折叠是如此强大,它似乎无视任何优化.

Answer 1

显而易见的：

fold_left f acc (List.map g li) => fold_left (fun acc x -> f acc (g x)) acc li
fold_right f li acc => fold_left f acc li (* if (f,acc) is a monoid *)

您可能对主题为“香蕉、镜头、信封和铁丝网的函数式编程”的经典论文感兴趣。但请注意，它是技术性的并且具有难以理解的符号。

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.125

编辑：我的第一条规则的第一个版本是错误的，感谢 vincent-hugot 的编辑。