計算表達式中的遞歸函數

一些背景優先。我目前正在學習一些關於monadic解析器組合器的東西。當我試圖從this paper（第16-17）轉移「chainl1」功能，我想出了這個解決方案：計算表達式中的遞歸函數

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 
}

我測試了一些大的輸入功能，並得到了StackOverflowException。現在我想知道，是否有可能重寫遞歸函數，它使用一些計算表達式，所以它使用尾遞歸？

當我擴大計算表達式時，我看不出它通常是可能的。

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)))

來源

2010-06-29 PetPaulsen

在代碼中，下面的函數不是尾遞歸，因爲 - 在每次迭代 - 這使得無論是p'或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

根據您的實現解析器組合中，以下重寫可以工作（我不是專家，但它可能是值得嘗試此）：

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) }

一般情況下，模式編寫尾遞歸函數中的計算式的作品。這樣的事情就可以了（對於在一個方式，讓尾遞歸實現的計算式）：

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

你可以檢查一下，新版本的模式相匹配，但原來的一個沒有。

來源

2010-06-29 14:44:12

這擺脫了通過用戶代碼遞歸，但在我的實現這裏http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!1772.entry它仍然StackOverflows通過解析器實現本身。我現在會被激發去研究'延續解析器'... – Brian 2010-06-29 18:31:55

FParsec http://www.quanttec.com/fparsec/處理這個問題嗎？ – Brian 2010-06-29 18:33:00

布賴恩，我也用你的博客系列作爲學習資源。它幫助了很多。同時我將Mau的答案（'seq'）與我的解析器進行了比較。我猜想monad中的Delay方法是導入。但我真的不知道。 FParsec使用'while'...但我想使用功能性解決方案：D – PetPaulsen 2010-06-29 18:50:15

一般來說也能夠let!感謝綁定寫尾遞歸計算表達式（見1和2），甚至具有多至「延遲」機制。

在這種情況下，chainl1的最後一個陳述是讓你進入角落的原因。

來源

2010-06-29 14:41:58 Mau

計算表達式中的遞歸函數

回答

相關問題