# Class method with heterogeneous recursive infinite and dependent type argument

I am stuck playing with "heterogeneous recursive infinite type" (some better title?).

Let the next worker "Deep Sort"

``````class Ord f => DeepSort f where
deepSort :: f -> f
deepSort = id

instance DeepSort Int where
-- and so on ...

instance DeepSort a => DeepSort [a] where
deepSort = sort . map deepSort
instance DeepSort a => DeepSort (Maybe a) where
deepSort = fmap deepSort
-- and so on ...
```

```

eg

``````sample :: [Maybe [[Int]]]
sample = [ Just [[5, 3, 7, 1], [6, 0]]
, Nothing
, Just [[8, -1], []]
]

main = print \$ deepSort sample
```

```

writes

``````[Nothing,Just [[],[-1,8]],Just [[0,6],[1,3,5,7]]]
```

```

but now I want to parameterize the sort criteria to do something like ( doesn't work )

``````main = print \$ deepSortBy sample
( By   (compare `on` someCriteria1)
\$ By   (compare `on` someCriteria2)
\$ By   (compare `on` someCriteria3)
\$ Then (compare `on` someCriteria4)
)
```

```

My problem is how to define the "heterogeneous recursive infinite type" argument (or whatever name you like).

I think that it is

``````By (f1 (f2 ... (fN a) ...)
(By (f2 ... (fN a) ...)
...
Then (fN a)
)
```

```

Note: In the example, `deepSort`

nested containers are sorted in ascending order with the `Ord`

default instance ; the point `deepSortBy`

is to provide explicit comparison functions `Ord`

for each nested container. As containers `f1 (f2 (f3 ... (fN a)...)`

, then the criteria can / should be represented as `By comparer1 (By comparer2 (By ...`

. But, of course, another approach might be better.

Also, there is probably a better "Haskell" approach BUT I wish (if possible)

• Is there some direct solution for my "by class" approach?

• Why is Haskell's approach to this problem better?

• Do some libraries solve this?

Thank!!!

EDITED

I have a possible solution approach (post as solution, it works!: D)

+3

source to share

Any structure that can be traversed can be sorted. Both `Maybe`

and `[]`

are equal `Traversable`

. We can understand that everything `Traversable`

`Functor`

can be sorted by the following definition `sortBy`

. It works by listing all the data in a structure, sorting that list, and then moving the structure from left to right, replacing each item with the first item in the list, and keeping the rest of the list.

``````import qualified Data.List as List

import Data.Foldable
import Data.Traversable

sortBy :: Traversable f => (a -> a -> Ordering) -> f a -> f a
sortBy o f = snd . mapAccumL (\(h:t) _ -> (t, h)) sorted \$ f
where
sorted = List.sortBy o . toList \$ f
```

```

When you `deepSortBy`

do something, you just apply the function internally `Traversable`

`Functor`

before sorting it. It's just a handy feature that captures this pattern.

``````deepSortBy :: Traversable f => (b -> b -> Ordering) -> (a -> b) -> f a -> f b
deepSortBy o f = sortBy o . fmap f
```

```

We can conveniently write the sorting of your sample in terms of `deepSortBy`

.

``````sample :: [Maybe [[Int]]]
sample = [ Just [[5, 3, 7, 1], [6, 0]]
, Nothing
, Just [[8, -1], []]
]

sampleSorter :: [Maybe [[Int]]] -> [Maybe [[Int]]]
sampleSorter =
deepSortBy (compare `on` isJust) \$
deepSortBy (compare `on` length) \$
deepSortBy (compare `on` listToMaybe) \$
sortBy compare
```

```

The last line is `sortBy compare`

equivalent `deepSortBy compare id`

. `listToMaybe`

avoids the error that will be `head`

.

### Reusing deeper discontinuous comparisons

Note that this does not repeat the deeper tie break comparison in external comparisons. For example `sample`

sorted with

``````[Nothing,Just [[0,6],[1,3,5,7]],Just [[],[-1,8]]]
```

```

`Just [[0,6],[1,3,5,7]]`

and `Just [[],[-1,8]]`

binding when comparing by `isJust`

and `[[0,6],[1,3,5,7]]`

and `[[],[-1,8]]`

when comparing by `length`

. If internal comparisons were used to break these bonds, `listToMaybe`

they would be reversed. If the desired result is

``````[Nothing,Just [[],[-1,8]],Just [[0,6],[1,3,5,7]]]
```

```

we need to do a bit of work to capture the internal comparisons.

+4

source

All Articles