Funkcje rekursywne w wyrażeniach obliczeniowych

Question

Pierwsze tło. Obecnie uczę się kilku rzeczy o kombinatorach parserów monadycznych. Chociaż starałem się przekazać funkcję „chainl1” z this paper (str. 16-17), wpadłem na to rozwiązanie:

let chainl1 p op = parser { 
    let! x = p 
    let rec chainl1' (acc : 'a) : Parser<'a> = 
     let p' = parser { 
      let! f = op 
      let! y = p 
      return! chainl1' (f acc y) 
      } 
     p' <|> succeed acc 
    return! chainl1' x 
} 

testowałem funkcji z jakiegoś dużego wejście i dostał StackOverflowException. Teraz zastanawiam się, czy jest możliwe przepisanie funkcji rekursywnej, która używa pewnej ekspresji obliczeniowej, w taki sposób, że używa rekursji ogonowej?

Kiedy rozszerzam wyrażenie obliczeniowe, nie widzę, jak byłoby to ogólnie możliwe.

let chainl1 p op = 
    let b = parser 
    b.Bind(p, (fun x -> 
    let rec chainl1' (acc : 'a) : Parser<'a> = 
     let p' = 
      let b = parser 
      b.Bind(op, (fun f -> 
      b.Bind(p, (fun y -> 
      b.ReturnFrom(chainl1' (f acc y)))))) 
     p' <|> succeed acc 
    b.ReturnFrom(chainl1' x))) 

Answer 1

W kodzie, poniższa funkcja nie jest ogon rekurencyjne, ponieważ - w każdej iteracji - to sprawia, że ​​wybór między obu p' lub succeed:

// Renamed a few symbols to avoid breaking SO code formatter 
let rec chainl1Util (acc : 'a) : Parser<'a> = 
    let pOp = parser { 
    let! f = op 
    let! y = p 
    return! chainl1Util (f acc y) } 
    // This is done 'after' the call using 'return!', which means 
    // that the 'cahinl1Util' function isn't really tail-recursive! 
    pOp <|> succeed acc 

W zależności od implementacji parsera kombinatorów, następujących przepisać mógł pracować (nie jestem ekspertem tutaj, ale może warto byłoby to):

let rec chainl1Util (acc : 'a) : Parser<'a> = 
    // Succeeds always returning the accumulated value (?) 
    let pSuc = parser { 
    let! r = succeed acc 
    return Choice1Of2(r) } 
    // Parses the next operator (if it is available) 
    let pOp = parser { 
    let! f = op 
    return Choice2Of2(f) } 

    // The main parsing code is tail-recursive now... 
    parser { 
    // We can continue using one of the previous two options 
    let! cont = pOp <|> pSuc 
    match cont with 
    // In case of 'succeed acc', we call this branch and finish... 
    | Choice1Of2(r) -> return r 
    // In case of 'op', we need to read the next sub-expression.. 
    | Choice2Of2(f) -> 
     let! y = p 
     // ..and then continue (this is tail-call now, because there are 
     // no operations left - e.g. this isn't used as a parameter to <|>) 
     return! chainl1Util (f acc y) } 

w ogóle, wzór do pisania funkcje ogon rekurencyjnej wewnątrz wyrażenia obliczeniowe działa. Coś jak to będzie działać (dla wyrażeń obliczeniowych, które są realizowane w sposób, który pozwala tail-rekurencji):

let rec foo(arg) = id { 
    // some computation here 
    return! foo(expr) } 

Jak można sprawdzić, nowa wersja pasuje do tego wzoru, ale oryginalny jeden nie.

Answer 2

W ogóle jest to możliwe, aby napisać ogon rekurencyjnej wyrażeń obliczeniowych (patrz 1 i 2), nawet z wieloma let! do wiązań dzięki mechanizmowi „opóźnienie”.

W tym przypadku ostatnie zdanie z chainl1 jest tym, co myślę.