编写一个函数来获取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 = ...

请记住,基本案例的定义需要与递归案例中的定义一起使用.仔细想想:不要只假设基本案例都会产生一个空列表.

这有帮助吗？