list - Haskell 得到一个过滤的整数列表

Question

设想:
如果有一个整数数组，我想得到整数数组作为返回，它们的总数不应超过 10。

我是 Haskell 的初学者，并在下面尝试过。如果有人能纠正我，将不胜感激。

numbers :: [Int]
numbers = [1,2,3,4,5,6,7,8,9,10, 11, 12]

getUpTo :: [Int] -> Int -> [Int]
getUpTo (x:xs) max =
    if max <= 10
    then
            max = max + x
            getUpTo xs max
    else
            x

输入

getUpTo numbers 0

预期产出

[1,2,3,4]

Answer 1

当心:这不是背包问题的解决方案:)

我想出的一个非常快速的解决方案是以下一个。当然，解决完整的背包问题会更难，但如果您只需要一个快速的解决方案，这应该可行:

import Data.List (sort)

getUpTo :: Int -> [Int] -> [Int]
getUpTo max xs = go (sort xs) 0 []
    where
        go [] sum acc         = acc
        go (x:xs) sum acc
            | x + sum <= max  = go xs (x + sum) (x:acc)
            | otherwise       = acc

通过在其他所有事情之前对数组进行排序，我可以从顶部一个接一个地取出项目，直到超过最大值；然后返回建立到该点的列表。

编辑:作为旁注，我交换了前两个参数的顺序，因为这种方式对于部分应用程序应该更有用。