module Trie where

import qualified Data.Map.Monoidal.Strict as Mm
data Trie k m = Trie
  { load :: m, 
    down :: Mm.MonoidalMap k (Trie k m)
  }
  deriving (Eq, Show)

instance (Ord k, Semigroup m) => Semigroup (Trie k m) where
  Trie fi t <> Trie fi' t' = Trie (fi <> fi') (t <> t')

instance (Ord k, Monoid m) => Monoid (Trie k m) where
  mempty = Trie mempty mempty