[Haskell-beginners] Disappointing thought on Haskell -- a simple space leak on "insert" is hard bug to catch

[Dimitri DeFigueiredo]

Here's a problem I just found with Haskell (and maybe functional 
programming)
that I would like to know how to avoid.

Please don't get me wrong. I'm in *LUUV* with Haskell! :-)


Exercise 2.3 of Chris Okasaki's book "Purely Functional Data Structures" 
shows that
something as simple as an insert function in a binary tree can cause a space
leak in Haskell. (and other functional languages as well)

Here's a simple tree type:

data Tree a = Empty
             | MkTree (Tree a) a (Tree a)

Here's the version of insert with the space leak:

-- ** SPACE LEAK! ** version
-- this version unnecessarily copies the path to the inserted element 
even if
-- the same element is already present in the tree.
-- a million insertions of the same element will cause a million trees
-- to exist whereone would suffice.

treeInsert :: Ord a => a -> Tree a -> Tree a
treeInsert e Empty = MkTree Empty e Empty
treeInsert e t@(MkTree a x b) | e > x     = MkTree a x (treeInsert e b)
                               | e < x     = MkTree (treeInsert e a) x b
                               | otherwise = t

Here's a version without the space leak:

treeInsert :: Ord a => a -> Tree a -> Tree a
treeInsert e t = case (treeInsert' e t) of
                     Nothing -> t
                     Just x  -> x
     where
         treeInsert' :: Ord a => a -> Tree a -> Maybe (Tree a)
         treeInsert' e Empty = return $ MkTree Empty e Empty
         treeInsert' e (MkTree a x b) | e > x     = do {r <- treeInsert' 
e b; return $ MkTree a x r}
                                      | e < x     = do {r <- treeInsert' 
e a; return $ MkTree r x b}
                                      | otherwise = Nothing


This is so tricky that I think it is worth questioning whether Haskell 
is helping here.
First, just spotting that the first version leads to a space leak is not 
trivial. Second, the fix
is so much uglier than the original version. It is disappointing to have 
to write it!

Questions:
1) ** Is there a warning sign that would easily flag this space leak? **
2) Is there a simpler fix?


Cheers,


Dimitri