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.