[Haskell-cafe] What is the best way to preserve the order of a list

Stefan Holdermans stefan at cs.uu.nl
Wed Nov 1 04:29:18 EST 2006


John,

> My question is, how do I preserve the ordering of entities in my  
> list and still be able to assign the proper order values to each  
> entity?  Is there an efficient way to do this?  How else might I  
> improve my orderByPriority algorithm.

Straightforwardly, you could do it like this:

   import List (sortBy)

   type Priority = Int
   type Order    = Int

   order :: [Priority] -> [(Priority, Order)]
   order =  unlabel . sortOnLab . assignOrder . sortOnPrio . label
     where
       label       = zip [0 ..]
       unlabel     = map snd
       sortOnLab   = sortBy (\(l, _) (m, _) -> compare l m)
       sortOnPrio  = sortBy (\(_, p) (_, q) -> compare p q)
       assignOrder = \xs -> zipWith (\(l, p) o -> (l, (p, o))) xs [0 ..]

For instance:

   > order [5, 2, 3, 7]
   [(5,2),(2,0),(3,1),(7,3)]

HTH,

   Stefan


More information about the Haskell-Cafe mailing list