数据如何。MemoCombinators工作？

StackOverflow https://stackoverflow.com/questions/4980102

题

我一直在寻找消息来源 数据。记忆传播者 但我真的看不到它的核心在哪里。

请向我解释所有这些组合器背后的逻辑是什么 机械师 他们是如何在现实世界的编程中加速你的程序的。

我在寻找细节 这 实现，并可选地与其他Haskell记忆方法进行比较/对比。我明白什么是记忆，我是 不是 寻找它是如何工作的一般描述。

有帮助吗？

解决方案

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

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 到任何东西，并返回一个语义上相同的函数，该函数已被记忆（或没有）。

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

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

功能从 Bool 它们等价于对，除了对只会对每个组件求值一次（就像lambda之外的每个值一样）。所以我们只是映射到一对并返回。关键的一点是，我们将函数的计算提升到lambda上方的参数（这里是 table)通过枚举域。

记忆化 Maybe a 是一个类似的故事，除了现在我们需要知道如何记忆 a 为 Just 案例。所以记忆器 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..].这有点涉及，但基本上只是创建一个无限树（表示二进制中的数字以阐明结构）:

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

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

正如sclv所指出的那样，Conal的MemoTrie库使用相同的底层技术，但使用typeclass表示而不是combinator表示。我们在同一时间独立发布了我们的图书馆（事实上，在几个小时内！).Conal's在简单的情况下更容易使用（只有一个函数, 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等。但是使用起来很麻烦，而且它对要记忆的函数施加了严格的约束（例如没有无限的左递归）。我不相信有任何实现这种技术的库。

这回答了你的好奇吗？如果没有，也许明确你感到困惑的要点？

其他提示

心是 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节使用列表显示了最简单的记忆策略，第3节使用类似于 IntTree 在memocombinators中使用。

基本思想是使用像 (map fib [0 ..] !!) 或者在memocombinators案例中 - IntTrie.apply (fmap f IntTrie.identity).这里要注意的是两者之间的对应关系。 IntTie.apply 和 !! 而且还在 IntTrie.identity 和 [0..].

下一步是使用其他类型的参数记忆函数。这是用 wrap 在类型之间使用同构的函数 a 和 b 建造一个 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这样的类型，也许，或者记忆多个参数。

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

卢克的图书馆是康纳尔的MemoTrie图书馆的变体，他在这里描述了这一点: http://conal.net/blog/posts/elegant-memoization-with-functional-memo-tries/

进一步的扩展--函数记忆背后的一般概念是从 a -> b 并将其映射到由 一切可能 的价值 a 并包含的值 b.这样的数据结构应该在两个方面懒惰-首先它应该在它所持有的值中懒惰。其次，它应该是懒惰的生产本身。前者默认为非约束语言。后者是通过使用广义尝试来完成的。

Memocombinators，memotrie等的各种方法都只是在单个类型的数据结构上创建尝试片段的组合，以便为日益复杂的结构简单地构建尝试。

@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 6 时未能重新计算 FIB 5 。对我来说，备忘录组合者是否具有相同的行为（即顶级备忘，而不是仅禁止重新计算“在FIB计算中），而且如果是，为什么？

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top