Sorting

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Sorting

Mike Houghton
Hi,

I’m trying to sort a list of tuples. A char and a count of that char (Char , Int) 
e.g.

[ ('r',2), ('c',2),('a', 2), ('b',3), ('f',2)]

e.g. ‘r’ occurs twice etc.
The order should be based on the count first and then ties broken by the 
natural ordering of char.
So 
[ ('r',2), ('c',2),('a', 2), ('b',3), ('f',2)]

will sort as

[('b',3),('a', 2), ('c',2),('f',2), ('r',2)]

I initially tried variants on
sortBy (compare `on` snd)

and then made a type Tup = T (Char, Int)
and defined Eq and then got to the point where I felt that this had become too difficult for a simple problem and concluded that I’m missing a point somewhere and need a bit of help!

Many thanks
M

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Sorting

Francesco Ariis
On Tue, Dec 13, 2016 at 02:36:39PM +0000, mike h wrote:

> Hi,
>
> I’m trying to sort a list of tuples. A char and a count of that char (Char , Int)
> e.g.
>
> [ ('r',2), ('c',2),('a', 2), ('b',3), ('f',2)]
>
> e.g. ‘r’ occurs twice etc.
> The order should be based on the count first and then ties broken by the
> natural ordering of char.

You should provide sortBy with an appropriate compare function, e.g.

    comp (a,b) (c,d) | a > c = GT
                     | -- etc etc.

or go with the manky but working hack:

λ> :m Data.List
λ> sortOn (\(a, b) -> b*(-100) + fromEnum a) [('r',2), ('c',2),('a', 2), ('b',3), ('f',2)]
[('b',3),('a',2),('c',2),('f',2),('r',2)]

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Sorting

Erlend Hamberg-2
There is a really nice solution that takes advantage of Ordering's Monoid instance (see https://wiki.haskell.org/Monoid).

The imports you need:

import Data.List (sortBy)
import Data.Ord (Down(..), comparing)
import Data.Monoid ((<>)) -- the “mappend” operator

You can then combine two calls to `comparing`

sortBy (comparing  (Down . snd) <> comparing fst) xs

(`Down` is just a newtype that reverses the ordering, since you wanted the first element in descending order and the second in ascending order.)

On Tue, 13 Dec 2016 at 16:30 Francesco Ariis <[hidden email]> wrote:
On Tue, Dec 13, 2016 at 02:36:39PM +0000, mike h wrote:
> Hi,
>
> I’m trying to sort a list of tuples. A char and a count of that char (Char , Int)
> e.g.
>
> [ ('r',2), ('c',2),('a', 2), ('b',3), ('f',2)]
>
> e.g. ‘r’ occurs twice etc.
> The order should be based on the count first and then ties broken by the
> natural ordering of char.

You should provide sortBy with an appropriate compare function, e.g.

    comp (a,b) (c,d) | a > c = GT
                     | -- etc etc.

or go with the manky but working hack:

λ> :m Data.List
λ> sortOn (\(a, b) -> b*(-100) + fromEnum a) [('r',2), ('c',2),('a', 2), ('b',3), ('f',2)]
[('b',3),('a',2),('c',2),('f',2),('r',2)]

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
--
Erlend Hamberg

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
Reply | Threaded
Open this post in threaded view
|

Re: Sorting

Mike Houghton
Thanks folks.

Francesco
Cool - I just came to that conclusion too and did

tupleOrder :: (Char, Int) -> (Char, Int) -> Ordering
        tupleOrder (c1, x1) (c2, x2) 
        -- char compared by ord and a is less than b!
          | x1 == x2 && c1 <= c2 = GT 
          | x1 == x2 && c1 >= c2 = LT
          | x1 < x2 = LT 
          | x1 > x2 = GT

and then did sortBy.


Erlend

I’ll try that - Monoids have such an understated elegance. :)


On 13 Dec 2016, at 16:01, Erlend Hamberg <[hidden email]> wrote:

There is a really nice solution that takes advantage of Ordering's Monoid instance (see https://wiki.haskell.org/Monoid).

The imports you need:

import Data.List (sortBy)
import Data.Ord (Down(..), comparing)
import Data.Monoid ((<>)) -- the “mappend” operator

You can then combine two calls to `comparing`

sortBy (comparing  (Down . snd) <> comparing fst) xs

(`Down` is just a newtype that reverses the ordering, since you wanted the first element in descending order and the second in ascending order.)

On Tue, 13 Dec 2016 at 16:30 Francesco Ariis <[hidden email]> wrote:
On Tue, Dec 13, 2016 at 02:36:39PM +0000, mike h wrote:
> Hi,
>
> I’m trying to sort a list of tuples. A char and a count of that char (Char , Int)
> e.g.
>
> [ ('r',2), ('c',2),('a', 2), ('b',3), ('f',2)]
>
> e.g. ‘r’ occurs twice etc.
> The order should be based on the count first and then ties broken by the
> natural ordering of char.

You should provide sortBy with an appropriate compare function, e.g.

    comp (a,b) (c,d) | a > c = GT
                     | -- etc etc.

or go with the manky but working hack:

λ> :m Data.List
λ> sortOn (\(a, b) -> b*(-100) + fromEnum a) [('r',2), ('c',2),('a', 2), ('b',3), ('f',2)]
[('b',3),('a',2),('c',2),('f',2),('r',2)]

_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
--
Erlend Hamberg
_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners


_______________________________________________
Beginners mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners