生成列表的所有连续子列表

Question

我有点新手使用Haskell，我正在尝试生成列表的所有连续子列表。

我目前有以下代码：

listSublists :: [a] -> [[a]]
listSublists []     = [[]]
listSublists xs     = [xs] ++ listSublists (init xs) 

我知道上面的函数会生成去掉最后一个元素的子列表，但我不知道如何完成我的伪代码。

我的伪代码基本上是这样的，

取整个完整列表，删除尾部。将（x:xs）的xs传递到listSublists中

例如，xs = [1,2,3] [xs] ++ listSublists (init xs) 将生成[1,2,3,4]、[1,2,3]、[1,2]、[1]、[]，我试图继续传入[2,3,4]作为xs，直到列表用尽。

有人可以给我一些指针吗？还是我想法完全错误了？

- rlhh

Answer 1

您拥有的listSublists函数在功能上几乎与inits函数相同。您正在正确的道路上，因为您目前可以列出给定列表的所有前缀。

您想要问的是“什么是列表的子列表？”一个答案是它是列表前缀的后缀（即从列表末尾截掉一部分，然后从该列表的前面截掉一些元素，这样您就得到了其中一个连续的子列表）。

所以，如果您拥有您的prefixes，那么您想要的是一种生成给定前缀（即某个列表）的所有后缀的方法。所以，如果您拥有：

prefixes :: [a] -> [[a]]
prefixes []     = [[]]
prefixes xs     = [xs] ++ prefixes (init xs) 

您还希望有一个相应的功能后缀

suffixes :: [a] -> [[a]]
suffixes []     = [[]]
suffixes xs     = [xs] ++ suffixes (??? xs) 

我会留给你自己决定要用什么代替???。使用这两个函数，你只需要取出所有前缀，然后生成所有后缀，就可以得到所有连续子列表。

allSublists :: [a] -> [[a]]
allSublists = concat . map suffixes . prefixes

您可能希望在结果集中删除所有空列表，因为它们不是很有趣的情况。

- sabauma

---

谢谢你的回答。我知道我应该使用tail来???，但我不太理解concat . map suffixes . prefixes这部分。我不确定如何正确地编写它。 - rlhh

@user1043625 我不确定你的意思。那就是你应该写的方式。除非你想知道如何编写其中的列表函数。否则，它只是一组函数的组合。 - sabauma

我相信我误解了你回答的某些部分，但我相信我已经弄清楚了。我实际上是用不同的方法来做这件事。listSuffix(xs) ++ listPrefix(init xs)。现在我需要找到一种方法来删除空列表的重复项。 - rlhh

Answer 2

所有子列表（不一定连续）：

sublists [] = [[]]
sublists (x:xs) = [x:sublist | sublist <- sublists xs] ++ sublists xs

仅连续子列表：

nub $ concat $ map tails $ inits ls

或者

(:) [] $ filter (\x -> length x /= 0) $ concat $ map tails $ inits ls

- smilenkovic