haskell - 在 Haskell 中编写一个函数来获取大小为 n 的所有子序列？

Question

我试图编写一个函数来获取大小为 n 的列表的所有子序列，但我不知道如何去做。

我想我可能可以使用内置的 Data.List.subsequences 并过滤掉大小不是 n 的列表，但这似乎是一种相当迂回且低效的方法，而且我'如果可以避免的话我宁愿不这样做，所以我想知道你有什么想法吗？

我希望它是这样的类型

subseqofsize :: Int -> [a] -> [[a]]

为了进一步说明，这是我正在寻找的示例:

subseqofsize 2 [1,2,3,3]
[[1,2],[1,3],[2,3],[1,3],[2,3],[3,3]]

此外，我不关心任何事情的顺序。

Answer 1

我假设这是家庭作业，或者您这样做是为了学习练习，所以我会给您一个解决方案的概述，而不是用勺子给您灌输正确的答案。

无论如何，这是一个递归问题。

有两种基本情况:

sublistofsize 0 _        = ...
sublistofsize _ []       = ...

然后有两个递归步骤:

sublistofsize n (x : xs) = sublistsThatStartWithX ++ sublistsThatDon'tStartWithX
  where sublistsThatStartWithX = ...
        sublistsThatDon'tStartWithX = ...

请记住，基本情况的定义需要与递归情况中的定义适当配合。仔细思考:不要仅仅假设基本情况都会导致空列表。

这有帮助吗？