Question and suggestion:
looking at
http://hackage.haskell.org/packages/archive/bytestring-trie/0.1.1/doc/html/src/Data-Trie.html#Trie
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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
