Mutually recursive let bindings

Question

I'm trying to implement a parser that looks something like this:

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

The last functions are mutually recursive in their definitions. Expression's definition depends on Term, which depends on Factor, which depends on Part, which depends on Paren, which depends on Expression.

When I try to compile this, I get an error about mutually recursive definitions with the suggestion to make Expression lazy or a function. I tried both of those, and I get a cryptic InvalidOperationException with both that says something about ValueFactory attempting to access the Value property.

Answer 1

In general, F# lets you use let rec .. and .. not just for defining mutually recursive functions, but also for defining mutually recursive values. This means that you might be able to write something like this:

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

However, this only works if the computation is not evaluated immediately (because then the recursive definition would not make sense). This very much depends on the library you're using here (or on the rest of your code). But you can try the above and see if that works - if no, you'll need to provide more details.

EDIT In the updated example, there is an immediate loop in your recursive definition. You need to delay some part of the definition using fun _ -> ... so that not everything needs to be evaluated at once. In your example, you can do that by replacing Then with ThenBind in the definition of Paren:

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