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

Если я пытаюсь использовать «добавить тест», я получаю ошибку переполнения стека, что, я думаю, сводится к определению (+) внутри самого моего шрифта, полагаясь на '+'.

Можно ли как-нибудь это исправить?Любая помощь будет принята с благодарностью.

Большое спасибо, Эш

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 во всех примитивных операциях.В этом случае вы будете создавать только конечные структуры данных (и операторы будут обрабатывать их с нетерпением).