Ана-/ Катаморфизмы только медленнее?

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

Теперь после бенчмаркинга всего Шебанга я обнаружил, что KDTreeF версия примерно в два раза медленнее, чем обычная версия (здесь можно найти весь прогон).

Это просто дополнительный Fix фантик, который меня здесь тормозит? И могу ли я что-нибудь сделать против этого?

Предостережения:

• На данный момент это специализируется на (V3 Double).
• Это данные после применения анаморфизма. Гиломорфизм не подходит для kdtrees.
• я использую cata (fmap foo algebra) несколько раз. Это хорошая практика?
• Я использую Эдвардс recursion-schemes пакет.

Изменить 1:

Это связано? https://ghc.haskell.org/trac/ghc/wiki/NewtypeWrappers Is newtype Fix f = Fix (f (Fix f)) не бесплатно"?

Изменить 2:

Просто сделал еще кучу тестов. На этот раз я проверил конструкцию дерева и деконструкцию. Тест здесь: https://dl.dropboxusercontent.com/u/2359191/2014-05-15-kdtree-bench-03.html

Хотя вывод Core указывает на то, что промежуточные структуры данных не удаляются полностью, и неудивительно, что в настоящее время доминируют линейные поиски, KDTreeFтеперь немного быстрее, чем KDTrees. Не имеет большого значения, хотя.

Answer 1

Я только что реализовал Thing + ThingF + Base instance вариант дерева. И угадайте, что... это удивительно быстро.

У меня сложилось впечатление, что этот вариант будет самым медленным из всех вариантов. Я действительно должен был прочитать мой собственный пост... строку, где я пишу:

нет никакого следа структуры TreeF, которая будет найдена

Пусть числа говорят сами за себя, kdtreeu это новый вариант. Результаты не всегда такие же четкие, как в этих случаях, но в большинстве случаев они, по крайней мере, так же быстры, как и явная рекурсия (kdtree в бенчмарке).

Answer 2

Я использовал не схемы рекурсии, а собственные "свернутые вручную" cata, ana, Fix/unFix для генерации (списков) и оценки программ на небольшом языке в надежде найти такую, которая соответствует списку. из (входных, выходных) пар.

По моему опыту, cata оптимизировалась лучше, чем прямая рекурсия, и дала прирост скорости. Также IME, предотвращал ошибки переполнения стека, которые вызывал мой наивный генератор, но это было связано с генерацией окончательного списка.

Итак, мой ответ: нет, они не всегда медленнее, но я не вижу очевидных проблем; поэтому они могут просто быть медленнее в вашем случае. Также возможно, что сама схема рекурсии просто не оптимизирована по скорости.