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

Question

我对Haskell有点陌生，我试图生成列表的所有连续子列表。

我目前有以下几点：

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

我知道上面的函数会在删除最后一个元素的情况下生成子列表，但我不知道如何完成伪代码。

我的伪代码基本上是，

拿着完整的清单，去掉尾巴。将（x:xs）的xs传递到列表子列表中

例如，xs=[1,2,3][xs]列表子列表（init xs）将生成[1,2,3,4]、[1,2,3]、[1,2]、[1]、[1]、[1]，[1]，我试图继续以xs的形式传入[2,3,4]，直到列表用尽。

有人能给我指点指点吗？还是我的思维方式完全错了？

Answer 1

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

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

Answer 2

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

你要问的是“什么是列表的子列表？”一个答案是它是列表前缀的后缀（即从列表的末尾砍掉一些部分，然后从列表的前面砍掉一些元素，这样就有了一个连续的子列表）。

因此，如果您有前缀，那么您需要的是一种生成给定前缀（即某个列表）的所有后缀的方法。所以，如果你有

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

您可能想要删除结果集中的所有空列表，因为它们不是那么有趣的案例。