你如何找到列表的所有子序列？

Question

我正在努力学习如何列出理解,我正试图找到一种方法来查找列表的所有子序列,但我不太确定如何去做.谁能帮助我？

Answer 1

另一个有趣的解决方案

filterM (const [True,False]) [1,2,3]

我按如下方式阅读:返回包括或不包括列表元素的可能组合.这种解释可能没有使用正确的术语,但这是我直观地理解它的方式.为每个元素const求值[True,False],因此每个元素都包含在结果中或不包含在结果中.使用filterM,这里的谓词在列表monad中,因此我们得到可能结果的列表.

Answer 2

如果要访问此功能,可以使用其中的subsequences功能Data.List.

subsequences [1,2,3]
>>> [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

如果您想知道它是如何实现的,您可以查看函数的源代码,该代码可在Hackage上获得.

在这种情况下,它是:

subsequences            :: [a] -> [[a]]
subsequences xs         =  [] : nonEmptySubsequences xs

nonEmptySubsequences         :: [a] -> [[a]]
nonEmptySubsequences []      =  []
nonEmptySubsequences (x:xs)  =  [x] : foldr f [] (nonEmptySubsequences xs)
  where f ys r = ys : (x : ys) : r

Answer 3

Ezra的答案涵盖了所有子序列,但如果你只想要连续的子序列,你可以使用:

import Data.List
continuousSubSeqs = filter (not . null) . concatMap inits . tails

你知道了

Prelude Data.List> continuousSubSeqs "asdf"
["a","as","asd","asdf","s","sd","sdf","d","df","f"]

以上内容也可以写成列表理解:

import Data.List
continuousSubSeqs ls = [t | i <- inits ls, t <- tails i, not $ null t]