具有异构递归无穷大且依赖类型参数的类方法
我一直在玩“异构递归无限类型”(更好的标题？)。
让下一个工作“深度排序”
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 )
回答 1
Stack Overflow用户
发布于 2014-10-08 19:28:08
任何可以是横越的结构都可以排序。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]]]我们需要做更多的工作来捕捉内心的比较。
https://stackoverflow.com/questions/26252289
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号