独立记忆参数

Question

我有一个模拟很多函数的调用type F = A -> B -> C -> D,其中A.. D是具体的类型.

类型的对象A具有中等寿命.(这是codegolf的ratrace的基因组.)

最昂贵的计算来自参数A.我可以像这样容易地记忆:

f1 :: F
f1 a = let expensive = trace "expensive computation!" $ expensiveComputation a
        in \b c -> expensive

并expensive通过部分应用保留一些预处理值:

preProz :: [B -> C -> D]
preProz = [f1 [], f1 [False], f2 []]

这些痕迹表明preProz <*> [[],[[]]] <*> [1,2]我不会重新计算这些值.

现在我发现我F的一些人也会受益于预处理B.这种预处理是独立的A,事实上,这样的记忆没有任何好处

f2 a = let expensive = trace "expensive computation!" $ expensiveComputation a
        in \b -> let dear = trace "expensive computation!" $ expensiveComputation b
                  in expensive + dear

因为dear是重新计算的,即使是b相等的.

我需要的是:

(B -> e) -> A -> e -> C -> D

其中e应memoized.这里的类型e是存在的类型.但这迫使我重新计算A每一个的所有值B,这同样糟糕,我无法保存es,这是函数的私有.

如何独立记忆2个参数？

Answer 1

a您需要一个同时记录和的函数b：

f12 a b = ...
    in \c -> ...

当你想记住a但不想记住时b，你可以使用f1 a，当你想记住时，你可以使用f12 a b。

当然，如果能够在f1和之间共享一些实现，那就太好了f12。但是，您只能通过使用预先计算的结果代替原始值的私有函数来做到这一点：

f1 a = privateA (precomputeA a)
f12 a b = privateAB (precomputeA a) (precomputeB b)
privateA a' b = privateAB a' (precomputeB b)
private AB a' b' c = ...

如果 的预计算b依赖于 的预计算a，则：

f1 a = privateA (precomputeA a)
f12 a b = let a' = precomputeA a in privateAB a' (precomputeB a' b)
privateA a' b = privateAB a' (precomputeB a' b)
private AB a' b' c = ...

我故意不使用函数组合和 eta 约简，以使事情变得更清晰。我还遗漏了您可能想要用来控制评估时间的任何严格性注释。

也许“记忆”这个词在这里不太合适。你的意思是“带有一些预计算的部分应用程序”。