38

我一直在寻找Data.MemoCombinators的来源，但我真的看不出它的核心在哪里。

请向我解释所有这些组合器背后的逻辑以及它们如何实际工作以在现实世界编程中加速您的程序的机制。

我正在寻找此实现的细节，并可选择与其他 Haskell 记忆方法进行比较/对比。我了解什么是记忆化，而不是在寻找关于它一般如何工作的描述。

4

4 回答 4

59

这个库是众所周知的记忆技术的直接组合。让我们从典型的例子开始：

fib = (map fib' [0..] !!)
    where
    fib' 0 = 0
    fib' 1 = 1
    fib' n = fib (n-1) + fib (n-2)

我将您所说的解释为您知道这是如何以及为什么起作用的。所以我将专注于组合化。

我们基本上是在试图捕捉和概括(map f [0..] !!). 这个函数的类型是(Int -> r) -> (Int -> r)，这是有道理的：它从一个函数中获取Int -> r并返回同一个函数的记忆版本。任何在语义上是身份并具有这种类型的函数都称为“memoizer for Int”（甚至id，它不记忆）。我们推广到这个抽象：

type Memo a = forall r. (a -> r) -> (a -> r)

所以 a Memo a，一个 memoizer for a，从任何东西中获取一个函数a，并返回一个语义相同的函数，该函数已被记忆（或未记忆）。

不同记忆器的想法是找到一种方法来枚举具有数据结构的域，将函数映射到它们上，然后索引数据结构。 bool是一个很好的例子：

bool :: Memo Bool
bool f = table (f True, f False)
    where
    table (t,f) True = t
    table (t,f) False = f

函数 fromBool等价于对，除了一对只会评估每个组件一次（就像出现在 lambda 之外的每个值的情况一样）。所以我们只是映射到一对并返回。要点是，我们table通过枚举域来提升参数（这里是 的最后一个参数）的 lambda 之上的函数评估。

记忆Maybe a是一个类似的故事，除了现在我们需要知道如何记忆a这个Just案例。所以 memoizer forMaybe将 memoizer fora作为参数：

maybe :: Memo a -> Memo (Maybe a)
maybe ma f = table (f Nothing, ma (f . Just))
    where
    table (n,j) Nothing = n
    table (n,j) (Just x) = j x

图书馆的其余部分只是这个主题的变体。

它记忆整数类型的方式使用了比[0..]. 它有点复杂，但基本上只是创建了一个无限树（以二进制表示数字以阐明结构）：

1
  10
    100
      1000
      1001
    101
      1010
      1011
  11
    110
      1100
      1101
    111
      1110
      1111

因此，在树中查找数字的运行时间与其表示中的位数成正比。

正如 sclv 所指出的，Conal 的 MemoTrie 库使用相同的底层技术，但使用类型类表示而不是组合表示。我们同时独立发布了我们的库（实际上，在几个小时内！）。Conal 更容易在简单的情况下使用（只有一个函数 ，memo它会根据类型确定要使用的备忘录结构），而我的更灵活，因为您可以执行以下操作：

boundedMemo :: Integer -> Memo Integer
boundedMemo bound f = \z -> if z < bound then memof z else f z
   where
   memof = integral f

它只记住小于给定界限的值，这是实现项目欧拉问题之一所需的。

还有其他方法，例如在 monad 上公开一个开放的定点函数：

memo :: MonadState ... m => ((Integer -> m r) -> (Integer -> m r)) -> m (Integer -> m r)

这允许更大的灵活性，例如。清除缓存、LRU 等。但使用起来很麻烦，而且它对要记忆的函数施加了严格的限制（例如，没有无限左递归）。我不相信有任何库可以实现这种技术。

这是否回答了你好奇的问题？如果不是，也许明确指出您感到困惑的点？

于 2011-02-12T21:48:58.320 回答
18

心脏是bits功能：

-- | Memoize an ordered type with a bits instance.
bits :: (Ord a, Bits a) => Memo a
bits f = IntTrie.apply (fmap f IntTrie.identity)

它是唯一unit :: Memo ()可以给你一个Memo a值的函数（除了 trivial ）。它使用与此页面中有关 Haskell 记忆的相同想法。第 2 节展示了使用列表的最简单的记忆策略，第 3 节使用类似于IntTreememocombinators 中使用的自然二叉树来做同样的事情。

(map fib [0 ..] !!)基本思想是在 memocombinators 的情况下使用类似or 的结构 - IntTrie.apply (fmap f IntTrie.identity)。这里要注意的是 和 之间的对应关系IntTie.apply以及!!和 之间IntTrie.identity的对应关系[0..]。

下一步是使用其他类型的参数来记忆函数。这是通过wrap使用类型之间的同构a并从 ab构造 a的函数来完成的。例如：Memo bMemo a

Memo.integral f
=>
wrap fromInteger toInteger bits f
=>
bits (f . fromInteger) . toInteger
=>
IntTrie.apply (fmap (f . fromInteger) IntTrie.identity) . toInteger
~> (semantically equivalent)
(map (f . fromInteger) [0..] !!) . toInteger

源代码的其余部分处理诸如 List、Maybe、Either 之类的类型以及记忆多个参数。

于 2011-02-12T21:20:14.713 回答
7

部分工作由 IntTrie 完成：http: //hackage.haskell.org/package/data-inttrie-0.0.4

Luke 的库是 Conal 的 MemoTrie 库的变体，他在此描述了该库：http: //conal.net/blog/posts/elegant-memoization-with-functional-memo-tries/

一些进一步的扩展——函数式记忆背后的一般概念是从一个数据结构中获取一个函数，并将其映射到一个数据结构中，该数据结构由 的所有可能值a -> b索引并包含. 这样的数据结构应该在两个方面是惰性的——首先它应该在它所持有的值上是惰性的。二是自己懒惰生产。前者默认使用非严格语言。后者是通过使用广义尝试来完成的。ab

memocombinators、memotrie 等的各种方法都只是在单个类型的数据结构上创建尝试片段组合的方法，以允许为越来越复杂的结构简单构造尝试。

于 2011-02-12T19:50:31.100 回答
0

@luqui 我不清楚的一件事：这是否具有与以下相同的操作行为：

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

上面应该在顶层记住 fib ，因此如果你定义了两个函数：

f n = fib!!n + fib!!(n+1)

如果我们然后计算f 5，我们得到fib 5在计算fib 6时没有重新计算。我不清楚 memoization 组合器是否具有相同的行为（即顶级 memoization 而不是仅禁止 fib 计算“内部”的重新计算），如果是，为什么？

于 2011-02-14T13:05:47.020 回答