如何在Haskell函数中使用向量缓存结果?

nqwrtyyt  于 2022-11-14  发布在  其他
关注(0)|答案(2)|浏览(126)

我有一个计算量很大的向量,我想在一个函数中建立索引,但是由于这个表从来没有在其他地方使用过,我不想传递这个向量,而是像记忆函数一样访问预先计算的值。
其想法是:

cachedFunction :: Int -> Int
cachedFunction ix = table ! ix
    where table = <vector creation>

我注意到的一个方面是,我所看到的所有记忆示例都涉及递归,即使使用表来记忆,表中的值也依赖于表中的其他值。这与我的情况不同,在我的情况下,计算值是使用试错法找到的,但每个元素都是独立于另一个的。
如何在函数中实现缓存表?

elcex8rz

elcex8rz1#

你几乎是对的。问题是,你的例子基本上是这样的:

┌────────────────────────────────┐
cachedFunction ix = │ table ! ix                     │
                    │where table = <vector creation> │
                    └────────────────────────────────┘

也就是说,table不会在不同的ix之间共享。这与它碰巧不 * 依赖于 * ix的事实无关(这在本例中很明显,但一般情况下并不如此)。因此,将它保存在内存中是没有用的,Haskell也不会这样做。
但是,您可以通过将ix参数及其关联的where-block拉入结果中来改变这一点:

cachedFunction = \ix -> table ! ix
 where table = <vector creation>

也就是说

┌────────────────────────────────┐
cachedFunction = │ \ix -> table ! ix              │
                 │where table = <vector creation> │
                 └────────────────────────────────┘

或更短,

cachedFunction = (<vector creation> !)

在这种形式中,cachedFunctionconstant applicative form,也就是说,尽管有一个函数类型,但它被编译器视为 * 一个常量值 *。它不是一个你可以计算为范式的值,但它将保持相同的表(它 * 不能 * 依赖于ix;它的作用域中没有它)。

erhoui1w

erhoui1w2#

根据this answer,GHC永远不会重新计算在模块顶层声明的 values。(一次)第一次需要它,然后它就再也不会被请求了。(为简单起见,示例使用简单整数而不是向量)

import Debug.Trace

cachedFunction :: Int -> Int
cachedFunction ix = table + ix

table = traceShow "Computed" 0

main :: IO ()
main = do
  print 0
  print $ cachedFunction 1
  print $ cachedFunction 2

输出:

0
"Computed"
1
2

我们可以看到,tablecachedFunction被调用之前 * 没有 * 被计算,并且它只被计算一次,即使我们调用了cachedFunction两次。

相关问题