我对 Haskell 相当陌生,我正在尝试实现一个基本的记忆功能,它使用Data.Map
存储计算值。我的示例是欧拉项目问题 15,其中涉及计算 20x20 网格中从一个角到另一个角的可能路径数。
这是我到目前为止所拥有的。我还没有尝试编译,因为我知道它不会编译。下面我会解释一下。
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'
调用自身,这将在第一次迭代后删除记忆。
我的实施memoize
接受一个函数(在本例中getNumberOfPaths'
)和一个初始值(在本例中是一个元组(x,y)
表示距网格另一个角的网格单元距离的数量)。它调用memoize'
它具有相同的结构,但包含一个空的Map
保存值,并返回一个包含返回值和新计算值的元组Map
. memoize'
进行映射查找并返回该值和原始映射(如果存在值)。如果不存在值,则返回计算值和新映射。
这就是我的算法崩溃的地方。为了计算新值,我调用func'
(getNumberOfPaths'
) with mem
and x'
. mem
只是返回y''
, where y''
包含在调用结果中memoize'
again. memoize'
还返回一个新的映射,然后我们向其中添加新值并用作memoize'
.
这里的问题是该行(y'', map') = memoize' map func' x''
应该在mem
因为它依赖于x''
,这是一个参数mem
。我当然可以做到,但那样我就会失去map'
value,我需要它,因为它包含来自中间计算的记忆值。不过我不想介绍Map
返回值mem
因为然后函数传递给memoize
将不得不处理Map
.
抱歉,如果这听起来令人困惑。很多超高阶函数的东西让我感到困惑。
我确信有办法做到这一点。我想要的是一个通用的memoize
允许递归调用的函数与定义中完全相同getNumberOfPaths
,其中计算逻辑不必确切关心记忆是如何完成的。