我只是好奇是否有任何(仅限一阶多态)折叠优化。
对于 map ,有森林砍伐:map g (map f ls) => map (g . f) ls
, 和 rev (map f ls) => rev_map f ls
(在 Ocaml 中更快)。
但是 fold 是如此强大,它似乎无视任何优化。
最佳答案
显而易见的:
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 进行了编辑。
关于performance - 折叠优化,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4851542/