caching - 扩展不可变类型(或 : fast cache for immutable types) in OCaml

Question

我在 ocaml 中有一个递归的不可变数据结构，可以简化为这样的:

type expr =
{
    eexpr : expr_expr;
    some_other_complex_field : a_complex_type;
}

and expr_expr =
    | TInt of int
    | TSum of (expr * expr)
    | TMul of (expr * expr)

这是一个 AST，有时它变得非常复杂(非常深)。

有一个计算表达式的递归函数。例如，让我们说，

let rec result expr =
    match expr.eexpr with
        | TInt i -> i
        | TSum (e1, e2) -> result e1 + result e2
        | TMul (e1, e2) -> result e1 * result e2

现在假设我正在将一个表达式映射到另一个表达式，并且我需要不断检查一个 expr 的结果，有时对同一个 expr 不止一次，有时对最近使用模式映射的表达式

{ someExpr with eexpr = TSum(someExpr, otherExpr) }

现在，结果函数非常轻量级，但是对于深度 AST 多次运行它不会得到很好的优化。我知道我可以使用 Hashtbl 缓存该值，但 AFAIK Hashtbl 只会进行结构相等，因此无论如何它都需要遍历我的长 AST。
我知道最好的选择是在 expr 类型中包含一个可能不可变的“结果”字段。但我不能。

那么 Ocaml 中是否有任何方法可以将值缓存到不可变类型，这样我就不必每次需要时都急切地计算它？

谢谢!

Answer 1

散列约束 expr_expr 的值.通过在您的程序中执行此结构相等的值将共享完全相同的内存表示，您可以将结构相等( = )替换为物理相等( == )。

此 paper应该可以让您快速开始在 OCaml 中进行哈希处理。