list - 一种生成给定长度组合的更快方法，保留顺序

Question

TL;DR:我想要确切的行为 filter ((== 4) . length) . subsequences .只是使用 subsequences还会创建可变长度的列表，这需要大量时间来处理。由于最终只需要长度为 4 的列表，我认为必须有一种更快的方法。

我有一个功能列表。该列表的类型为 [Wor -> Wor]
列表看起来像这样
[f1, f2, f3 .. fn]
我想要的是一个列表列表 n功能，同时保持这样的顺序

输入:[f1, f2, f3 .. fn]
参数:4 个函数

输出:4 个函数的列表。

如果存在 f1，则预期输出将在何处在子列表中，它将始终位于 head的名单。

如果有 f2在子列表中，如果子列表没有 f1 , f2将在 head .如 fn位于子列表中，它将位于 last .

一般来说，如果有 fx在列表中，它永远不会出现在 f(x - 1) 的前面.

生成子列表时基本上保留主列表的顺序。

可以假设列表的长度总是大于给定的参数。

我刚刚开始学习 Haskell，所以我还没有尝试那么多，但到目前为止，这是我尝试过的:

代排列 subsequences功能及应用 (filter (== 4) . length)在它上面似乎生成了正确的排列——但它不保留顺序——(它保留了顺序，我把它和我自己的函数混淆了)。

所以我该怎么做？

如果可能的话，Hackage 中是否存在一个函数或函数的组合？或 Stackage哪个可以做到这一点？因为我想了解来源。

Answer 1

您描述了一个不确定性 take :

ndtake :: Int -> [a] -> [[a]]
ndtake 0 _      = [[]]
ndtake n []     = []
ndtake n (x:xs) = map (x:) (ndtake (n-1) xs) ++ ndtake n xs

要么我们拿一个 x ，并有 n-1更多内容来自 xs ;或者我们不接 x并有 n更多元素来自 xs .

运行:

> ndtake 3 [1..4]
[[1,2,3],[1,2,4],[1,3,4],[2,3,4]]

更新:你想要效率。如果我们确定输入列表是有限的，我们可以尽快停止:

ndetake n xs = go (length xs) n xs
    where
    go spare n _  | n >  spare = []
    go spare n xs | n == spare = [xs]
    go spare 0 _      =  [[]]
    go spare n []     =  []
    go spare n (x:xs) =  map (x:) (go (spare-1) (n-1) xs) 
                            ++     go (spare-1)  n   xs

尝试:

> length $ ndetake 443 [1..444]
444

前一个版本似乎卡在这个输入上，但后一个版本立即返回。

但是，正如 @dfeuer 所指出的，它测量了整个列表的长度，这是不必要的。在评论中。我们可以实现同样的效率提升，同时保留更多的惰性:

ndzetake :: Int -> [a] -> [[a]]
ndzetake n xs | n > 0 = 
    go n (length (take n xs) == n) (drop n xs) xs
    where
    go n b p ~(x:xs)
         | n == 0 = [[]]
         | not b  = []
         | null p = [(x:xs)]
         | otherwise = map (x:) (go (n-1) b p xs)
                          ++ go n b (tail p) xs

现在最后一个测试也可以立即使用此代码。

这里还有改进的余地。就像库函数 subsequences ，搜索空间可以更懒惰地探索。现在我们有

> take 9 $ ndzetake 3 [1..]
[[1,2,3],[1,2,4],[1,2,5],[1,2,6],[1,2,7],[1,2,8],[1,2,9],[1,2,10],[1,2,11]]

但它可能会找到 [2,3,4]之前强制 5出输入列表。我们可以把它作为练习吗？