Haskell实现m元素组合函数comb的技术求助

给定一个含n个不同元素的列表xs，需要实现函数comb，接收自然数m和列表xs，返回所有从xs中选m个元素的组合（元素顺序无关，无重复元素）。示例如下：

• comb 0 "abcd" → [""]
• comb 3 "bcd" → ["bcd"]
• comb 2 "bcd" → ["cd","bd","bc"]
• comb 3 "abcd" → ["bcd", "acd", "abd", "abc"]

我已经理清了思路：用“位置指针”的方式，通过移除指针后length xs - m个元素得到结果，再递归移动指针，但不知道怎么用Haskell代码实现。用指针类比的伪逻辑如下：

m = 3，xs = "abcd"，* 代表指针
abcd → 移除指针后length xs - m（即1）个元素 → 结果"bcd"
递归移动指针：
"abcd" → "acd"
"abcd" → "abd"
"abcd" → "abc"
"abcd*" → [""]

你的指针思路本质是递归选择是否包含当前元素，同时控制剩余需要选择的元素数量，可以直接转化为Haskell的递归实现，核心逻辑分三种情况：

核心递归逻辑 #

1. 当m=0时：不管输入列表是什么，只有一种组合——空列表（对应示例comb 0 "abcd" → [""]）
2. 当列表为空时：如果m>0，没有符合条件的组合，返回空列表
3. 正常递归情况：
   • 不包含当前第一个元素：相当于把指针往后移一位，直接从列表尾部选m个元素
   • 包含当前第一个元素：剩下的元素需要从列表尾部选m-1个，把当前元素加到这些组合的前面

把这个逻辑转化为代码（完全匹配你示例的输出顺序）：

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

代码解释 #

• comb 0 _ = [[]]：选0个元素，只有空组合这一种可能
• comb _ [] = []：空列表里无法选出大于0个元素，返回空结果
• comb m (x:xs)：
  • comb m xs：跳过当前元素x，直接从剩余列表xs中选m个元素，对应指针后移的操作
  • map (x:) (comb (m-1) xs)：将x加入到所有从xs中选m-1个元素的组合前，对应指针停在当前位置、保留x并选取后续元素的操作
  • 用++合并两种情况的结果，就是所有符合要求的组合

测试验证 #

运行代码验证示例：

comb 0 "abcd"  -- 输出 [""]
comb 3 "bcd"   -- 输出 ["bcd"]
comb 2 "bcd"   -- 输出 ["cd","bd","bc"]
comb 3 "abcd"  -- 输出 ["bcd", "acd", "abd", "abc"]

内容的提问来源于stack exchange，提问作者Metiwi