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

[KC]

Sometimes one wants duplicate keys.

Perhaps findkey might be better.

--
--

Sent from an expensive device which will be obsolete in a few months! :D

Casey

On Aug 15, 2014 5:15 PM, "Dimitri DeFigueiredo" <defigueiredo at ucdavis.edu>
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? **
> 2) Is there a simpler fix?
>
>
> Cheers,
>
>
> Dimitri
>
>
>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20140815/d8726451/attachment.html>