在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类型中包含一个可能不可变的"result"字段.但我不能.

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

谢谢!

Answer 1

Hash-cons的价值观expr_expr.通过这样做,程序中的结构相等的值将共享完全相同的内存表示,并且您可以=通过物理相等(==)替换结构相等().

这纸应该让你迅速开始OCaml中哈希consing.

Answer 2

您可以使用函子接口来控制哈希表使用的相等类型。我相信 (==) 的语义对于您的目的来说是合法的；即，对于任何纯函数 f，如果 A == B，则 f A = f B。因此，您可以缓存 f A 的结果。然后，如果您找到物理上等于 A 的 B，则缓存的值对于 B 来说是正确的。

使用 (==) 进行散列的缺点是，散列函数会将所有结构上相等的对象发送到同一个散列桶，在那里它们将被视为不同的对象。如果表中有很多结构相同的对象，则散列不会带来任何好处。该行为退化为线性搜索。

您无法定义哈希函数来处理物理地址，因为垃圾收集器可以随时更改物理地址。

但是，如果您知道您的表仅包含相对较少的大值，那么使用物理相等可能对您有用。