adding word to Trie data structure

Question

let the Trie data structure and the function to add a string are defined as follows:

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)

The question is about a better algorithm in case the character already does exist in the current level. I'd like to avoid call of mydrop function and reconstruction of the list of children.

Answer 1

First of all you may optimize mydrop function itself in order to stop traversing the list when found the value.

But, IMHO, the only way to optimize the whole add function is to merge lookup and replacing steps into the one traversal.

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

If you use a Map instead of an association list, you can use alter with fromMaybe to provide an empty Trie when the lookup fails:

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 }