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

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子列表中有 a而子列表没有f1，f2则位于head。如果fn在子列表中，它将在last.

一般来说，如果fx列表中有 a ，它永远不会在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退出输入列表之前找到。我们可以把它作为练习吗？