Как удалить слово из структуры Trie?

Question

Возможно я не достаточно умен, чтобы изучать Хаскелл, но я бы дал ему последний шанс. Я застрял в реализации удаления записи из дерева, структура, похожая на Trie, чтобы быть более конкретной ( http://en.wikipedia.org/wiki/Trie).

Я ищу любые советы (не решение!), Как реализовать такую ​​чистую функцию. У меня была идея об одном алгоритме. Воссоздайте новое дерево, пройдя по всему дереву "пропуская" значения, равные каждому символу слова, при условии, что ребро возвращает исходное дерево, если следующий символ не будет найден. Но возникает проблема, когда персонаж также принадлежит другому слову.

data Trie = Trie { commonness :: Maybe Int
                 , children :: [(Char, Trie)]
                 } deriving (Eq, Read, Show)

-- Creates an empty "dictionary"
trie :: Trie
trie = Trie { commonness = Nothing, children = [] }

-- Inserts a word with given commonness into dictionary
add :: String -> Int -> Trie -> Trie
add [] freq tree
    | (0 <= freq) && (freq <= 16) = tree { commonness = Just freq }
    | otherwise = error $ "Commonness out of bounds: " ++ (show freq)
add word freq tree = tree { children = traverse word (children tree) }
    where
        traverse [] tree = error $ "traverse called with [] " ++ (show tree)
        traverse (x:xs) [] = [(x, add xs freq trie)]
        traverse str@(x:xs) (t:ts)
            | x == fst t = (x, add xs freq $ snd t):ts
            | otherwise = t:(traverse str ts)

remove :: String -> Trie -> Trie
???

И данные выглядят так:

GHCi> putStrLn $ groom $ add "learn" 16 $ add "leap" 5 $ add "sing" 7 $ add "lift" 10 trie

Trie{commonness = Nothing,
     children =
       [('l',
         Trie{commonness = Nothing,
              children =
                [('i',
                  Trie{commonness = Nothing,
                       children =
                         [('f',
                           Trie{commonness = Nothing,
                                children = [('t', Trie{commonness = Just 10, children = []})]})]}),
                 ('e',
                  Trie{commonness = Nothing,
                       children =
                         [('a',
                           Trie{commonness = Nothing,
                                children =
                                  [('p', Trie{commonness = Just 5, children = []}),
                                   ('r',
                                    Trie{commonness = Nothing,
                                         children =
                                           [('n',
                                             Trie{commonness = Just 16, children = []})]})]})]})]}),
        ('s',
         Trie{commonness = Nothing,
              children =
                [('i',
                  Trie{commonness = Nothing,
                       children =
                         [('n',
                           Trie{commonness = Nothing,
                                children =
                                  [('g', Trie{commonness = Just 7, children = []})]})]})]})]}

Answer 1

Это будет проще, если вы используете Map Char Trie вместо [(Char,Trie)] для вашего детского стола. Вот что я собираюсь предположить для этого ответа. Я начну с индуктивного случая:

import qualified Data.Map as Map

remove :: String -> Trie -> Trie
remove (c:cs) t = t { children = Map.alter remove' c (children t) }
    where
    remove' (Just t) = Just (remove cs t)
    remove' Nothing = Nothing
remove [] t = ...

Я оставлю базовый случай для вас. Вот документы для Map Я использовал функцию, изменить. Вы можете получить это же решение без использования Map если вы реализовали alter за [(Char,a)],

Упражнение: remove' довольно многословно Посмотрите, можете ли вы сократить его, используя fmap,

Answer 2

В Python вы можете сделать что-то вроде этого

def remove_string_helper(self, string, pnode, index):
    if pnode:
        flag = False
        if index < len(string):
            flag = self.remove_string_helper(string, pnode.childs.get(string[index]), index + 1)

        if index == len(string) and pnode.is_complete_word:
            pnode.is_complete_word = False
            return len(pnode.childs) == 0

        if flag:
            pnode.childs.pop(string[index])
            return len(self.childs) == 0

    return False

def remove_string(self, string):
    self.remove_string_helper(string, self.childs.get(string[0]), 1)