Haskell TRIE функции - Установка значений и поиск

Question

Типом является синтаксического дерева

data Trie a = TrieNode (Maybe a) [(Char, Trie a)] 
deriving Show 

Я хочу, чтобы написать функцию, которая принимает в паре ключ-значение и приставкой синтаксического дерева. Затем я хочу, чтобы она вернула таблицу символов, в которую включена пара ключ-значение. Если ключ уже существует, новое значение должно заменить старое.

Пример:

trieInsert ("abc",10) emptyTrie == 
    TrieNode Nothing [ 
     ('a', TrieNode Nothing [ 
      ('b', TrieNode Nothing [ 
       ('c', TrieNode (Just 10) [])])])] 

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

findTrie "c" oneTrie -> ["at","in"] 
findTrie "ca" oneTrie -> ["z","r"] 

Answer 1

Если вы не ищете помощь в выполнении домашних заданий, есть много различных реализаций примеряет hackage:

http://hackage.haskell.org/packages/archive/pkg-list.html (поиск «синтаксического дерева» там)

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

Общий наконечник должен начать сверху-вниз разработки с использованием where, деконструкции аргументов и положить undefined вместо того, чтобы еще недоразвитые части:

Шаг 1:

trieInsert (keyH : keyT) value (TrieNode oldValue oldChars) = undefined 

Шаг 2:

Затем подумайте о самых простых «базовых» случаях:

trieInsert [] value (TrieNode _ oldChildren) = TrieNode (Just value) oldChildren 
trieInsert (keyH : keyT) value (TrieNode oldValue oldChars) = undefined 

В этом примере первая строка гласит: «Если мы добавим пустой ключ, тогда значение должно быть заменено в корне, а дочерние узлы должны быть оставлены так, как они есть». Вторая строка гласит: «если мы добавим непустой ключ, а затем ...»

Шаг 3:

trieInsert [] value (TrieNode _ oldChildren) = TrieNode (Just value) oldChildren 
trieInsert (keyH : keyT) value (TrieNode oldValue oldChars) = TrieNode oldValue newChildren where 
    newChildren = undefined 

второй линии теперь гласит: «если мы добавим непустой ключ, то мы оставляем oldValue как есть и каким-то образом модифицируем детей ».

Затем на этапе 4 разрабатывают новые дети как-то и так далее