Haskell的记忆递推功能

Question

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

编写一个函数'howSum( targetSum，numbers)‘，它接受一个targetSum和一个数字数组作为参数。该函数应该返回一个数组，该数组包含任何元素的组合，这些元素加起来正好等于targetSum。如果没有与targetSum相加的组合，则返回null。如果可能有多个组合，则可以返回任何一个组合。

我得到的是所有可能的数字组合。

该函数的工作方式是创建一个递归树，其中第一个调用具有总和，target和concatMap为每个数字创建一个分支，并提供所需的剩余和。如果达到target为0，那么要获得的分支是从nums中减去数字的组合，这意味着您可以在nums中使用数字求和到目标。当返回时，在该节点上的值的结果被连接(到每个子列表)。

根据我的测试，该功能正常工作，但回忆录没有。我现在知道，memo (Map对象)在我的尝试中是无用的，因为它是不可变的，对howSumMemo的单独调用只能访问递归树中祖先的已兑现的值。如果备忘录是可变的和可引用的(在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。

Answer 1

当尝试以功能方式实现有状态的东西时，所有其他方法都失败了，您可以始终使用State。下面是一个使用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

回忆录数据结构仍然是一张地图。recurse函数完成了大部分的繁重工作。

它首先尝试在地图中lookup结果。Map.lookup的结果是一个Maybe值。如果它是一个Just值，它意味着结果已经在映射中，所以只需返回它。

如果lookup返回一个Nothing值，则调用howSumState以生成res值，将其放入映射中并返回。

您可以通过计算状态值来创建一个回忆录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'函数，我们可以使用它作为一个测试神谕。我编写了一个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个测试，所有测试都通过。