[Haskell-cafe] Implementing ParseChart with Data.Map

[Adrian Hey]

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