[Haskell] stack overflow - nonobvious thunks?

Adrian Hey ahey at iee.org
Thu Jul 28 20:16:31 EDT 2005

On Wednesday 27 Jul 2005 10:19 pm, Scherrer, Chad wrote:
> Adrian, Does your AVL library have an "insertWith'"-type function
> mentioned by Udo?

I haven't followed this too closely, but I did try to ensure that
Data.Tree.AVL provides all the strictness control users will need
in practice.

Basically all functions operating on AVL type itself behave as if
it was strict in left and right subtrees, though this is done via
explicit seqs in the code, not using ! in the type definition
(which seems to slow things down). As for the tree elements, this
is user controllable in two ways..

1- Provision of distinct strict and non-strict versions of functions
   eg. mapAVL (non-strict) vs. mapAVL' (strict)
2- By users controlling the strictness in any combining comparisons
   they define.

For example..
insertWith' :: Ord k => (a -> a -> a) -> k -> a -> AVL (k,a) -> AVL (k,a)
insertWith' f k a avl = genPush ccmp (k,a) avl
 where ccmp (k',a') = case compare k k' of
                      LT -> Lt
                      EQ -> let a'' = f a a' in a'' `seq` Eq (k',a'')
                      GT -> Gt

Of course the above code does not guarantee strictness in the value
argument (a). It just guarantees that a'' is evaluated in the event
that a matching key is already present.

Adrian Hey

More information about the Haskell mailing list