在Haskell中,如何对无限字符串列表进行排序？

Question

所以基本上,如果我有一个(有限的或无限的)字符串列表(有限或无限)列表,是否可以先按长度排序列表,然后按字典顺序排序,不包括重复项？输入/输出的示例如下:

输入:

[["a","b",...],["a","aa","aaa"],["b","bb","bbb",...],... ]

输出:

["a","b","aa","bb","aaa","bbb",...]

我知道输入列表不是有效的haskell表达式,但假设有类似的输入.我尝试使用合并算法,但它倾向于挂在我给它的输入上.有人可以解释并展示一个可以做到这一点的体面分类功能吗？如果没有这样的功能,你能解释一下原因吗？

如果某人不理解排序顺序的含义,我的意思是最短的字符串首先排序,如果一个或多个字符串的长度相同,则使用<运算符对它们进行排序.

谢谢!

Answer 1

最终,你无法对无限列表进行排序,因为列表尾部的项目可以一直渗透到结果的前面,所以在看到最后一项之前你无法完成无限列表的排序,但是你的名单是无限的,所以你永远不会到达那里.

您甚至可以尝试对无限列表进行排序的唯一方法是需要对列表中的居民进行约束.如果列表项的值来自一个有根据的集合,并且列表的内容是唯一的,那么您至少可以在返回元素列表的初始元素方面取得一些进展.例如,如果列表具有不同的自然数,则可以返回您看到的前0,然后是第1个等,但是在您看到2之前,无论在列表中有多远,您都无法在结果中取得任何进展你去了.最终,如果你曾经跳过集合中的元素,因为它不存在于源代码中,那么在你掌握了整个输入之前,你将停止生成新的输出元素.

您可以使用字符串执行相同的操作,因为它们是有根据的,但如果您计划返回所有可能的字符串,那么这甚至是可行的.

简而言之,如果您需要这个,那么您将以错误的方式解决您遇到的问题.这不是您想要使用的任何解决方案的易处理路径.

正如yairchu指出的那样,合并有限数量的有序无限列表可以正常工作.

Answer 2

• 通常,无法对无限列表进行排序.因为最小的项目可能处于无限的位置,我们必须在输出它之前找到它.

• 合并无限排序列表是可能的.

• 通常,合并无限的排序列表列表是不可能的.出于同样的原因,对它们进行排序.

• 合并无限列表的排序列表是可能的,这些列表按头(forall i j.i < j=> head (lists !! i) <= head (lists !! j))排序.

所以我猜你真正想要的是合并一个排序无限的排序列表列表.这甚至是一项有意义的任务.甚至有一些现有的代码使用它,在那里为monadic列表实现 - 有点丑陋的语法等等.所以这里是普通列表的一个版本:

mergeOnSortedHeads :: Ord b => (a -> b) -> [[a]] -> [a]
mergeOnSortedHeads _ [] = []
mergeOnSortedHeads f ([]:xs) = mergeOnSortedHeads f xs
mergeOnSortedHeads f ((x:xs):ys) =
  x : mergeOnSortedHeads f (bury xs ys)
  where
    bury [] ks = ks
    bury js [] = [js]
    bury js ([]:ks) = bury js ks
    bury jj@(j:js) ll@(kk@(k:ks):ls)
      | f j <= f k = jj : ll
      | otherwise = kk : bury jj ls

ghci> take 20 $ mergeOnSortedHeads id $ [[0,4,6], [2,3,9], [3,5..], [8]] ++ map repeat [12..]
[0,2,3,3,4,5,6,7,8,9,9,11,12,12,12,12,12,12,12,12]

顺便说一句:你需要什么？