在Haskell中实现一个memoization函数 [英] Implementing a memoization function in Haskell

问题描述

我对Haskell相当陌生，我试图实现一个使用 Data.Map 来存储计算值的基本memoization函数。我的例子是Project Euler Problem 15，它涉及到计算20x20网格中从1个角落到另一个角落的可能路径的数量。

I'm fairly new to Haskell, and I'm trying to implement a basic memoization function which uses a Data.Map to store computed values. My example is for Project Euler Problem 15, which involves computing the number of possible paths from 1 corner to the other in a 20x20 grid.

这就是我迄今为止所拥有的。我还没有尝试编译，因为我知道它不会编译。

This is what I have so far. I haven't tried compiling yet because I know it won't compile. I'll explain below.

import qualified Data.Map as Map

main = print getProblem15Value

getProblem15Value :: Integer
getProblem15Value = getNumberOfPaths 20 20

getNumberOfPaths :: Integer -> Integer -> Integer
getNumberOfPaths x y = memoize getNumberOfPaths' (x,y)
where getNumberOfPaths' mem (0,_) = 1
      getNumberOfPaths' mem (_,0) = 1
      getNumberOfPaths' mem (x,y) = (mem (x-1,y)) + (mem (x,y-1))

memoize :: ((a -> b) -> a -> b) -> a -> b
memoize func x = fst $ memoize' Map.Empty func x
    where memoize' map func' x' = case (Map.lookup x' map) of (Just y) -> (y, map)
                                                              Nothing -> (y', map'')
           where y' = func' mem x'
                 mem x'' = y''
                 (y'', map') = memoize' map func' x''
                 map'' = Map.insert x' y' map'

所以基本上，我有这种结构的方式是 memoize 是一个组合符（根据我的理解）。因为 memoize 提供了一个函数（在本例中为 getNumberOfPaths'），函数调用（ mem ），而不是 getNumberOfPaths'调用它自己，这会在第一次迭代后删除记忆。

So basically, the way I have this structured is that memoize is a combinator (by my understanding). The memoization works because memoize provides a function (in this case getNumberOfPaths') with a function to call (mem) for recursion, instead of having getNumberOfPaths' call itself, which would remove the memoization after the first iteration.

我的 memoize 实现了一个函数（在本例中为 getNumberOfPaths' ）和一个初始值（在这种情况下，元组（x，y）代表网格另一个角落的网格单元距离）。它调用 memoize'，它具有相同的结构，但包含一个空的 Map 来保存值，并返回一个包含返回值和新计算的 Map 。 memoize'进行地图查找，并在存在值的情况下返回值和原始地图。如果没有值存在，它会返回计算值和一个新地图。

My implementation of memoize takes a function (in this case getNumberOfPaths') and an initial value (in this case a tuple (x,y) representing the number of grid cell distances from the other corner of the grid). It calls memoize' which has the same structure, but includes an empty Map to hold values, and returns a tuple containing the return value and a new computed Map. memoize' does a map lookup and returns the value and the original map if there is a value present. If there is no value present, it returns the computed value and a new map.

这是我的算法崩溃的地方。为了计算新值，我使用 mem 来调用 func'（ getNumberOfPaths'>） code>和 x'。 mem 只需返回 y''，其中 y''包含在再次调用 memoize'的结果中。 memoize'也返回一个新的地图，然后我们添加新的地图并用作 memoize'

This is where my algorithm breaks down. To compute the new value, I call func' (getNumberOfPaths') with mem and x'. mem simply returns y'', where y'' is contained in the result of calling memoize' again. memoize' also returns a new map, to which we then add the new value and use as the return value of memoize'.

这里的问题在于（y''，map'）= memoize'map func'x''应该在 mem 下，因为它依赖于 x''，它是 MEM 。我当然可以做到这一点，但后来我将失去 map'值，这是我需要的，因为它包含来自中间计算的memoized值。但是，我不想在 mem 的返回值中引入 Map ，因为那么传递给 memoize 必须处理 Map 。

The issue here is that the line (y'', map') = memoize' map func' x'' should be under mem because it's dependent on x'', which is a parameter of mem. I can certainly do that, but then I will lose the map' value, which I need because it contains memoized values from intermediate computations. However, I don't want to introduce the Map into the return value of mem because then the function passed to memoize will have to handle the Map.

听起来很混乱。很多这种超高阶功能的东西让我感到困惑。

Sorry if that sounded confusing. A lot of this ultra-high-order functional stuff is confusing to me.

我确信有一种方法可以做到这一点。我想要的是一个通用的 memoize 函数，它允许递归调用，就像 getNumberOfPaths 的定义一样，其中计算逻辑

I'm sure that there is a way to do this. What I want is a generic memoize function that allows recursive calling exactly like in the definition of getNumberOfPaths, where the computation logic doesn't have to care exactly how the memoization is done.

推荐答案

如果您的输入足够小，您可以执行一件事将备忘表分配为 Array 而不是 Map ，其中包含所有提前结果，但延迟计算：

Provided your inputs are small enough, one thing you can do is allocate the memo table as an Array instead of a Map, containing all the results ahead of time, but calculated lazily:

import Data.Array ((!), array)

numPaths :: Integer -> Integer -> Integer
numPaths w h = get (w - 1) (h - 1)
  where

    table = array (0, w * h)
      [ (y * w + x, go x y)
      | y <- [0 .. h - 1]
      , x <- [0 .. w - 1]
      ]

    get x y = table ! fromInteger (y * w + x)

    go 0 _ = 1
    go _ 0 = 1
    go x y = get (x - 1) y + get x (y - 1)

如果您愿意，还可以将其分成单独的函数：

You can also split this into separate functions if you prefer:

numPaths w h = withTable w h go (w - 1) (h - 1)
  where
    go mem 0 _ = 1
    go mem _ 0 = 1
    go mem x y = mem (x - 1) y + mem x (y - 1)

withTable w h f = f'
  where
    f' = f get
    get x y = table ! fromInteger (y * w + x)
    table = makeTable w h f'

makeTable w h f = array (0, w * h)
  [ (y * w + x, f x y)
  | y <- [0 .. w - 1]
  , x <- [0 .. h - 1]
  ]

我不会为你破坏它，但也有一个非递归公式来解答。

And I won’t spoil it for you, but there’s also a non-recursive formula for the answer.

这篇关于在Haskell中实现一个memoization函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！