Haskell 得到和为X的所有数字
Haskell get all the numbers whose sum is X
我需要在 haskell 中创建一个函数，它接收一个数字和 returns 一个列表列表，其中列表包含数字的所有组合，其总和是接收到的数字。
很难解释所以这就是例子：
sum1 4 = [ [4], [3,1], [2,2], [1,3], [1,1,2], [1,2,1] , [2,1,1] ]
sum1 3 = [ [3], [2,1], [1,2], [1,1,1]
我需要用递归和理解列表来做这个
编辑
这是我的代码：
sum1 n = sum3 (sum2 1 (n-1) n)
sum2 x y n = if ((x+y)==n && x>0 && y>0) then [x,y]:sum2 (x+1) (y-1) n else []
sum3 [] = []
sum3 (x:xs) = sum4 x 1 : sum3 xs
sum4 [] t = []
sum4 (x:xs) t = if not (x == t) then (sum1 x) else x
是的，这是考试的多余部分，但我不知道该怎么做
我假设这是家庭作业（在我看来是一个更难的作业），所以我现在不会破坏所有内容。
如果您考虑一下，您应该会发现基本上有两种操作可以将总和为 n 的列表 xs 转换为总和为 [=15= 的列表]:
- 你可以再添加一个
1
- 您可以将
1 添加到 xs 中的一些 x
因此，如果您设法实现这两个操作，您的任务将会容易得多。
第一个并不难（hint (1:) 是一个函数，在某些列表中添加一个额外的 1 - 现在你必须 地图这个...)
第二个有点难，虽然几乎相同的分而治之的想法会帮助你。
以下是我将如何开始：
add1Somewhere :: Num a => [a] -> [[a]]
add1Somewhere [i] = [[i+1]]
add1Somewhere (i:is) = ???
（是的，这是一个 部分 函数）
备注：
- 正如您在下面看到的那样，您实际上不必在某处插入额外的
1 或在 xs 中选择任何 x - 使用第一个 x xs 并放在首位 就足够了
- 我暗示的算法有时会产生相同的结果 - 例如，如果你有一个
[1,1]，那么你可以通过两种方式在 [2,2] 之后结束：[1,1] -> [2,1] -> [2,2]和 [1,1] -> [1,2] -> [2,2] - 这些可以用 Data.List.nub 删除，或者如果您更改算法以产生 ordered/filtered 结果（不产生 [1,1] -> [1,2]）
- 你的例子遗漏了一些东西
[1,1,1,1]，老实说，我不知道这个练习是否暗示了这样一个顺序
- 你可能应该看看
concatMap（或 concat）
- 这与@cirdec 暗示的算法不同（可能他的算法更快）——但是如果你在某个地方插入一个额外的 1[，同样的重复问题也会出现=126=]
解决方案
因为过了一段时间，你说这是一道老考题，我觉得可以剧透一下（不想继续看下去）
所以这是一个可能的解决方案（不考虑任何性能问题）：
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 和 nub，两者都可能适合也可能不适合。
我希望你明白基本的想法
显然更好的解决方案
糟糕 - 我刚刚注意到您可以摆脱所有 有问题的 函数，如 concat 和 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 上的归纳法（假设只有正自然数）
对于 n=1 只需注意 [1] 是唯一可能的列表
现在假设我们找到 n>0 的所有排列并查看一些列表 xs
总和为 n+1（显然列表需要非空）
现在 xs = x:ys 的第一个元素 x 将是 1 或 >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）
我需要在 haskell 中创建一个函数，它接收一个数字和 returns 一个列表列表，其中列表包含数字的所有组合，其总和是接收到的数字。
很难解释所以这就是例子：
sum1 4 = [ [4], [3,1], [2,2], [1,3], [1,1,2], [1,2,1] , [2,1,1] ]
sum1 3 = [ [3], [2,1], [1,2], [1,1,1]
我需要用递归和理解列表来做这个
编辑
这是我的代码：
sum1 n = sum3 (sum2 1 (n-1) n)
sum2 x y n = if ((x+y)==n && x>0 && y>0) then [x,y]:sum2 (x+1) (y-1) n else []
sum3 [] = []
sum3 (x:xs) = sum4 x 1 : sum3 xs
sum4 [] t = []
sum4 (x:xs) t = if not (x == t) then (sum1 x) else x
是的，这是考试的多余部分，但我不知道该怎么做
我假设这是家庭作业（在我看来是一个更难的作业），所以我现在不会破坏所有内容。
如果您考虑一下，您应该会发现基本上有两种操作可以将总和为 n 的列表 xs 转换为总和为 [=15= 的列表]:
- 你可以再添加一个
1 - 您可以将
1添加到xs 中的一些
x
因此，如果您设法实现这两个操作，您的任务将会容易得多。
第一个并不难（hint (1:) 是一个函数，在某些列表中添加一个额外的 1 - 现在你必须 地图这个...)
第二个有点难，虽然几乎相同的分而治之的想法会帮助你。
以下是我将如何开始：
add1Somewhere :: Num a => [a] -> [[a]]
add1Somewhere [i] = [[i+1]]
add1Somewhere (i:is) = ???
（是的，这是一个 部分 函数）
备注：
- 正如您在下面看到的那样，您实际上不必在某处插入额外的
1或在xs中选择任何x- 使用第一个xxs并放在首位 就足够了 - 我暗示的算法有时会产生相同的结果 - 例如，如果你有一个
[1,1]，那么你可以通过两种方式在[2,2]之后结束：[1,1] -> [2,1] -> [2,2]和[1,1] -> [1,2] -> [2,2]- 这些可以用Data.List.nub删除，或者如果您更改算法以产生 ordered/filtered 结果（不产生[1,1] -> [1,2]） - 你的例子遗漏了一些东西
[1,1,1,1]，老实说，我不知道这个练习是否暗示了这样一个顺序 - 你可能应该看看
concatMap（或concat） - 这与@cirdec 暗示的算法不同（可能他的算法更快）——但是如果你在某个地方插入一个额外的 1[，同样的重复问题也会出现=126=]
解决方案
因为过了一段时间，你说这是一道老考题，我觉得可以剧透一下（不想继续看下去）
所以这是一个可能的解决方案（不考虑任何性能问题）：
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 和 nub，两者都可能适合也可能不适合。
我希望你明白基本的想法
显然更好的解决方案
糟糕 - 我刚刚注意到您可以摆脱所有 有问题的 函数，如 concat 和 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 上的归纳法（假设只有正自然数）
对于 n=1 只需注意 [1] 是唯一可能的列表
现在假设我们找到 n>0 的所有排列并查看一些列表 xs
总和为 n+1（显然列表需要非空）
现在 xs = x:ys 的第一个元素 x 将是 1 或 >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）