Question and suggestion: looking at http://hackage.haskell.org/packages/archive/bytestring-trie/0.1.1/doc/html/s... I am questioning your choice of foldr in fromList:
-- | Convert association list into a trie. On key conflict, values -- earlier in the list shadow later ones. fromList :: [(KeyString,a)] -> Trie a fromList = foldr (uncurry insert) empty
-- | /O(1)/, The empty trie. {-# INLINE empty #-} empty :: Trie a empty = Empty
-- | Insert a new key. If the key is already present, overrides the -- old value {-# INLINE insert #-} insert :: KeyString -> a -> Trie a -> Trie a insert = alterBy (\_ x _ -> Just x)
-- | Generic function to alter a trie by one element with a function -- to resolve conflicts (or non-conflicts). alterBy :: (KeyString -> a -> Maybe a -> Maybe a) -> KeyString -> a -> Trie a -> Trie a alterBy f_ q_ x_ | S.null q_ = mergeBy (\x y -> f_ q_ x (Just y)) (singleton q_ x_) | otherwise = go q_ where
-- | /O(1)/, Is the trie empty? {-# INLINE null #-} null :: Trie a -> Bool null Empty = True null _ = False
So it looks like the reduction is fromList - uncurry insert - alterBy - null. Let me use insert in place of uncurry insert: fromList ( (a,1) : ( (b,2) : ( (c,3) : [] ) ) ) (a,1) `insert` ( (b,2) `insert` ( (c,3) `insert` Empty ) ) ) So fromList forces the whole call chain above to be traversed until it hits the Empty. For a large input list this will force the whole list to be allocated before proceeding AND the call chain might overflow the allowed stack size in ghc. For a large trie (which is a likely use case) this is a poor situation. If you use foldl' then the input list is only forced one element at a time. A small change to the lambda that insert passes to adjustBy will retain the same semantics of earlier key wins (which are an especially good idea in the foldl' case). Cheers, Chris