cir*_*uin 13 haskell memoization
我知道memoization似乎是关于堆栈溢出的haskell标记的一个常年话题,但我认为这个问题以前没有被问过.
我知道几个不同的'现成'Haskell的memoization库:
Cmpfor Hashable和Data.Mapfor Data.HashMap和添加appropraite imports,你得到一个基于哈希的版.)但是,我不知道任何基于对象标识而不是对象值查找答案的库.这可能很重要,因为有时用作备忘录表的键的对象类型(即,作为被记忆的函数的输入)可能很大---如此之大以至于完全检查对象以确定是否之前看到它本身就是一个缓慢的操作.慢,而且也没有必要的,如果你将一次又一次地施加memoized函数被存储在给定的"位置在存储器"的对象1.(例如,如果我们正在记忆一个函数,这个函数是在一些具有大量结构共享的大型数据结构上递归调用的.)如果我们之前已经在那个确切的对象上计算了memoized函数,我们可以已经知道了答案,即使没有看对象本身!
实现这样的memoization库涉及一些微妙的问题,并且正确地执行它需要语言的几个特殊支持.幸运的是,GHC提供的特殊功能,我们需要的,是有纸的佩顿-琼斯,马洛和Elliott基本上担心这些问题多数为你解释如何建立一个坚实的实现.他们没有提供所有细节,但他们接近了.
我可以看到哪一个可能应该担心的细节,但是他们不担心的是线程安全---他们的代码显然根本不是线程安全的.
我的问题是:有没有人知道一个打包的库,它在Peyton-Jones,Marlow和Elliott论文中讨论了那种记忆,填写了所有的细节(最好还填写了适当的线程安全性)？
如果做不到这一点,我想我将不得不自己编写代码:是否有人对其他细微之处(除了线程安全和论文中讨论的内容)有任何想法,这样的库的实现者会记住哪些？
UPDATE
按照@ luqui的建议,下面是关于我面临的确切问题的更多数据.我们假设有一种类型:
data Node = Node [Node] [Annotation]
这种类型可以用来表示内存中一种简单的有根DAG,其中Nodes是DAG节点,root只是一个区分Node,每个节点都注明了一些Annotations,我认为其内部结构不需要关注我们(但是如果它很重要,那就问一下,我会更具体.)如果以这种方式使用,请注意Node内存中的s 之间可能存在显着的结构共享- 可能会有指数级的路径从根到a节点比节点本身.我从一个外部库中获得了这种形式的数据结构,我必须与它接口; 我无法更改数据类型.
我有一个功能
myTransform : Node -> Node
细节不需要我们关注(或者至少我是这么认为的;但如果需要的话,我可以更具体).它将节点映射到节点,检查它给出的节点的注释,以及它的直接子节点的注释,以提出Node具有相同子节点但可能具有不同注释的新节点.我想写一个函数
recursiveTransform : Node -> Node
其输出与数据结构"看起来一样",就像你做的那样:
recursiveTransform Node originalChildren annotations =
myTransform Node recursivelyTransformedChildren annotations
where
recursivelyTransformedChildren = map recursiveTransform originalChildren
除了它以明显的方式使用结构共享,以便它不返回指数数据结构,而是返回与其输入大小相同的数据结构.
我很欣赏,如果说,Nodes在我得到它们之前已经编号,或者我可以改变a的定义,这将更容易Node.我不能(轻松)做这些事情.
我也对存在实现我提到的功能的库的一般问题感兴趣,这个功能完全独立于我现在面临的具体问题:我觉得我必须在几次这个问题上解决这个问题,一劳永逸地杀死龙会很好.事实上,SPJ等人认为值得为GHC添加一个而不是三个特征来支持这种形式的库的存在,这表明该特征真正有用,并且无法在所有情况下解决.(但我仍然非常有兴趣听到有助于这个特殊情况的解决方法:长期问题并不像我现在遇到的问题那么紧急:-))
1从技术上讲,我并不是指内存中的位置,因为垃圾收集器有时会移动一些物体 - 我真正的意思是'对象识别'.但我们可以认为这与我们在记忆中的位置的直观概念大致相同.
如果您只希望基于对象的身份,而不是平等memoize的,你可以使用内置的语言现有的懒惰机制.
例如,如果您有这样的数据结构
data Foo = Foo { ... }
expensive :: Foo -> Bar
然后你可以添加要记忆的值作为额外的字段,并让懒惰为你处理其余的事情.
data Foo = Foo { ..., memo :: Bar }
为了更容易使用,添加一个智能构造函数来打结.
makeFoo ... = let foo = Foo { ..., memo = expensive foo } in foo
虽然这比使用库稍微不那么优雅,并且需要修改数据类型才真正有用,但这是一种非常简单的技术,所有线程安全问题都已经为您解决了.