我有一个试图解决这个问题的 haskell 函数:

Write a function 'howSum(targetSum, numbers)' that takes in a targetSum and an array of numbers as arguments. The function should return an array containing any combination of elements that add up to exactly the targetSum. If there is no combination that adds up to the targetSum, then return null. If there are multiple combinations possible, you may return any single one.

我所返回的是所有可能的数字组合。

该函数通过创建一个递归树来工作，其中第一个调用具有总和、target，并且 concatMap 为每个数字创建一个分支以及所需的剩余总和。如果这达到了 0 的 target，到达那里的分支是从 nums 中减去数字的组合，这意味着您可以在 nums 中使用数字> 总结为目标。当返回结果时，该节点处的值被连接起来(到每个子列表)。

根据我的测试，该功能可以正常工作，但无法内存。我现在知道 memo(Map 对象)在我的尝试中毫无用处，因为它是不可变的，并且对 howSumMemo 的单独调用只能访问作为祖先的兑现值递归树。如果 memo 是可变的和引用的(这在 Haskell 中是不可能的)，它就会工作。

import Data.Map (Map, member, findWithDefault, empty, insert)
howSumMemo :: Int -> [Int] -> Map Int [[Int]] -> [[Int]]
howSumMemo target nums memo
    | target > 0 = findWithDefault val target $ insert target val memo
    | target < 0 = []
    | otherwise = [[]]
    where val = concatMap (\x -> map (x :) (howSumMemo (target-x) nums memo)) nums

-- Memoized howSum
howSum target nums = howSumMemo target nums empty


-- Normal howSum
howSum' :: Int -> [Int] -> [[Int]]
howSum' target nums
    | target > 0 = concatMap (\x -> map (x :) (howSum' (target-x) nums)) nums
    | target < 0 = []
    | otherwise = [[]]

我怎样才能让内存为 howSum 工作？我试过引用 https://wiki.haskell.org/Memoization .

最佳答案

当尝试以函数式方式实现有状态的东西时，如果所有其他方法都失败了，您始终可以使用 State monad。这是一个使用来自 transformers 的 Control.Monad.Trans.State.Strict 的版本:

howSumState :: Int -> [Int] -> State (Map Int [[Int]]) [[Int]]
howSumState target nums
    | target > 0 = join <$> traverse (\x -> fmap (x :) <$> recurse (target - x)) nums
    | target < 0 = return []
    | otherwise = return [[]]
    where recurse x = do
            m <- gets $ Map.lookup x
            case m of
              Just res -> return res
              Nothing -> do
                res <- howSumState x nums
                modify (Map.insert x res)
                return res

内存数据结构仍然是一张 map 。 recurse 函数完成了大部分繁重的工作。

它首先尝试在 map 中查找结果。 Map.lookup 的结果是一个 Maybe 值。如果是Just值，说明结果已经在map中了，直接返回即可。

如果lookup 返回一个Nothing 值，调用howSumState 以生成result，将它插入到 map 中，并返回它。

您可以通过评估 State 值创建一个内存howSum 函数:

-- Memoized howSum
howSum :: Int -> [Int] -> [[Int]]
howSum target nums = evalState (howSumState target nums) Map.empty

evalState 只返回最终值。如果您还想查看已建立的状态，可以使用 runState:

ghci> runState (howSumState 3 [1,2]) Map.empty
([[1,1,1],[1,2],[2,1]],fromList [(-1,[]),(0,[[]]),(1,[[1]]),(2,[[1,1],[2]])])

元组的第一个元素是结果:

[[1,1,1],[1,2],[2,1]]

元组的第二个元素是 map ，这里为了便于阅读而格式化:

Map.fromList [
    (-1, []),
    (0, [[]]),
    (1, [[1]]),
    (2, [[1,1],[2]])]

每个值都是一个元组，其中第一个元素是键，第二个元素是值。

由于我们还有非记忆化的howSum' 函数，我们可以将其用作test oracle。 .我写了一个QuickCheck -based 属性来验证两个实现是否返回相同的值:

testProperty "Both implementations behave the same" (withMaxSuccess 10000 (do
    target <- resize 10 arbitrary
    nums <- fmap getPositive <$> arbitrary

    let actual = howSum target nums

    let expected = howSum' target nums
    return $ expected === actual))

此属性运行 10,000 次测试，全部通过。

https://stackoverflow.com/questions/72918195/