[Haskell-cafe] Re: Optimization problem

apfelmus@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