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)
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.
source to share