相互递归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)))