加字特里數據結構

Question

讓特里數據結構，並添加一個字符串的函數定義如下：

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') 

Answer 2

如果使用地圖，而不是一個關聯列表，你可以使用alter與fromMaybe當查找未能提供一個空Trie：

import qualified Data.Map as Map 
import Data.Map (Map) 
import Data.Maybe (fromMaybe) 

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

-- trie returns an "empty" Trie 
trie :: Trie 
trie = Trie { commonness = Nothing, children = Map.empty } 

-- 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 = 
    tree { children = Map.alter (Just . add xs freq . fromMaybe trie) x $ children tree }