[Haskell-cafe] Re: Optimization problem

[apfelmus at quantentunnel.de]

apfelmus at quantentunnel.de wrote:
> type BiMap a b = (Map.Map a b, Map.Map b a)

Actually BiMap is not needed at all, it suffices to have

> splitStreams :: Ord a => [(a,b)] -> [(a,[b])]
> splitStreams xs =
>     takeWhile (not . null . snd) $ toList $ splitStreams' Map.empty xs
>
> splitStreams' :: Ord a => Map.Map a Position -> [(a,b)] -> Imp (a,[b])
> splitStreams' map [] =
>    fmap (const (undefined,[])) $ fromList [1..]
> splitStreams' map ((a,b):xs) =
>    update fun pos $ splitStreams' map' xs
>    where
>    fun ~(_,bs) = (a,b:bs)
>    sz	         = Map.size map
>    pos         = Map.findWithDefault (sz+1) a map
>    map'        =
>       (if Map.member a map then id else Map.insert a (sz+1)) map

Regards,
apfelmus