I have the following data structure:data XComposeString = XComposeString { keyEvents :: [Event], s :: Result }  deriving (Eq, Show)data XComposeFile = XComposeFile { strings :: [XComposeString] }  deriving (Eq, Show)Where Event and Result just String or some combination of several String.I'm creating a Trie from list of type [(keyEvents x, [s x])]:constructTrie list = M.fromListWith comp list  where    comp = \old new -> old ++ newI want to check on duplicates and prefix overlaps.duplicates :: M.TrieMap Map.Map Event [Result] -> Stringduplicates m = M.showTrie list   where    list = M.filter (\v -> length v /= 1) mprefixOverlap :: M.TrieMap Map.Map Event [Result] -> StringprefixOverlap m = M.showTrie list   where    list = M.filterWithKey (\k v -> not $ null $ catMaybes [M.lookup x m | x <- reverse (inits (init k))]) mHow can I improve this, so, there would be three functions: one to create, one to check on duplicates and one to check on prefix overlaps.Useful imports and types definition:import Data.List(inits)import Data.Maybe(catMaybes)import qualified Data.Map as Mapimport qualified Data.ListTrie.Map as Mtype Event = Stringtype Result = StringAlso, cabal install list-tries is needed for ListTrie data structure.
Improve Trie manipulation in Haskell code
haskell
Can you add minimal imports so your code compiles? I had to guess:import Data.ListTrie.Map as M hiding (null)import qualified Data.Map as Mapimport Data.Maybeimport Data.Listdata Event = Event deriving (Show, Eq, Ord)data Result = Result deriving (Show, Eq)constructTrie can be easily improved by inlining comp:constructTrie list = M.fromListWith (++) listOr even to constructTrie = M.fromListWith (++) but that requires turning off monomorphism restriction or adding an explicit signature for constructTrie, so it's up to your taste.Also you can deduplicate showTrie calls and long trie signatures:mshow list = M.showTrie list type ResultTrie = M.TrieMap Map.Map Event [Result]duplicates :: ResultTrie -> Stringduplicates m = mshow list  where    list = M.filter (\v -> length v /= 1) mprefixOverlap :: ResultTrie -> StringprefixOverlap m = mshow list  where    list = M.filterWithKey (\k v -> not $ null $ catMaybes [M.lookup x m | x <- reverse (inits (init k))]) mNow it's beneficial to inline list variables in both functions:duplicates :: ResultTrie -> Stringduplicates m = mshow $ M.filter (\v -> length v /= 1) mprefixOverlap :: ResultTrie -> StringprefixOverlap m = mshow $ M.filterWithKey (\k v -> not $ null $ catMaybes [M.lookup x m | x <- reverse (inits (init k))]) mNow you can get rid of m in duplicates:duplicates :: ResultTrie -> Stringduplicates = mshow . M.filter (\v -> length v /= 1)In prefixOverlap the line is too long, I can split it. I chose to extract the (\ -> ) construct. Note that m is in more that 1 place so we cannot use ..prefixOverlap :: ResultTrie -> StringprefixOverlap m = mshow $ M.filterWithKey f m where    f k _ = not $ null $ catMaybes [M.lookup x m | x <- reverse (inits (init k))]Now remove extra parentheses in the comprehension:prefixOverlap :: ResultTrie -> StringprefixOverlap m = mshow $ M.filterWithKey f m where    f k _ = not $ null $ catMaybes [M.lookup x m | x <- reverse $ inits $ init k]From here I'll only work on f. Now a trickier part. Long chains of $ are equivalent to . following one $ in the end:    f k _ = (not . null . catMaybes) [M.lookup x m | x <- reverse $ inits $ init k]not . null . catMaybes is a function of [Maybe a] -> Bool that returns True only if there is any Just in the list. I can literally translate this sentence into Haskell: it's just any isJust:    f k _ = any isJust [M.lookup x m | x <- reverse $ inits $ init k]Now even trickier: your comprehension is just a map:    f k _ = any isJust $ map (\x -> M.lookup x m) $ reverse $ inits $ init kCongratulations, we can again turn a chain of $ into a chain of .:    f k _ = any isJust . map (\x -> M.lookup x m) . reverse . inits . init $ kNow remember that . is associative so you can put parentheses in the middle of the chain wherever you want:any isJust . (map (\x -> M.lookup x m) . reverse) . inits . initNow we have map something . reverse. And it doesn't matter when you reverse - before or after map:map something f . reverse = reverse . map somethingThat is, map and reverse commute and we can swap them and remove parens:any isJust . reverse . map (\x -> M.lookup x m) . inits . initNow we can put around any and reverse. It's clear that any works the same way for straight and reversed lists, that is, any something . reverse = any something, so we can throw reverse away:any isJust . map (\x -> M.lookup x m) . inits . initAnd put back into prefixOverlap:prefixOverlap :: ResultTrie -> StringprefixOverlap m = mshow $ M.filterWithKey f m where    f k _ = any isJust . map (\x -> M.lookup x m) . inits . init $ kHere is the full version of the code:import Data.ListTrie.Map as M hiding (null, map)import qualified Data.Map as Mapimport Data.Maybeimport Data.Listtype Event = Chartype Result = ()type ResultTrie = M.TrieMap Map.Map Event [Result]data XComposeString = XComposeString { keyEvents :: [Event], s :: Result }  deriving (Eq, Show)data XComposeFile = XComposeFile { strings :: [XComposeString] }  deriving (Eq, Show)constructTrie list = M.fromListWith (++) listmshow :: ResultTrie -> Stringmshow list = M.showTrie list duplicates :: ResultTrie -> Stringduplicates = mshow . M.filter (\v -> length v /= 1)prefixOverlap :: ResultTrie -> StringprefixOverlap m = mshow $ M.filterWithKey f m where    f k _ = any isJust . map (\x -> M.lookup x m) . inits . init $ kNote that I used fake Event and Result types. I also checked that old and new prefixOverlap are the same using QuickCheck and smallcheck libraries:prefixOverlapOld :: ResultTrie -> StringprefixOverlapOld m = M.showTrie list   where    list = M.filterWithKey (\k v -> not $ null $ catMaybes [M.lookup x m | x <- reverse (inits (init k))]) mprop_foo x = prefixOverlap m == prefixOverlapOld m where    m = M.fromList $ map (first (++ X)) xfirst is from Control.Arrow.The prefixOverlap probably can still be improved with using lookupPrefix and/or children functions from Data.ListTrie.Map.Here is my take:prefixOverlapNew :: ResultTrie -> StringprefixOverlapNew = mshow . M.unions . map (\(p,m) -> M.addPrefix [p] m) . Prelude.filter (\(p, m) -> M.size m /= 1 || (null $ fst $ head $ M.toList m)) . Map.toList . M.children1Note that it differs from both original prefixOverlapOld and refactored prefixOverlap:QuickCheck found that they differ on a map with 2 keys fo and f. The prefixOverlapNew  version correctly shows both fo and f as they overlap. The original version(s) show only value on fo key which is dubuios.Here is an improved version using list comprehension to combine filter and map:prefixOverlapNew :: ResultTrie -> StringprefixOvelapNew mm = mshow $     M.unions [M.addPrefix [p] m | (p, m) <- Map.toList $ M.children1 mm,  M.size m /= 1 || null (fst $ head $ M.toList m)]Moved f out:prefixOverlapNew mm = mshow $ M.unions [M.addPrefix [p] m | (p, m) <- Map.toList $ M.children1 mm, f m] where        f m =  M.size m /= 1 || null (fst $ head $ M.toList m)Finally, a version in list monad, just for fun:prefixOverlapNew :: ResultTrie -> StringprefixOverlapNew mm = mshow $ M.unions $ do        (p, m) <- Map.toList $ M.children1 mm        guard $ M.size m /= 1 || null (fst $ head $ M.toList m)        return $ M.addPrefix [p] mguard is from Control.Monad.