Here's a toy implementation of a 'Trie' so that I can get a feel for Free monads (not that this is a monad; maybe I should explore using MonadPlus instead of the Monoid constraint?).

Trie-Free-Monad.hs

{-#LANGUAGE GADTs, StandaloneDeriving #-}                                          
                                                                                   
module Trie                                                                        
  ( Trie                                                                           
  , emptyTrie                                                                      
  , trieIsEmpty                                                                    
  , trieFromList                                                                   
  , trieFromLists                                                                  
  , joinTries                                                                      
  , trieToLists                                                                    
  , suffixesOf                                                                     
  , main ) where                                                                   
                                                                                   
import Control.Applicative ((<$>), (<*>), pure)                                    
import Control.Monad (liftM)                                                       
import Control.Monad.Free (Free(..))                                               
import Data.Foldable (foldMap)                                                     
import Data.Map as M (empty, fromList, lookup, Map, null, singleton, toList, unionWith)
import Data.Maybe (fromJust)                                                       
import Data.Monoid ((<>))                                                          
                                                                                   
-- | Here's a toy implementation of a 'Trie' so that I can get a feel for          
-- @Free@ monads.                                                                  
newtype Trie k = Trie { unTrie :: Free (Map k) (Maybe (Trie k)) }                  
                                                                                   
deriving instance Show k => Show (Trie k)                                          
                                                                                   
-- | Construct an empty 'Trie'.                                                    
emptyTrie :: Trie k                                                                
emptyTrie = Trie $ Impure M.empty                                                  
                                                                                   
-- | Test to see if a 'Trie' is empty.                                             
trieIsEmpty :: Trie k -> Bool                                                      
trieIsEmpty (Trie (Impure m)) = M.null m                                           
trieIsEmpty _ = False                                                              
                                                                                   
-- | Construct a 'Trie' from a list.                                               
trieFromList :: [k] -> Trie k
trieFromList ks = Trie $ go ks                                                  
  where go [] = Pure (Nothing)                                                  
        go (k:ks) = Impure . singleton k $ go ks                                
                                                                                
-- | Construct a 'Trie' from a list of lists (of @Ord@erable values).           
trieFromLists :: Ord k => [[k]] -> Trie k                                       
trieFromLists [] = emptyTrie                                                    
trieFromLists (ks:kss)                                                          
  = foldr (\a b -> b `joinTries` trieFromList a) (trieFromList ks) kss          
                                                                                
-- | Join two 'Trie's.                                                          
joinTries :: Ord k => Trie k -> Trie k -> Trie k                                
joinTries l r = Trie $ go (unTrie l) (unTrie r)                                 
  where go (Pure Nothing) (Pure Nothing) = Pure Nothing                         
        go l (Pure Nothing) = Pure . Just $ Trie l                              
        go (Pure Nothing) r = Pure . Just $ Trie r                              
        go l (Pure (Just r)) = Pure . Just $ joinTries (Trie l) r               
        go (Pure (Just l)) r = Pure . Just $ joinTries l (Trie r)               
        go (Impure l) (Impure r) = Impure $ unionWith go l r                    
                                                                                
-- | Deconstruct a 'Trie' into a list of lists.                                 
trieToLists :: Trie k -> [[k]]                                                  
trieToLists (Trie (Pure Nothing)) = [[]]                                        
trieToLists (Trie (Pure (Just t))) = [] : trieToLists t                         
trieToLists (Trie f)                                                            
    = foldr (\(k, t) kss -> kss ++ (map ((:) k) $ trieToLists t)) [] $ go f     
  where go (Pure p) = foldMap (go . unTrie) p                                   
        go (Impure m) = map (fmap Trie) $ toList m                              
                                                                                
-- | Check if a list (of @Ord@erable values) is an element of a 'Trie'.         
elemOfTrie :: Ord k => [k] -> Trie k -> Bool                                    
elemOfTrie [] (Trie (Pure _)) = True                                            
elemOfTrie [] (Trie (Impure _)) = False                                         
elemOfTrie ks (Trie (Pure Nothing)) = False                                     
elemOfTrie ks (Trie (Pure (Just l))) = elemOfTrie ks l                          
elemOfTrie (k:ks) (Trie (Impure m)) =                                           
  case M.lookup k m of                                                          
    Nothing -> False
    Just t -> elemOfTrie ks $ Trie t                                            
                                                                                
-- | Returns a 'Trie' containing all suffixes of the given list (of             
-- @Ord@erable values) in the original 'Trie'.                                  
suffixesOf :: Ord k => [k] -> Trie k -> Maybe (Trie k)                          
suffixesOf [] (Trie (Pure l)) = l                                               
suffixesOf [] t = Just $ t                                                      
suffixesOf ks (Trie (Pure l)) = l >>= suffixesOf ks                             
suffixesOf (k:ks) (Trie (Impure m)) = M.lookup k m >>= (suffixesOf ks . Trie)   
                                                                                
-- | Test application.                                                          
main :: IO ()                                                                   
main = print $ trieToLists <$>                                                  
  (suffixesOf "Hell" $ trieFromLists ["Jazz", "Help", "Hello", "Hellish"])