tries are monoids

trie-monoid.hs

import qualified Data.Map as M

newtype Trie c = Trie { getTrie :: M.Map c (Trie c) }
    deriving (Show)

type Word c = [c]

instance Ord c => Monoid (Trie c) where
    mempty                       = Trie M.empty
    (Trie t) `mappend` (Trie t') = Trie $ M.unionWith mappend t t'

fromWord :: Ord c => Word c -> Trie c
fromWord = foldr (\c t -> Trie $ M.singleton c t) mempty

fromWords :: Ord c => [Word c] -> Trie c
fromWords = foldMap fromWord