Ana/Catamorphisms只是慢一点吗？

Question

写完这篇文章之后,我决定将我的钱放在我的嘴边,并开始转换我以前使用的项目recursion-schemes.

有问题的数据结构是一个懒惰的kdtree.请查看具有显式和隐式递归的实现.

这主要是一种简单的转换:

data KDTree v a = Node a (Node v a) (Node v a) | Leaf v a

至

data KDTreeF v a f = NodeF a f f | Leaf v a

现在对整个shebang进行基准测试后,我发现该KDTreeF版本比普通版本慢了两倍(在这里找到整个版本).

这只是额外的Fix包装,让我放慢了速度吗？有什么我可以做的吗？

注意事项:

• 目前这是专门为(V3双).
• 这是在变形应用之后的cata-.Hylomorphism不适合kdtrees.
• 我用cata (fmap foo algebra)了好几次.这是好习惯吗？
• 我使用Edwards recursion-schemes包.

编辑1:

这有关系吗？https://ghc.haskell.org/trac/ghc/wiki/NewtypeWrappers 是newtype Fix f = Fix (f (Fix f))不是"免费"？

编辑2:

刚做了另一堆基准测试.这次我测试了树木的构造和解构.基准测试:https://dl.dropboxusercontent.com/u/2359191/2014-05-15-kdtree-bench-03.html

虽然Core输出表明中间数据结构没有被完全删除,但现在线性搜索占主导地位并不奇怪,现在KDTreeFs略快于KDTrees.虽然没关系.

Answer 1

我刚刚实现Thing + ThingF + Base instance了树的变体.猜猜看......这个速度非常快.

我的印象是这一个是所有变种中最慢的.我真的应该读自己的帖子...我写的行:

没有找到TreeF结构的痕迹

让数字说明一下,kdtreeu是新变种.结果并不总是像这些情况一样清晰,但在大多数情况下,它们至少与显式递归一样快(kdtree在基准测试中).