如何在Haskell中无导入递归生成n长度1~n元素组合列表？

你当前的代码generate n = [replicate n _ | _ <- [1..n]]存在逻辑问题：它只能生成n个所有元素完全相同的列表，比如n=3时仅返回[[1,1,1],[2,2,2],[3,3,3]]，完全不符合需求中“所有由1到n元素组成的长度为n的列表集合”的要求。

要实现正确的递归版本，我们可以通过分解问题来构建：

1. 递归基例：当n=0时，唯一符合条件的长度为0的列表是空列表，因此：

   generate 0 = [[]]
   

2. 递归步骤：对于n>0的情况，长度为n的所有列表，本质是在长度为n-1的所有合法列表的前面，分别添加1到n中的每一个数。基于这个逻辑，递归式可以写成：

   generate n = [x : xs | x <- [1..n], xs <- generate (n-1)]
   

验证示例 #

当调用generate 3时，递归过程会逐步构建所有组合：

• 先计算generate 2得到[[1,1],[1,2],[2,1],[2,2]]
• 再给每个子列表前分别添加1、2、3，最终得到题目要求的27个列表，与示例输出完全一致。

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