我假设这是一份家庭作业（在我看来，这是一项更难的作业），所以我现在不会破坏一切。
如果您考虑一下，您应该会发现基本上有两种操作可以从列表中获取xs总和就是n到一个列表，总和为n+1:
- 你可以添加另一个
1
- 你可以加
1对某些人x in xs
因此，如果您设法实现这两项操作，您的任务就会容易得多。
第一个并不难（hint (1:)是一个在前面附加一个函数1到一些清单 - 现在你必须map这...）
第二个有点难，尽管几乎相同的分而治之的想法会帮助你。
我将这样开始：
add1Somewhere :: Num a => [a] -> [[a]]
add1Somewhere [i] = [[i+1]]
add1Somewhere (i:is) = ???
（是的，这是一个partial功能）
remarks:
- 正如您在下面看到的，您实际上不必插入额外的
1某处或选择任何x in xs- 使用第一个x in xs并放在第一位确实足够了
- 我暗示的算法有时会产生相同的结果 - 例如，如果你有一个
[1,1]那么你可以结束于[2,2]后来通过两种方式：[1,1] -> [2,1] -> [2,2] and [1,1] -> [1,2] -> [2,2]- 这些可以通过删除Data.List.nub或者如果您更改算法以生成排序/过滤结果（不生成[1,1] -> [1,2])
- 你的例子缺少一些东西
[1,1,1,1]老实说，我无法判断这个练习是否暗示了这样一个命令
- 你可能应该看看
concatMap (or concat)
- 这与 @cirdec 暗示的算法不同（可能他的速度更快） - 但如果你在某个地方额外插入1
solution
因为已经有一段时间了，而且你说这是一个旧的考试问题，我认为破坏它是可以的（如果你不想，请不要继续阅读）
所以这是一个可能的解决方案（不关心任何性能问题）：
import Data.List (nub)
sum1 :: (Eq a, Num a) => a -> [[a]]
sum1 1 = [[1]]
sum1 n = nub $ concatMap add1Somewhere ns ++ map (1:) ns
where ns = sum1 (n-1)
add1Somewhere :: Num a => [a] -> [[a]]
add1Somewhere [i] = [[i+1]]
add1Somewhere (i:is) = ((i+1):is) : map (i:) (add1Somewhere is)
请注意，这使用concatMap and nub两者都可能适合也可能不适合。
我希望你能明白基本的想法
显然更好的解决方案
哎呀 - 我刚刚注意到你可以摆脱所有有问题的功能类似于concat and nub无论如何，因为只需在前面添加一个就足够了1或者增加第一个列表元素 - 无论如何，递归将提供所有需要的排列（我提到的不同路径正是排列） -虽然顺序有区别:
sum1 :: (Eq a, Num a) => a -> [[a]]
sum1 1 = [[1]]
sum1 n = map add1 ns ++ map prep1 ns
where ns = sum1 (n-1)
prep1 is = 1:is
add1 (i:is) = (i+1):is
当然你可以更换map如果你愿意的话可以使用列表理解
证明这找到了所有排列
通过感应n（假设只有正自然数）
for n=1请注意[1]是唯一可能的列表
现在假设我们找到了所有排列n>0看看一些清单xs总结起来就是n+1（显然列表必须非空）
现在第一个元素x of xs = x:ys将是1 or >1
-
x=1- 在这种情况下prep1会提供xs因为ys我们的算法通过归纳法发现了（注意sum ys = sum xs - 1 = n)
-
x>1- 在这种情况下(x-1):ys我们的算法通过归纳法发现了add1将创造xs（再次因为sum ((x-1):ys) = sum xs - 1 = n)
