8

我有一个非常大的决策树。它的用法如下：

-- once per application start
t :: Tree
t = buildDecisionTree
-- done several times
makeDecision :: Something -> Decision
makeDecision something = search t something

此决策树太大而无法放入内存。但是，由于惰性评估，它只被部分评估。

问题是，在某些情况下会尝试所有可能的决策，从而导致对整个树进行评估。这不会终止，但也不应该导致内存溢出。此外，如果此过程中止，内存使用量不会减少，因为仍然已经评估了一个巨大的子树。

一种解决方案是每次makeDecision调用时都重新评估树，但这会失去缓存决策的好处并显着减慢makeDecision.

我想参加中级课程。特别是在我的应用程序中，使用树中的公共路径前缀进行连续决策是很常见的。所以我想缓存最后使用的路径，但删除其他路径，使它们在下次使用时重新评估。我怎样才能在 Haskell 中做到这一点？

4

1 回答 1

6

在纯 Haskell 中是不可能的，请参阅问题Can a thunk be duplicated to raise memory performance？（正如@shang 所指出的）。但是，您可以使用 IO 执行此操作。

我们从模块头开始，只列出应该使这个模块（将使用 unsafePerformIO）安全的类型和函数。也可以在没有 unsafePerformIO 的情况下执行此操作，但这意味着用户必须将更多代码保留在 IO 中。

{-# LANGUAGE ExistentialQuantification #-}
module ReEval (ReEval, newReEval, readReEval, resetReEval) where

import Data.IORef
import System.IO.Unsafe

我们首先定义一种数据类型，该数据类型以防止所有共享的方式存储值，方法是使函数和参数彼此远离，并且仅在我们需要该值时应用该函数。请注意，返回的值unsharedValue 可以共享，但不能与其他调用的返回值共享（假设函数正在做一些不平凡的事情）：

data Unshared a = forall b. Unshared (b -> a) b

unsharedValue :: Unshared a -> a
unsharedValue (Unshared f x) = f x

现在我们定义可重置计算的数据类型。我们需要存储计算和当前值。后者存储在 中IORef，因为我们希望能够重置它。

data ReEval a = ReEval {
    calculation :: Unshared a,
    currentValue :: IORef a
    }

要将一个值包装在一个ReEval盒子中，我们需要一个函数和一个参数。为什么不只是a -> ReEval a？因为那样就没有办法阻止参数被共享。

newReEval :: (b -> a) -> b -> ReEval a
newReEval f x = unsafePerformIO $ do
    let c = Unshared f x
    ref <- newIORef (unsharedValue c)
    return $ ReEval c ref

阅读很简单：只需从IORef. 这种使用unsafePerformIO是安全的，因为我们总是会得到 的值unsharedValue c，尽管它是不同的“副本”。 

readReEval :: ReEval a -> a
readReEval r = unsafePerformIO $ readIORef (currentValue r)

最后是重置。我将它留在 IO monad 中，不是因为它比其他要包装的函数更安全unsafePerformIO，而是因为这是让用户控制何时实际发生重置的最简单方法。您不想冒这样的风险，resetReEval因为没有返回值可供使用，所以您的所有调用都会被延迟延迟，直到您的内存用完甚至优化掉。

resetReEval :: ReEval a -> IO ()
resetReEval r = writeIORef (currentValue r) (unsharedValue (calculation r))

这是模块的结尾。这是示例代码：

import Debug.Trace
import ReEval
main = do
    let func a = trace ("func " ++ show a) negate a
    let l = [ newReEval func n | n <- [1..5] ]
    print (map readReEval l)
    print (map readReEval l)
    mapM_ resetReEval l
    print (map readReEval l)

在这里你可以看到它做了预期的事情：

$ runhaskell test.hs 
func 1
func 2
func 3
func 4
func 5
[-1,-2,-3,-4,-5]
[-1,-2,-3,-4,-5]
func 1
func 2
func 3
func 4
func 5
[-1,-2,-3,-4,-5]
于 2013-01-18T16:32:54.643 回答