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 ...



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

main = print $ deepSort sample



[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?



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


source to share

1 answer

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

and []

are equal Traversable

. We can understand that everything Traversable


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
        sorted = List.sortBy o . toList $ f


When you deepSortBy

do something, you just apply the function internally Traversable


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.



All Articles