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

John Ky newhoggy at gmail.com
Wed Nov 1 03:35:35 EST 2006


Hi,

I have a list of entities.  Each entity has a priority field and an order
field.  The priority field contain the input values to my algorithm, the
order fields contain the output value of my algorithm.  My algorithm needs
to assign 1 to the order field of the entity with the lowest priority value,
2 to the order field of the entity with the next lowest priority value, ....
and so on.  I've written a function orderByPriority that does that.
However, it also does something else that is undesireable.  It reorders the
list.

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.

Thanks

-John

> import Data.List

> data Entity = Entity {
>     entityId :: Int,
>     priority :: Float,
>     order :: Int
>   }

> initEntity = Entity {
>     entityId = 0,
>     priority = 0.0,
>     order = 0
>   }

> myList = [
>     initEntity { entityId = 1, priority = 8.7 },
>     initEntity { entityId = 2, priority = 5.4 },
>     initEntity { entityId = 3, priority = 2.9 },
>     initEntity { entityId = 4, priority = 5.4 },
>     initEntity { entityId = 5, priority = 1.3 },
>     initEntity { entityId = 6, priority = 3.5 },
>     initEntity { entityId = 7, priority = 9.5 }
>   ]

> comparePriority entity1 entity2 =
>   compare (priority entity1) (priority entity2)

> orderByPriority :: [Entity] -> [Entity]
> orderByPriority entities = assignOrder orderList 1
>   where
>     orderList = sortBy comparePriority entities
>     assignOrder [] _ = []
>     assignOrder (entity:entities) count =
>       (entity { order = count }):(assignOrder entities (count + 1))

> instance Show Entity where
>   show entity = "{" ++
>     "entityId:" ++ (show $ entityId entity) ++ "," ++
>     "priority:" ++ (show $ priority entity) ++ "," ++
>     "order: " ++ (show $ order entity) ++
>     "}"
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20061101/a17dc3af/attachment.htm


More information about the Haskell-Cafe mailing list