哈斯克尔：部分下降懒惰评估结果

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

在纯哈斯克尔中是不可能的，参见问题Can a thunk be duplicated to improve memory performance?（正如@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]