类型定义中的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',我会得到一个堆栈溢出错误,我认为这取决于我的类型本身依赖于'+'的(+)定义.

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

非常感谢,Ash

Answer 1

正如您所想,问题是F#不使用延迟评估,并且您创建的数据结构是"无限的"(因为dZero递归引用自身).计算时+,操作者调用+的df价值观和依次调用+的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在所有基本操作中检查实例.在这种情况下,您只能创建有限的数据结构(操作员会急切地处理它们).