haskell - 将单词添加到 Trie 数据结构

Question

让Trie数据结构和添加字符串的函数定义如下:

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

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


-- Add inserts a word to a Trie with a given frequency
-- stored after the last character
add :: String -> Int -> Trie -> Trie
add [] freq tree = tree { commonness = Just freq }
add (x:xs) freq tree = case lookup x (children tree) of
                        Nothing -> tree { children = (x, add xs freq trie):(children tree) }
                        Just subtree -> tree { children = (x, add xs freq subtree):(mydrop x (children tree)) }
                        where
                            mydrop :: Char -> [(Char, Trie)] -> [(Char, Trie)]
                            mydrop _ [] = []
                            mydrop elm (x:xs)
                                | (fst x) == elm = mydrop elm xs
                                | otherwise = x:(mydrop elm xs)

问题是关于一个更好的算法，以防该角色已经存在于当前关卡中。我想避免调用 mydrop 函数和重建子列表。

Answer 1

首先，您可以优化 mydrop 函数本身，以便在找到值时停止遍历列表。

但是，恕我直言，优化整个 add 函数的唯一方法是将 lookup 和替换步骤合并到一次遍历中。

add' :: String -> Int -> Trie -> Trie
add' [] freq tree = tree { commonness = Just freq }
add' (x:xs) freq tree =
    traverse x (children tree) []
    where
        traverse x [] ts' = tree { children = (x, add' xs freq trie) : ts' }
        traverse x (t:ts) ts' | fst t == x = tree { children = (x, add' xs freq $ snd t) : (ts ++ ts') }
                              | otherwise = traverse x ts (t:ts')