相互遞歸let綁定

Question

我想實現一個分析器，它看起來是這樣的：

open System 

type ParseResult<'a> = 
    { 
     Result : Option<'a>; 
     Rest : string 
    } 

let Fail  = fun input -> { Result = None; Rest = input } 
let Return a = fun input -> { Result = Some a; Rest = input } 

let ThenBind p f = 
    fun input -> 
     let r = p input 
     match r.Result with 
     | None -> { Result = None; Rest = input } // Recreate the result since p returns a ParseResult<'a> 
     | _ -> (f r.Result) r.Rest 
let Then p1 p2 = ThenBind p1 (fun r -> p2) 

let Or p1 p2 = 
    fun input -> 
     let r = p1 input 
     match r.Result with 
     | None -> p2 input 
     | _ -> r 

let rec Chainl1Helper a p op = 
    Or 
     <| ThenBind op (fun f -> 
      ThenBind p (fun y -> 
      Chainl1Helper (f.Value a y.Value) p op)) 
     <| Return a 
let Chainl1 p op = ThenBind p (fun x -> Chainl1Helper x.Value p op) 

let rec Chainr1 p op = 
    ThenBind p (fun x -> 
     Or 
      (ThenBind op (fun f -> 
       ThenBind (Chainr1 p op) (fun y -> 
        Return (f.Value x.Value y.Value)))) 
      (Return x.Value)) 

let Next = fun input -> 
    match input with 
    | null -> { Result = None; Rest = input } 
    | "" -> { Result = None; Rest = input } 
    | _ -> { Result = Some <| char input.[0..1]; Rest = input.[1..] } 

let Sat predicate = ThenBind Next (fun n -> if predicate n.Value then Return n.Value else Fail) 

let Digit = ThenBind (Sat Char.IsDigit) (fun c -> Return <| float c.Value) 
let rec NatHelper i = 
    Or 
     (ThenBind Digit (fun x -> 
      NatHelper (float 10 * i + x.Value))) 
     (Return i) 
let Nat = ThenBind Digit (fun d -> NatHelper d.Value) 

let LiteralChar c = Sat (fun x -> x = c) 
let rec Literal input token = 
    match input with 
    | "" -> Return token 
    | _ -> Then (LiteralChar <| char input.[0..1]) (Literal input.[1..] token) 

let AddSub = 
    Or 
     <| ThenBind (LiteralChar '+') (fun c -> Return (+)) 
     <| ThenBind (LiteralChar '-') (fun c -> Return (-)) 

let MulDiv = 
    Or 
     <| ThenBind (LiteralChar '*') (fun c -> Return (*)) 
     <| ThenBind (LiteralChar '/') (fun c -> Return (/)) 

let Exp = ThenBind (LiteralChar '^') (fun c -> Return (**)) 

let rec Expression = Chainl1 Term AddSub 
and Term = Chainl1 Factor MulDiv 
and Factor = Chainr1 Part Exp 
and Part = Or Nat Paren 
and Paren = 
    Then 
     <| LiteralChar '(' 
     <| ThenBind Expression (fun e -> 
      Then (LiteralChar ')') (Return e.Value)) 

最後一個功能是其定義相互遞歸。 Expression的定義依據Term，依賴於Factor，依賴Part，這依賴於Paren，它依賴於Expression。

當我嘗試編譯這個，我得到一個關於相互遞歸定義的錯誤，並建議使Expression懶惰或函數。我嘗試了這兩個，並且我得到了一個神祕的InvalidOperationException，這兩個都說明了一些關於ValueFactory試圖訪問Value屬性的內容。

Answer 1

通常，F＃可讓您使用let rec .. and ..，不僅用於定義相互遞歸函數，還用於定義相互遞歸的值。這意味着，你也許可以寫出這樣的事：

let rec Expression = Chainl1 Term AddSub 
and Paren = 
    Then 
     <| LiteralChar '(' 
     <| ThenBind Expression (fun e -> 
      Then (LiteralChar ')') (Return e.Value)) 
and Part = Or Nat Paren 
and Factor = Chainr1 Part Exp 
and Term = Chainl1 Factor MulDiv 

然而，如果計算不立即進行評估（因爲那時遞歸定義將沒有任何意義），這僅適用。這很大程度上取決於您在此使用的庫（或其他代碼）。但是，您可以嘗試以上方法，看看是否可行 - 如果不行，您需要提供更多詳細信息。

編輯在更新的示例中，您的遞歸定義中有一個直接循環。您需要使用fun _ -> ...來延遲某些部分的定義，以便並非一切都需要一次進行評估。在你的榜樣，你可以做，通過在Paren定義與ThenBind更換Then：

let rec Expression = Chainl1 Term AddSub 
and Term = Chainl1 Factor MulDiv 
and Factor = Chainr1 Part Exp 
and Part = Or Nat Paren 
and Paren = 
    ThenBind 
     (LiteralChar '(') 
     (fun _ -> ThenBind Expression (fun e -> 
      Then (LiteralChar ')') (Return e.Value)))