Generic Sorting

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

Generic Sorting

Henry Laxen
Good evening Haskellers.

I've done some searching but so far haven't found anything, which make
me think this probably isn't possible.  I am wondering if it is
possible to do a "Generic Sort" on multilevel data structures.
Suppose you have something like:

data A = A Int [Int]
data B = B Int [A]

a1 = A 2 [2,1]
a2 = A 1 [4,3]
b  = B 1 [a1,a2]

genericSort b = B 1 [A 1 [3,4], A 2 [1,2]]

note that not only are the A's sorted, but the list inside each A is
sorted.  It "sorted all the way down".  Has Edward written such a
thing yet? ;-) His "discrimination" library doesn't do this, in case
you're wondering.  Any ideas?

Best wishes,
Henry Laxen
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Generic Sorting

Haskell - Haskell-Cafe mailing list
November 14, 2020 2:08 PM, "Henry Laxen" <[hidden email]> wrote:

> I've done some searching but so far haven't found anything, which make
> me think this probably isn't possible. I am wondering if it is
> possible to do a "Generic Sort" on multilevel data structures.
> Suppose you have something like:

This is not quite what you asked for, but might get you started. It's based on a trick that Alex Mason once showed me:

{-# LANGUAGE AllowAmbiguousTypes  #-}
{-# LANGUAGE DeriveDataTypeable  #-}
{-# LANGUAGE ScopedTypeVariables #-}

import Control.Lens
import Data.Data
import Data.Data.Lens
import Data.List

data A = A Int [Int] deriving (Data, Show)
data B = B Int [A] deriving (Data, Show)

a1 = A 2 [2,1]
a2 = A 1 [4,3]
b  = B 1 [a1,a2]

-- | oh no
-- >>> genericSort @Int b
-- B 1 [A 1 [1,2],A 2 [3,4]]
genericSort :: forall a d . (Data d, Typeable a, Ord a) => d -> d
genericSort = partsOf template %~ (sort :: [a] -> [a])

Note that it's sorted every Int anywhere in the structure, not just the ones inside an A.

HTH,
-- Jack
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Generic Sorting

Henning Thielemann
In reply to this post by Henry Laxen

On Fri, 13 Nov 2020, Henry Laxen wrote:

> Good evening Haskellers.
>
> I've done some searching but so far haven't found anything, which make
> me think this probably isn't possible.  I am wondering if it is
> possible to do a "Generic Sort" on multilevel data structures.
> Suppose you have something like:
>
> data A = A Int [Int]
> data B = B Int [A]
>
> a1 = A 2 [2,1]
> a2 = A 1 [4,3]
> b  = B 1 [a1,a2]
>
> genericSort b = B 1 [A 1 [3,4], A 2 [1,2]]
>
> note that not only are the A's sorted, but the list inside each A is
> sorted.  It "sorted all the way down".  Has Edward written such a
> thing yet? ;-) His "discrimination" library doesn't do this, in case
> you're wondering.  Any ideas?

You could first sort the structures and then fill it with a sorted
flattened list.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|

Re: Generic Sorting

Henry Laxen
In reply to this post by Haskell - Haskell-Cafe mailing list
>>>>> "jack" == jack  <[hidden email]> writes:

    Henry> November 14, 2020 2:08 PM, "Henry Laxen" <[hidden email]> wrote:
    Henry> I've done some searching but so far haven't found anything, which make
    Henry> me think this probably isn't possible. I am wondering if it is
    Henry> possible to do a "Generic Sort" on multilevel data structures.
    Henry> Suppose you have something like:

    jack> This is not quite what you asked for, but might get you started. It's based on a trick that Alex Mason once showed me:

    jack> {-# LANGUAGE AllowAmbiguousTypes  #-}
    jack> {-# LANGUAGE DeriveDataTypeable  #-}
    jack> {-# LANGUAGE ScopedTypeVariables #-}

    jack> import Control.Lens
    jack> import Data.Data
    jack> import Data.Data.Lens
    jack> import Data.List

    jack> data A = A Int [Int] deriving (Data, Show)
    jack> data B = B Int [A] deriving (Data, Show)

    jack> a1 = A 2 [2,1]
    jack> a2 = A 1 [4,3]
    jack> b  = B 1 [a1,a2]

    jack> -- | oh no
    jack> -- >>> genericSort @Int b
    jack> -- B 1 [A 1 [1,2],A 2 [3,4]]
    jack> genericSort :: forall a d . (Data d, Typeable a, Ord a) => d -> d
    jack> genericSort = partsOf template %~ (sort :: [a] -> [a])

    Henry> Note that it's sorted every Int anywhere in the structure, not just the ones inside an A.

Wow Jack, that looks like magic.  I'm going to read about partsOf and
template, which I've never used before.  One thing, to actuall run it you need
to add {-# LANGUAGE TypeApplications #-} so you can say "genericSort @Int b".
Thanks so much for your quick and brilliant response.
Best wishes,
Henry Laxen
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.