Hello Krasimir,
Krasimir Angelov wrote:
Hi,
I have to write ParseChart implementation with Data.Map/Set. The chart
is type like this:
type Chart k v = Map k (Set v)
now I need operation like:
insert :: k -> v -> Chart k v -> Maybe (Chart k v)
where the result is (Just _) if the (k,v) is actually added to the
chart or Nothing if it was already there and nothing have to be done.
The straight forward implementation is:
case Map.lookup k chart of
Nothing -> Just (Map.insert k (Set.singleton v) chart)
Just set | Set.member v set -> Nothing
| otherwise -> Just (Map.insert k
(Set.insert v set) chart)
You can do this quite easily with the AVL library, something like this
(untested code)
import Data.Cordering
import Data.Tree.AVL
type Chart k v = AVL (k, AVL v)
insert :: (Ord k, Ord v) => k -> v -> Chart k v -> Maybe (Chart k v)
insert k v tk =
case genOpenPathWith cmpk tk of
EmptyBP pthk -> Just $! insertPath pthk (k, singleton v) tk
FullBP pthk tv ->
case genOpenPath (compare v) tv of
EmptyBP pthv -> let tv' = insertPath pthv v tv
in tv' `seq` (Just $! writePath pthk (k, tv') tk)
FullBP _ _ -> Nothing
where cmpk (k',tv) = case compare k k' of
LT -> Lt
EQ -> Eq tv
GT -> Gt
..or something like that (maybe you don't want all that strictness)
The insertPath & writePath functions do involve a second traversal
but do not repeat all the comparisons. Also, provided not too much
has happened in between, they should be very fast as the nodes on
the path are probably still in cache. The important thing is that
in the case where Nothing is returned you'll have burned very little
heap.
Regards
--
Adrian Hey
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
