具有异构递归无限和依赖类型参数的类方法

Question

我被困在玩"异构递归无限类型">(更好的标题？

让下一个工作"深度排序">

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

但现在我想参数化排序标准，做一些类似的事情(不起作用(

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

我的问题是如何定义"异构递归无限类型">参数(或任何名称(。

我认为是

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

注意：deepSort示例中，嵌套容器按默认Ord实例升序排序;deepSortBy的意义是为每个嵌套容器提供显式Ord比较函数。由于容器是f1 (f2 (f3 ... (fN a)...)的，因此可以/应该提供标准作为By comparer1 (By comparer2 (By ...。当然，其他方法可能更好。

此外，可能存在更好的"Haskell方法">，但我希望(如果可能的话(

• 我的"按类">方法存在一些直接解决方案吗？

• 对于这类问题，什么是更好的"Haskell方法">？

• 一些图书馆解决了这个问题？

谢谢！！！

编辑

我有一个可能的解决方案方法(发布为解决方案，它有效！ :D (

Answer 1

可以对任何可以遍历的结构进行排序。Maybe和[]都是Traversable。我们可以捕捉到这样的想法，即所有Traversable Functor都可以按以下定义进行排序 sortBy .它的工作原理是列出结构中的所有数据，对该列表进行排序，然后从左到右遍历结构，将每个项目替换为列表中的第一项，并携带列表的其余部分。

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

当你deepSortBy某物时，你只是在Traversable Functor内应用一个函数，然后再对其进行排序。它只是一个捕获此模式的便利功能。

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

我们可以方便地根据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

最后一行 sortBy compare 等效于 deepSortBy compare id 。 listToMaybe避免了head会抛出的错误。

重用更深层次的比较来断绝关系

请注意，这不会重用更深层次的比较来打破外部比较中的联系。例如，sample排序为

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

Just [[0,6],[1,3,5,7]]和Just [[],[-1,8]]在isJust上比较时并列，[[0,6],[1,3,5,7]]和[[],[-1,8]]在length上比较时并列。如果用内部比较来打破这些联系，listToMaybe会把它们放在相反的顺序上。如果期望的结果是

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

我们必须做更多的工作来捕捉内部比较。