所以基本上，如果我有（有限或无限）列表（有限或无限）字符串列表，是否可以按列表先按长度对列表进行排序，然后按照字典顺序对列表进行排序，排除重复项？样品输入/输出将是：在Haskell中，你如何排序无限的字符串列表？
输入：
[[ “一”， “B”，...]，[ “一”， “AA”， “AAA”]，[“B ”， “BB”， “BBB”，...]，...]
输出：
[ “一”， “b”， “AA”， “BB”， “AAA”， “bbb”，...]
我知道输入列表不是有效的haskell表达式，但假设有这样的输入。我尝试使用合并算法，但它倾向于挂在我给它的输入上。有人可以解释并显示一个体面的排序功能，可以做到这一点？如果没有这样的功能，你能解释为什么吗？
如果有人不明白我的排序顺序是什么意思，我的意思是最短长度的字符串先排序，如果一个或多个字符串长度相同，则使用<运算符排序。
谢谢！
那么，我会忽略你的请求排序无限的数据。
按照子列表的长度进行排序，然后按字典顺序，我们可以很容易地做到这一点。哦，你想删除重复项。
我们将与样本开始：
> s
[["a","b"],["a","aa","aaa"],["b","bb","bbb"]]
，然后生成程序增量。
长度上第一分拣（使用Data.Ord.comparing建立排序体）：
> sortBy (comparing length) s
[["a","b"],["a","aa","aaa"],["b","bb","bbb"]]
确定。这看起来很合理。因此，我们只需concat，然后sortBy长度然后alpha：
> sortBy (comparing length) . nub . concat $ s
["a","b","aa","bb","aaa","bbb"]
如果您的输入是排序的。否则，你需要一个非常不同的身体来排序。
一般来说，不可能对无限列表进行排序。因为最小的物品可能处于无限的位置，我们必须在输出它之前找到它。
Merging无限排序列表是可能的。
通常，合并无限列表的排序列表是不可能的。出于同样的原因，排序他们是。
合并无限列表的排序列表（按照排序顺序排列）（forall i j。i < j =>head (lists !! i) <= head (lists !! j)），是可能的。
所以我猜你真正想要的是合并排序列表的无序列表。这甚至是一个有意义的任务。甚至还有使用它some existing code，对于单子列出来实现有 - 有点丑陋的语法，明智等，所以这里是为纯清单版本：
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 [email protected](j:js) [email protected]([email protected](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]
BTW：你需要什么用的？
最终，您无法对无限列表进行排序，因为列表尾部的项目可能会渗透到结果的前部，因此您无法完成排序无限列表直到看到最后一项，但你的名单是无限的，所以你永远不会到达那里。
您甚至可以尝试对无限列表进行排序的唯一方法是需要对列表中的居民进行限制。如果列表项的值来自well-founded set并且列表的内容是唯一的，那么您至少可以在返回元素时使列表的初始元素有所进展。例如，如果列表具有不同的自然数，那么您可以返回您看到的前0个，然后是前1个，但是无论结果有多少，只要您看到2，结果就无法取得任何进展你去了。最终，如果你跳过了一个元素，因为它没有出现在源代码中，你将不再生产新的输出元素，直到你掌握完整的输入。
你可以用字符串做同样的事情，因为它们是有根据的，但是如果你计划返回所有可能的字符串，那它只能是远程可行的。
总之，如果你需要这个，你就要解决你错误的方法。这不是任何您想要使用的解决方案的易处理路径。
正如yairchu指出的，合并有限数量的有序数目的无限列表可以很好地工作。
是否可以完成取决于输入数据的性质。如果在看到一个长度较长的列表时，如果可以“停止查找”某个长度的列表，则每个长度只有有限数量的列表，那么可以按升序排列长度，对这些列表进行排序连接结果。像这样的东西应该工作：
listsUptoLength n xss = takeWhile (\xs -> length xs <= n) $ xss
listsUptoLength' n [] = []
listsUptoLength' n (xss:xsss) = case listsUptoLength n xss of
[] -> []
xss' -> xss' : listsUptoLength' n xsss
listsOfLength n xsss = concatMap (\xss -> (filter (\xs -> length xs == n) xss)) (listsUptoLength' n xsss)
sortInfinite xsss = concatMap (\n -> sort . nub $ (listsOfLength n xsss)) [0..]
f xs y = [xs ++ replicate n y | n <- [1..]]
test = [ map (\x -> [x]) ['a'..'e'], f "" 'a', f "" 'b', f "b" 'a', f "a" 'b' ] ++ [f start 'c' | start <- f "" 'a']
（名字也许可以选择更照亮:)
我猜测你使用正则表达式，所以我觉得是这样的可以开始工作;我重复请求更多背景！
感谢大家对他们的投入，并对迟到的回复感到抱歉。原来我只是以一种错误的方式来解决问题。我试图做Yairchu显示，但我使用内置函数length进行合并，但长度不能在无限列表上工作，原因很明显。无论如何，我通过排序来解决问题，因为我在旅途中创建了列表，而不是最终的结果。我想知道其他语言提供无限列表吗？这样一个奇怪但有用的概念。
通过单击答案下方的复选框，不要忘记标记最佳答案作为答案。 – 2011-04-12 14:05:08
这是一种算法，让你在线排序：
它是没有效率的，但它是够懒，让您转到不同的排序几代人，即使你排序无限列表。这是一个很好的噱头，但不是很有用。例如，排序无限列表[10,9 ..]：
*Main> take 10 $ sortingStream [10,9..] !! 0
[9,8,7,6,5,4,3,2,1,0]
*Main> take 10 $ sortingStream [10,9..] !! 1
[8,7,6,5,4,3,2,1,0,-1]
*Main> take 10 $ sortingStream [10,9..] !! 2
[7,6,5,4,3,2,1,0,-1,-2]
*Main> take 10 $ sortingStream [10,9..] !! 3
[6,5,4,3,2,1,0,-1,-2,-3]
*Main> take 10 $ sortingStream [10,9..] !! 4
[5,4,3,2,1,0,-1,-2,-3,-4]
*Main> take 10 $ sortingStream [10,9..] !! 1000
[-991,-992,-993,-994,-995,-996,-997,-998,-999,-1000]
正如您所看到的排序改进了每一代。代码：
produce :: ([a] -> [a]) -> [a] -> [[a]]
produce f xs = f xs : (produce f (f xs))
sortingStream :: (Ord a) => [a] -> [[a]]
sortingStream = produce ss
ss :: (Ord a) => [a] -> [a]
ss [] = []
ss [x] = [x]
ss [x,y] | x <= y = [x,y]
| otherwise = [y,x]
ss (x:y:xs) | x <= y = x: (ss (y:xs))
| otherwise = y:(ss (x:xs))
你能保证输入列表按照你的例子排序吗？ – 2010-03-07 00:52:39