Мне нужна была общая реализация Trie на Haskell, но я не смог ее найти.
Мне были реализованы мои собственные функции (здесь только ключи, мне не нужны данные по Trie), но я хочу найти хорошая реализация Trie в Haskell для будущего использования (я новичок в haskeller).
Я нашел Data.Trie, но ключи ByteString.
Является ли Data.Trie правильным вариантом? (и то я не знаю, как его использовать)
Спасибо!!! :D
Перенесено из комментария по просьбе...
Единственная очень общая реализация trie, о которой я знаю, это пакет list-tries . Мне всегда казалось, что это немного перегружено, но «слишком сложный» для одного человека является «полнофункциональным» для другого, поэтому, если это соответствует вашим целям, дерзайте. Кроме того, пакет активно поддерживается, и это хорошо.
Да, и, поскольку в пакете нигде это явно не указано, я мог видеть: версия «Patricia trie» — это trie, который сжимает последовательности узлов с одной ветвью в один узел, хранящий префикс общего ключа. Таким образом, для ключей «aabb» и «aabc» вы получите узел с «aab», а затем ответвления «b» и «c». Стандартное дерево всегда разветвляется по одному элементу за раз.
Ознакомьтесь с пакетом MemoTrie на Hackage и на GitHub. Справочную информацию о простой и красивой теории, лежащей в основе, см. на странице мемоизации вики Haskell, включая две статьи Ральфа Хинце, одну мной и некоторыми сообщениями в блогах.
Другой пакет trie/memoization — functor-combo, также на Hackage и на GitHub. Этот пакет воплощает в себе реализацию идей, описанных в разделе Элегантное запоминание с использованием типов высшего порядка< /em> и другие записи блога.
Некоторые другие связанные пакеты:
memo = untrie . trie. Первая фаза (trie) преобразует функцию в дерево, а вторая фаза преобразует это дерево обратно в функцию. Если все, что вам нужно, это запоминание, вы можете обращаться с memo как с черным ящиком. Если вы хотите больше проверить и преобразовать сами данные, просто заступитесь после trie и перед untrie. Эти древовидные структуры всегда находятся в Functor, Applicative, Foldable, Traversable и Monad, поэтому сразу же доступно множество функций для работы с ними.
- person Conal; 19.04.2013
http://hackage.haskell.org/package/TrieMap — часть моей работы в день. Мне не совсем понятно, что вы подразумеваете под «общим», но TrieMap поддерживает более или менее произвольные (даже рекурсивные!) алгебраические типы данных, например бинарные деревья, как тройные ключи.
Data.IntMapиData.IntSet— это попытки с ключамиInt. - person C. A. McCann schedule 18.04.2013Data.IntMapобрабатываетIntкак последовательность битов. Возможность сортировать или индексировать непосредственно каждый фрагмент — это хорошо, но достаточно списка вещей, которые вы можете сравнить на равенство. В любом случае, есть пакетlist-tries, но он всегда казался мне немного запутанным. - person C. A. McCann schedule 18.04.2013MemoTrie, но для конкретной цели запоминания. - person kosmikus schedule 18.04.2013