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

[Brandon Moore]

Henk-Jan van Tuyl wrote:
> On Wed, 01 Nov 2006 10:29:18 +0100, Stefan Holdermans 
> <stefan at cs.uu.nl> wrote:
>
>>        sortOnLab   = sortBy (\(l, _) (m, _) -> compare l m)
>
> The following does the same:
>         sortOnLab   = sort
Not quite, sortOnLab preserves the order of tuples with the same first 
element while plain sort orders them by the second. Also, only sort 
requires that the second element of the tuple have an Ord instance 
(Haskell 98 requires that sort is stable).

 > Test.QuickCheck.test (\xs -> sort xs == sortOnLab xs)
Falsifiable, after 1 tests:
[(-3,3),(-3,1)]

 > sortOnLab [(-3,3),(-3,1)]
==>
[(-3,3),(-3,1)]

but
sort [(-3,3),(-3,1)]
==>
[(-3,1),(-3,3)]


Also,
 > map fst $ sortOnLab [(2,asTypeOf),(1,const)]
[1,2]

 > map fst $ sort [(2,asTypeOf),(1,const)]

<interactive>:1:10:
    No instance for (Ord (a -> a -> a))
      arising from use of `sort' at <interactive>:1:10-38
    Possible fix: add an instance declaration for (Ord (a -> a -> a))
    In the second argument of `($)', namely
    `sort [(1, asTypeOf), (1, const)]'
    In the expression: (map fst) $ (sort [(1, asTypeOf), (1, const)])
    In the definition of `it':
    it = (map fst) $ (sort [(1, asTypeOf), (1, const)])

Brandon