F# 类型定义内的递归

Question

我在尝试在 F# 中实现自动微分时遇到一些问题。我认为问题在于评估不“懒惰”。

这是我的代码：

type Diff =
    {d : double; df : Diff}
    static member (+) (x : Diff, y : Diff) =
        {d = x.d + y.d; df = x.df + y.df}
    static member (-) (x : Diff, y : Diff) =
        {d = x.d - y.d; df = x.df - y.df}
    static member (*) (x : Diff, a : double) =
        {d = x.d * a; df = x.df * a}
    static member (*) (x : Diff, y : Diff) =
        {d = x.d * y.d; df = (x.df * y) + (y.df * x)}

let rec dZero = {d = 0.0; df = dZero}

let dConst x = {d = x; df = dZero}

let dId x = {d = x; df = dConst 1.0}

let test = dId 5.0

let add (x:Diff) = (x+x).d

如果我尝试使用“add test”，则会出现堆栈溢出错误，我认为这归因于我的类型本身依赖于“+”的 (+) 定义。

有什么办法可以解决这个问题吗？任何帮助将不胜感激。

非常感谢，阿什

Answer 1

正如您所想，问题在于 F# 不使用延迟求值，并且您正在创建的数据结构是“无限的”（因为 dZero 递归地引用自身）。计算 + 时，运算符对 df 值调用 +，然后对 df 值调用 + code>df.df 值等等...

纠正此问题的一种方法是使记录的 df 成员显式惰性：

type Diff = 
    {d : double; df : Lazy<Diff>} 
    static member (+) (x : Diff, y : Diff) = 
        {d = x.d + y.d; df = lazy (x.df.Value + y.df.Value) } 
    static member (-) (x : Diff, y : Diff) = 
        {d = x.d - y.d; df = lazy (x.df.Value - y.df.Value) } 
    static member (*) (x : Diff, a : double) = 
        {d = x.d * a; df = lazy (x.df.Value * a) } 
    static member (*) (x : Diff, y : Diff) = 
        {d = x.d * y.d; df = lazy ((x.df.Value * y) + (y.df.Value * x)) } 

let rec dZero = {d = 0.0; df = lazy dZero} 
let dConst x = {d = x; df = lazy dZero} 
let dId x = {d = x; df = lazy dConst 1.0} 

这将评估 df 仅在实际使用时才值，因此 + 操作将计算 d 的值，并仅为 df 提供一个惰性值（如果有人需要的话可以评估）。

另一种替代方法是使 Diff 类型成为可区分联合，并将零表示为特殊值（而不是递归记录），除非您对其他内容使用递归引用，否则这种方法将有效。声明大致如下：

type Diff = 
    | DiffValue of double * Diff
    | DiffZero 
    static member (+) // etc...

这将使实现时间更长一些，因为您需要检查所有基元操作中的 Zero 情况。在这种情况下，您只会创建有限的数据结构（并且运算符会急切地处理它们）。