[Haskell-cafe] What is the best way to preserve the order of
a list
Brandon Moore
brandonm at yahoo-inc.com
Wed Nov 1 15:03:28 EST 2006
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
More information about the Haskell-Cafe
mailing list