Мне нужна была общая реализация Trie в Haskell, но я не смог найти ее.Общая реализация Trie Haskell
Я был реализован my own functions (только ключи здесь, мне не нужны данные на Trie), но я хочу найти хорошую реализацию Trie в Haskell для будущего использования (я новичок в kokkeller).
Я был найден Data.Trie, но ключи ByteString.
Is Data.Trie правильный вариант? (а затем я не знаю, как его использовать)
Спасибо !!! : D
Переехал от комментариев по запросу ...
только очень общее внедрение Trie я знаю с верхней части моей головы the list-tries package. Меня всегда поразило немного переутомления, но «слишком сложный» один человек - это «полнофункциональный» человек, поэтому, если он подходит вашим целям, заходите на него. Кроме того, пакет, как представляется, активно поддерживается, что хорошо.
О, и поскольку пакет не указал это явно нигде, я мог видеть: версия «Патрисия три» - это три, которая сжимает последовательности узлов с одной ветвью в один узел, который хранит общий префикс ключа. Поэтому для ключей «aabb» и «aabc» вы получите узел с «aab», а затем ветки «b» и «c». Стандартное trie всегда включает один элемент за раз.
Ознакомьтесь с пакетом MemoTrie on Hackage и on GitHub. Для фона на простой & красивая теория, см. Haskell wiki page on memoization, в том числе две работы Ральфа Хинзе, один из меня, и some blog posts.
Еще один пакет trie/memoization - functor-combo, также on Hackage и on GitHub. Этот пакет воплощает реализации идей, описанных в Elegant memoization with higher-order types и других блогах.
Некоторые другие связанные пакеты:
Спасибо, Конал, но я не могу сопоставить свой ответ с моим вопросом (по моей вине, я уверен). Интуитивно я не могу понять, как я могу проверять (внутри) мемуаризованную структуру, с другой стороны, используя trie, я могу проверить эту структуру для создания новой информации (мемонирование выполняется как черный ящик). Я читаю ваше сообщение frecuently, но слишком тяжело (как магия) для меня: D: D Спасибо, в любом случае !!!! – josejuan
@josejuan: «меморированная структура» * это * trie. Воспоминание - это состав двух фаз: 'memo = untrie. trie'. Первая фаза ('trie') преобразует функцию в trie, а вторая фаза преобразует ее обратно в функцию. Если все, что вам нужно, это memoization, вы можете обрабатывать 'memo' как черный ящик. Если вы хотите больше проверить и преобразовать сами данные, просто заступитесь после 'trie' и до' untrie'. Эти три структуры всегда находятся в «Functor», «Applicative», «Foldable», «Traversable» и «Monad», поэтому для работы на них существует много функциональных возможностей. – Conal
http://hackage.haskell.org/package/TrieMap была часть моей работы обратно в тот же день. Мне не совсем понятно, что вы означает «generic», но TrieMap поддерживает более или менее произвольные (рекурсивные, даже!) Алгебраические типы данных, например. бинарные деревья, как ключи trie.
Очень интересно, спасибо! list-try напрямую используется и как «generic trie» может использоваться из любой другой структуры (например, дерево является проходящим/секвентивным, тогда вы можете использовать его со списками-попытками, а другое - преобразовать IntTrie в список -trie [бит]), но ваша реализация делает это явно! (Я видел ваш пакет, но я не понимал), я буду использовать в будущем, конечно! : D Спасибо! – josejuan
Невозможно написать три, которые работают с произвольными ключевыми типами. Какие ключи вы хотите использовать? Обратите внимание, что 'Data.IntMap' и' Data.IntSet' ставятся с клавишами 'Int'. –
C.A. McCann, Trie требуется только тип поддержки оператора Equality над последовательными исходными данными. С этим вы можете построить Trie. Что имеет значение, если вы не знаете базовый тип ?. Разве моя реализация не является Trie? Спасибо! (Но предположим, что тип ключа [a]) – josejuan
Правильно, вам нужны ключи, чтобы быть какой-то последовательностью или чем-то, что вы можете превратить в последовательность. Например, 'Data.IntMap' обрабатывает' Int' как последовательность бит. Уметь сортировать или индексировать непосредственно на каждом куске приятно, но список вещей, которые вы можете сравнить для равенства, достаточно. Во всяком случае, есть [пакет 'list-try' там] (http://hackage.haskell.org/package/list-tries), но он всегда казался мне немного запутанным. –