Data.MemoCombinators如何工作？

Question

我一直在寻找Data.MemoCombinators的来源,但我无法真正看到它的核心位置.

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

我正在寻找这个实现的细节,并可选择与其他Haskell方法进行比较/对比来进行memoization.我理解什么是memoization,而不是在寻找它的工作原理.

Answer 1

该库是众所周知的记忆技术的直接组合.让我们从规范的例子开始:

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并返回相同函数的memoized版本.任何在语义上都具有此类型且具有此类型的函数称为"memoizer for Int"(即使id,它也不会记忆).我们推广到这个抽象:

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

因此Memo a,一个memoizer for a,将函数从a任何东西中取出,并返回一个已被记忆(或不记忆)的语义相同的函数.

不同的memoizers的想法是找到一种方法来使用数据结构枚举域,将函数映射到它们,然后索引数据结构. bool是一个很好的例子:

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

函数from Bool等价于对,除了一对只会评估每个组件一次(就像在lambda之外发生的每个值的情况一样).所以我们只是映射到一对和后面.关键点在于我们table通过枚举域来提升对lambda的函数的评估(这里是最后一个参数).

Memoizing Maybe a是一个类似的故事,但现在我们需要知道如何memoize的a的Just情况.所以memoizer Maybe将memoizer a作为参数:

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上公开一个开放的fixpoint函数:

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

这允许更多的灵活性,例如.清除高速缓存,LRU等.但是使用它是一种痛苦,并且它还对要记忆的函数施加严格限制(例如,没有无限的左递归).我不相信有任何库实现这种技术.

这回答了你的好奇吗？如果没有,或许明确指出你感到困惑的一点？

Answer 2

心是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价值的功能(除了微不足道).它使用与本页中有关Haskell memoization 的相同想法.第2节显示了使用列表的最简单的memoization策略,第3节使用类似于IntTreememocombinators中使用的自然二叉树来完成相同的操作.

基本思想是使用像(map fib [0 ..] !!)memocombinators一样的结构 - IntTrie.apply (fmap f IntTrie.identity).这里要注意的事情是之间的对应关系IntTie.apply和!!与之间也IntTrie.identity和[0..].

下一步是使用其他类型的参数记忆函数.这是通过wrap使用类型之间的同构a并从a b构造a 的函数来完成Memo b的Memo 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和memoizing多个参数等类型.

Answer 3

一些工作由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一个数据结构中获取一个函数并将其映射到由所有可能的值索引a并包含其值的数据结构b.这样的数据结构应该以两种方式延迟 - 首先它应该是它所持有的值的惰性.其次,应该懒得自己制作.前者默认使用非严格语言.后者通过使用广义尝试来完成.

memocombinators,memotrie等的各种方法都只是创建各种类型的数据结构的尝试组合的方法,以允许简单构建对越来越复杂的结构的尝试.