Data.MemoCombinators是如何工作的？

Question

Data.MemoCombinators是如何工作的？

haskellmemoizationcombinators

39

我一直在查看Data.MemoCombinators的源代码，但我真的看不出它的核心是哪里。

请解释一下所有这些组合器背后的逻辑以及它们如何在实际编程中工作来加速你的程序。

我正在寻找这个实现的特定细节，并可选地将其与其他Haskell记忆化方法进行比较/对比。我理解什么是记忆化，不需要描述它如何在一般情况下工作。

- Dan Burton

4个回答

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值。它使用与这个page有关Haskell记忆化的相同思想。第2节展示了使用列表的最简单的记忆化策略，第3节则使用类似于memocombinators中使用的自然数二叉树的二叉树来执行相同的操作。

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

下一步是记忆具有其他类型参数的函数。这是使用wrap函数完成的，该函数使用类型a和b之间的同构来从Memo a构造一个Memo b。例如：

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和记忆化多个参数之类的类型。

- Daniel

这个回答并没有得到很多赞，但实际上非常有建设性，是对luqui的回答的很好的补充。 - Dan Burton

@Dan：我早就预料到会发生这种情况了，毕竟他是这个包的作者 :) - Daniel

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的函数映射到一个数据结构上，该数据结构以所有可能的a值为索引，并包含b的值。这样的数据结构应该在两个方面都是惰性的--首先，它应该在它所持有的值上是惰性的。其次，它本身应该是惰性生成的。前者在非严格语言中默认存在。后者通过使用广义tries来实现。

memocombinators、memotrie等各种方法都只是创建单个数据结构类型的pieces组合的方式，以允许为越来越复杂的结构简单地构建tries。

- sclv

这里的链接非常棒，可以更深入地了解技术细节（实际上它们并不可怕，你只需学习一些新词汇）。 - Dan Burton

0

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

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

以上应该在顶层记忆化斐波那契数列，因此如果您定义了两个函数：

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

如果我们计算f 5，则在计算fib 6时不会重新计算fib 5。我不清楚备忘录组合器是否具有相同的行为（即顶层备忘录而不仅仅是禁止“内部”斐波那契计算中的重新计算），如果是这样，为什么呢？

- jejansse

你的语法有误。f n = (fib !! n) + (fib !! (n + 1)) -- 你的 fib 不是一个函数，而是一个惰性列表。Luqui 的方法将索引操作封装起来。这意味着他的顶层是一个函数，而不是一个常量应用形式，因此在调用之间不会被记忆化。然而，这并不是方法的缺陷，只是一种教学简化。 - sclv

好的，我修复了那个小错误。我并不是想表明那是一个缺陷，我只是想知道它是否相同。特别是因为 Reddit 上有人建议 fib 是处于常量应用形式（而你好像与之矛盾？）。 - jejansse

@sclv，那不正确。fib顶部的列表以及在组合化记忆化的斐波那契中的数据结构都在零个lambda之下，因此它将在顶层和调用之间进行记忆化。尝试在实现中将fib更改为fib'以使其变慢，并查看其行为！ - luqui

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- luqui · Accepted Answer

这个库是一个明确的组合记忆化技术的例子。让我们从经典的例子开始：

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到函数，并返回同一函数的记忆版本。任何在语义上等同于身份且具有此类型的函数都称为“Int的记忆器”（即使是不记忆的id也是如此）。我们将其推广到这个抽象层面：

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

因此，Memo a，即a的记忆化器，接受一个从a到任意类型的函数，并返回一个在语义上相同但已被记忆化（或未被记忆化）的函数。

不同的记忆化器的想法是找到一种枚举域的方式，使用数据结构映射函数，然后索引数据结构。bool是一个很好的例子：

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

< p >来自Bool的函数等效于对，只是对只会评估每个组件一次（与出现在lambda之外的每个值的情况相同）。所以我们只需映射到对并返回。重要的是，我们通过枚举域将函数的评估提升到参数的lambda之上（这里是table的最后一个参数）。

记忆化Maybe a是一个类似的故事，只是现在我们需要知道如何为Just情况记忆化a。因此，Maybe的记忆器将一个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..]更合适。虽然有点复杂，但基本上只是创建了一棵无限的树（用二进制表示数字以阐明结构）：

为了使在树中查找一个数字的运行时间与其表示中的位数成比例。

正如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

这是一个只缓存小于给定边界值的值的函数，需要用于解决Project Euler问题中的一个实现。

还有其他方法，例如在单子上公开一个开放的不动点函数：

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

这使得它更加灵活，例如可以清除缓存、LRU等。但使用起来很麻烦，而且还会对要进行记忆化的函数施加严格的约束（例如不能有无限的左递归）。我不认为有任何库实现了这种技术。

这回答了你的好奇心吗？如果没有，请明确你困惑的点是什么？