所以基本上,如果我有一个(有限或无限)字符串列表的(有限或无限)列表,是否可以先按长度排序列表,然后按字典顺序排序,排除重复项?示例输入/输出如下:
输入:
[["a", "b",...], ["a", "aa", "aaa"], ["b", "bb", "bbb",...], ...]
输出:
[“a”、“b”、“aa”、“bb”、“aaa”、“bbb”、...]
我知道输入列表不是有效的 haskell 表达式,但假设存在这样的输入。我尝试使用合并算法,但它往往会依赖于我提供的输入。有人可以解释并展示一个可以做到这一点的像样的排序功能吗?如果没有这样的功能,你能解释一下为什么吗?
如果有人不明白我所说的排序顺序的含义,我的意思是首先对最短长度的字符串进行排序,并且如果一个或多个字符串具有相同的长度,则使用 < 运算符对它们进行排序。
谢谢!
最佳答案
最终,您无法对无限列表进行排序,因为列表尾部的项目可能会一直渗透到结果的前面,因此您无法完成对无限列表的排序,直到您看到最后一项,但你的列表是无限的,所以你永远不会到达那里。
您甚至可以尝试对无限列表进行排序的唯一方法需要对列表中的居民进行限制。如果列表项的值来自 well-founded set并且列表的内容是唯一的,那么您至少可以在将元素返回列表的初始元素方面取得一些进展。例如,如果列表由不同的自然数组成,您可以返回您看到的第一个 0,然后返回第一个 1,依此类推。但在您看到 2 之前,无论列表的位置有多远,您都无法在结果中取得任何进展你去了。最终,如果您因为源中不存在而跳过了集合中的某个元素,那么您将停止生成新的输出元素,直到您掌握了整个输入。
您可以对字符串执行相同的操作,因为它们是有根据的,但如果您计划返回所有可能的字符串,那么这只是远程可行的。
简而言之,如果您需要这个,那么您将以错误的方式解决您遇到的问题。对于您想要使用的任何解决方案来说,这都不是一条容易处理的路径。
正如 yairchu 所指出的,合并有限数量的已排序无限列表效果很好。
关于sorting - 在 Haskell 中,如何对无限字符串列表进行排序?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2394684/