1

也许我不够聪明，无法学习 Haskell，但我会给它最后一次机会。我一直坚持从树中删除条目的实现，像 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 = []})]})]})]})]}
4

2 回答 2

4

如果您使用 aMap 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这是我使用的函数的文档， alter。如果Map您alter为[(Char,a)].

练习： remove'很罗嗦。看看你能不能用fmap.

于 2011-04-03T21:25:53.703 回答
0

在 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)
于 2018-09-23T08:47:50.387 回答