Haskell:部分删除惰性评估结果

Question

我有一个非常大的决策树.它使用如下:

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

此决策树太大而无法放入内存中.但是,由于懒惰的评估,它只是部分评估.

问题是,有些情况下会尝试所有可能的决策,导致整个树被评估.这不会终止,但也不应该导致内存溢出.此外,如果此过程中止,则内存使用量不会减少,因为仍然会评估一个巨大的子树.

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

我想去中学课程.特别是在我的应用程序中,在树中使用公共路径前缀做连续决策是很常见的.因此,我想缓存上次使用的路径但删除其他路径,导致它们在下次使用时重新评估.我怎么能在Haskell中做到这一点？

Answer 1

在纯haskell中是不可能的,请参阅问题是否可以重复thunk以提高内存性能？(正如@shang指出的那样).但是,您可以使用IO执行此操作.

我们从模块heade开始,仅列出应该使该模块(将使用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]