Три функции Haskell - Вставка значений и поиск - PullRequest
Новая
       36

Три функции Haskell - Вставка значений и поиск

0 голосов
/ 04 ноября 2011

Тип дерева 

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"]

1 Ответ

2 голосов
/ 04 ноября 2011

Если вы не ищите помощи в выполнении домашних заданий, существует множество различных вариантов попыток взлома:

http://hackage.haskell.org/packages/archive/pkg-list.html (найдите здесь "trie")

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

Общий совет - начать разработку сверху вниз, используя 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 разработайте новых детей как-нибудь и так далее

...