关于记忆/评估的 Haskell 问题

Question

我正在尝试在 Haskell 中编写“如何使用最少的硬币amount来访问各种面额的硬币”功能。coins我用 DFS 实现了这个，它可以工作，但速度太慢了。在Python（我的主要语言）中，我可以记住结果并让相同的算法运行得非常快。我尝试在 Haskell 中做同样的事情，但收效甚微。

我将给出一个问题的玩具版本，我试图理解记忆化，然后向 DFS 展示我实际上试图记忆化的情况。

玩具问题

从Haskell Wiki 的 memoization 页面来看，实现此目的的一种方法是索引到无限列表中。类似的要点。

memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
   where fib 0 = 0
         fib 1 = 1
         fib n = memoized_fib (n-2) + memoized_fib (n-1)

这对我来说很有意义——常规递归关系调用记忆列表的索引，如果有的话，它会给出值，并且可以回退到辅助函数。：竖起大拇指：

一个小的修改就打破了这个：

memoized_fib :: Int -> Integer
memoized_fib n = (map fib [0 ..] !! n)  -- now no longer lazily evaled!
   where fib 0 = 0
         fib 1 = 1
         fib n = memoized_fib (n-2) + memoized_fib (n-1)

-- these are not lazily eval'ed either
-- memoized_fib n = (map fib [0 ..] !! ) n
-- memoized_fib  = (\n -> map fib [0 ..] !! n) 

如果我只是想实现斐波那契数列，我可以将!!必须​​保留部分作为生活规则并忽略它。我试图更好地理解这一点，因为我的函数仅对一个参数进行递归，并且!!“无点”具有挑战性。

我的非记忆版本

这是我编写的非记忆代码，希望它是不言自明的：

import Data.List

smallestMaybeList :: Maybe [Integer] -> Maybe[Integer] -> Maybe[Integer]
smallestMaybeList (Just a) Nothing = (Just a)
smallestMaybeList Nothing (Just b) = (Just b)
smallestMaybeList Nothing Nothing = Nothing
smallestMaybeList (Just a) (Just b) = if (length a) < (length b) then (Just a) else (Just b)


makeChange :: Integer -> [Integer] -> Maybe [Integer]
makeChange 0 _ = Just []
makeChange _ [] = Nothing
makeChange amount coins
  | amount < 0 = Nothing
  | amount `elem` coins = Just [amount]
  | otherwise = foldl' smallestMaybeList Nothing [(++) [c] <$> makeChange (amount-c) remCoin | c <- remCoin]
      where remCoin = [c | c <- coins, c < amount]

对于我的（尝试）记忆版本，我放弃了对硬币的递归，只使用不大于当前金额的面额，并拥有这个（仍在热切评估）

import Data.List

--smallestMaybeList :: Maybe [Integer] -> Maybe[Integer] -> Maybe[Integer]
smallestMaybeList (Just a) Nothing = (Just a)
smallestMaybeList Nothing (Just b) = (Just b)
smallestMaybeList Nothing Nothing = Nothing
smallestMaybeList (Just a) (Just b) = if (length a) < (length b) then (Just a) else (Just b)

makeChange :: Integer -> [Integer] -> Maybe [Integer]
makeChange 0 coins = Just []
makeChange amount coins
  | amount < 0 = Nothing
  | otherwise = [mch a coins | a <- [0..]] !! (fromInteger amount)

-- this is "make change helper"
mch :: Integer -> [Integer] -> Maybe [Integer]
mch 0 _ = Just []
mch _ [] = Nothing
mch amount coins
  | amount < 0 = Nothing
  | amount `elem` coins = Just [amount]
  | otherwise = foldl' smallestMaybeList Nothing [(++) [c] <$> makeChange (amount-c) coins | c <- coins]

我尝试过其他变体，其中辅助函数是内联/嵌套的，但没有太大区别。

索引到无限列表的想法fib似乎比无限列表技巧更普遍zipWith，但即使在一个玩具问题上，我也很快陷入困境。

问题：

1. 为什么从无点变量到命名变量的转换会从惰性求值变为急切求值？
2. 关于如何记住我当前的算法的建议？

Answer 1

为什么从无点变量到命名变量的转换会从惰性求值变为急切求值？

这并不是要让程序变得无点，而是要在函数之外定义记忆列表。这是一次性创建列表与让每个递归调用创建一个新列表并因此不重用先前调用的工作之间的区别。

具体来说，对于斐波那契，操作符部分脱糖为

mamoized_fib = let fiblist = map fib [0..] in \n -> fiblist !! n

其中列表fiblist是在 lambda 外部定义的，因此它在提供任何参数之前就存在。如果你改为写

fib n = map fib [0..] !! n

那么列表是在 lambda 内部定义的，因此只有在应用函数时才能访问该列表，因此每个递归调用都会生成自己的新列表。

目标是记住Int -> asome类型的递归函数a，假设Ints 为正（参数可能是其他东西，您必须使用与列表不同的数据结构）。因此，首先您必须重写代码以使递归函数具有该类型。特别是，您应该将硬币列表变成“全局”参数，而不是在每次递归调用时携带它。let然后可以在or子句中本地定义实际的递归函数where。

import Data.Function
import Data.Foldable

makeChange :: [Int] -> Int -> [Int]
makeChange coins = make
  where
    make :: Int -> [Int]
    make 0 = []
    make amount = minimumBy (compare `on` sum) [ c : make (amount - c) | c <- coins, c <= amount ]

我们想要记住make。一旦将其编写为函数Int -> [Int]，该过程就非常简单。

1. 将结果放入列表中

    makeList = make <$> [0..]
   

2. 通过索引到列表来定义（将是什么）记忆函数

    memoMake :: Int -> [Int]
    memoMake n = makeList !! n
   

   (makeList !!)再次注意，是否使用运算符部分 ( ) 或不使用 ( )并不重要\n -> makeList !! n，只是列表是在索引范围之外定义的n。（只有在内联之后makeList，运算符部分才会产生影响。）

3. 先前调用的位置make（即除 中之外的所有位置makeList）将调用更改为make调用memoMake。这里出现了两次（一次出现在 的主体中makeChange，一次出现在 的主体中make）。

import Data.Function
import Data.Foldable

makeChange :: [Int] -> Int -> [Int]
makeChange coins = memoMake
  where
    make :: Int -> [Int]
    make 0 = []
    make amount = minimumBy (compare `on` sum) [ c : memoMake (amount - c) | c <- coins, c <= amount ]
    makeList :: [[Int]]
    makeList = make <$> [0 ..]
    memoMake :: Int -> [Int]
    memoMake n = makeList !! n