После написания этой статьи я решил поместить свои деньги туда, где есть мой рот, и начал конвертировать предыдущий мой проект, чтобы использовать recursion-schemes
.
Структура данных, о которой идет речь, представляет собой lazy kdtree. Пожалуйста, ознакомьтесь с реализациями с явным и неявным рекурсией.
Это в основном простое преобразование по строкам:
data KDTree v a = Node a (Node v a) (Node v a) | Leaf v a
to
data KDTreeF v a f = NodeF a f f | Leaf v a
Теперь, сравнив весь shebang, я обнаружил, что версия KDTreeF
примерно в два раза медленнее, чем обычная версия (найти весь пробег здесь).
Является ли это просто дополнительной оберткой Fix
, которая замедляет меня здесь? И есть ли что-нибудь, что я мог бы сделать против этого?
Предостережение:
- На данный момент это специализируется на (V3 Double).
- Это приложение для метаморфизма. Гиломорфизм не подходит для 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 указывает на то, что промежуточные структуры данных полностью не удаляются, и неудивительно, что линейные поисковые запросы доминируют сейчас, KDTreeF
теперь немного быстрее, чем KDTree
s. Не важно, хотя.