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

[Mateusz Kowalczyk]

On 08/16/2014 01:15 AM, Dimitri DeFigueiredo wrote:
> 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? **

Benchmarking and profiling.

> 2) Is there a simpler fix?

I don't know.

> 
> Cheers,
> 
> 
> Dimitri
> 


-- 
Mateusz K.