Data.MemoCombinators如何工作？
我一直在寻找Data.MemoCombinators的来源，但是我无法真正看到它的核心在哪里。
请向我解释一下这些组合器背后的逻辑以及他们如何在真实世界的编程中加速你的程序的机制。
我正在寻找这个实现的细节，并且可以与其他Haskell方法进行比较/对比。 我明白什么是memoization，我不是在寻找一般的工作原理的描述。
这个库是熟知的memoization技术的简单组合。 我们从典型的例子开始：
fib = (map fib' [0..] !!) where fib' 0 = 0 fib' 1 = 1 fib' n = fib (n-1) + fib (n-2) 我解释你所说的是什么意思，你知道这是怎样工作的。 所以我会关注组合。
我们必须试图捕捉和推广(map f [0..] !!)的想法。 这个函数的types是(Int -> r) -> (Int -> r) ，这是合理的：它从Int -> r获取一个函数，并返回一个同样函数的memoized版本。 任何语义上具有这种types的函数称为“ Int记忆器”（偶数，不记忆）。 我们概括这个抽象：
type Memo a = forall r. (a -> r) -> (a -> r)
所以一个Memo a ，一个记忆器，从一个函数到任何东西，并返回已经被记忆（或不）的语义相同的函数。
不同的记忆器的想法是find一种方法来枚举具有数据结构的域，将函数映射到它们上面，然后索引数据结构。 bool是一个很好的例子：
bool :: Memo Bool bool f = table (f True, f False) where table (t,f) True = t table (t,f) False = f
来自Bool函数等价于对，除了一对将只评估一次每个组件（就像在lambda之外发生的每个值一样）。 所以我们只是映射到一对，然后回来。 重点是我们通过枚举域来提升参数（这里是table的最后一个参数）的lambda上面的函数的评估。
记忆Maybe a是一个类似的故事，除了现在我们需要知道如何为Just案例记忆。 因此， Maybe的备忘录以一个备忘录作为参数：
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) = jx
图书馆的其余部分只是这个主题的变化。
它记忆整型的方式使用比[0..]更合适的结构。 这是有点牵扯，但基本上只是创build一个无限树（代表二进制数来阐明结构）：
1 10 100 1000 1001 101 1010 1011 11 110 1100 1101 111 1110 1111
因此，在树中查找数字的运行时间与其表示中的比特数成比例。
正如sclv指出的那样，Conal的MemoTrie库使用相同的底层技术，但是使用typestypes的表示而不是组合表示。 我们同时独立发布我们的图书馆（事实上，在几个小时内！）。 Conal在简单的情况下更容易使用（只有一个函数， memo ，它会根据types决定使用的备忘录结构），而我的更灵活，就像你可以这样做：
boundedMemo :: Integer -> Memo Integer boundedMemo bound f = \z -> if z < bound then memof z else fz where memof = integral f
其中只logging小于给定边界的值，这是执行一个项目欧拉问题所需要的。
还有其他的方法，例如通过monad公开一个开放的fixpoint函数：
memo :: MonadState ... m => ((Integer -> mr) -> (Integer -> mr)) -> m (Integer -> mr)
这允许更多的灵活性，例如。 清除caching，LRU等。但是这是一个痛苦的屁股使用，而且它对要记忆的function（例如没有无限的左recursion）提出了严格的约束。 我不相信有实施这种技术的图书馆。
这是否回答你好奇？ 如果不是，也许可以明确你所困惑的一些观点？
心是bitsfunction：
-- | Memoize an ordered type with a bits instance. bits :: (Ord a, Bits a) => Memo a bits f = IntTrie.apply (fmap f IntTrie.identity)
这是唯一的function（除了微不足道的unit :: Memo () ），它可以给你一个Memo a价值。 它使用与本页有关Haskell memoization相同的想法。 第2部分显示了使用列表的最简单的memoization策略，第3部分使用类似于IntTree使用的IntTree的自然二叉树进行相同的操作。
基本的想法是使用像(map fib [0 ..] !!)或Memocombinator案例 – IntTrie.apply (fmap f IntTrie.identity) 。 这里要注意的是IntTie.apply和!!之间的对应关系 IntTrie.identity和[0..] 。
下一步是用其他types的参数来记忆函数。 这是用wrap函数完成的，它使用typesa和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和memoizing多个参数的types。
部分工作由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/
一些进一步的扩展 – function记忆背后的一般概念是从a -> b取一个函数，并映射到一个数据结构，这个数据结构是由a的所有可能值索引的，并且包含b值。 这样的数据结构应该有两种懒惰 – 首先它应该是懒惰的。 其次，它本身应该是懒散的。 前者默认情况下是非严格的语言。 后者是通过使用泛化尝试来完成的。
memocomrie，memotrie等等的各种方法都是创build各种types的数据结构的尝试组合的方法，以允许简单构build日益复杂结构的尝试。
@luqui有一件事情我不清楚：它是否具有与以下相同的操作行为：
fib :: [Int] fib = map fib' [0..] where fib' 0 = 0 fib' 1 = 1 fib' n = fib!!(n-1) + fib!!(n-2)
上面应该记住顶层的fib，因此如果你定义了两个函数：
fn = fib!!n + fib!!(n+1)
如果我们然后计算f 5 ，我们得到fib 5在计算fib 6时不被重新计算。 我不清楚memoization combinators是否具有相同的行为（即顶级memoization，而不是只在fib计算内部禁止重新计算），如果是，为什么？
