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
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@haskell.org
http://www.haskell.org/mailman/listinfo/beginners