F# - Create a Recursive Discriminated Union at Runtime

Question

I am trying to write a simple interpreter to control a Turtle using F#.
I have created the following recursive union type to represent the few commands that the Turtle will accept. The code will be represented by a "Command list" that shouldn't be too hard to execute with a simple recursive function.

type Command = 
| Repeat of amount * Command list
| Forward of amount
| Turn of direction * amount

I want to make this interpreter white space delineated so the source could look as follows.

Forward 75
Repeat 4
    Forward 10
    Turn Right 50
    Repeat 6
        Forward 20
        Turn Right 60
        Repeat 8
            Forward 15
            Turn Left 30
    Turn Right 10
Forward 25

I then have this function to separate everything into an int*string list based on the indentation level. So Repeat 4 would become (0, "Repeat 4"), Forward 10 would be (1, "Forward 10"), and Turn Left 30 would be (3, "Turn Left 30").

/// Creates indentation chart for generating a syntax tree by cycling 
/// through a list of strings generated
///     by string.Split and counting the empty strings before each non-empty 
//// string.
let indent strs = 
    let rec inner strs search cmds indent temp =
        match strs, search with
        | [], _ -> (indent,temp)::cmds
        | ""::tail, Cmd -> inner tail Indent ((indent,temp)::cmds) 0 "" // 
Newline started -> push cached counter and command string
        | ""::tail, Indent -> inner tail Indent cmds (indent+1) temp // Next 
level of indent -> increment indent counter
        | h::tail, Cmd -> inner tail Cmd cmds indent (temp + " " + h)
        | h::tail, Indent -> inner tail Cmd cmds indent (temp + h)
        | h::tail, Start -> inner tail Cmd cmds indent (temp + h)
    inner strs Start [] 0 "" |> List.rev

let splitIndent (text:string) = text.Trim().Split() |> Array.toList |> 
    indent

Now this is where I am stuck. I have the list of commands with their indentation levels, but I do not know how to dynamically create a recursive discriminated union. I know how to hardcode it in. It looks something like this,

let tree = [
    Forward 75
    Repeat (4, [
        Forward 10
        Turn (Right, 50)
        Repeat (6, [
            Forward 20
            Turn (Right, 60)
            Repeat (8, [
                Forward 15
                Turn (Left, 30)
                ])])
        Turn (Right, 10)])
    Forward 25]

but I do not know how to generate something like this based on different input strings.

I have read many StackOverflow posts related to trees, discriminated unions, and creating recursive types like this dynamically but I have not found anything that fits my needs. I have tried modifying the few examples that I have found and the closest I found was an answer by Tomas Petricek at F# transform list to a tree. Plugging in the union cases and the pattern matching for them to get this to work got me a lot closer, but it left off a lot of commands and duplicated some of the others.

This is the best that I have come up with so far, but it does not get all of the commands.

/// Takes the indent,command pairs list and produces a list of commands. 
/// Some of these are nested in a tree structure based on their indent.
let buildProgram (diagram:(int*string) list) : Command list =   
    let rec collect indx lis commands =
        match lis with
        | [] -> commands
        | x::xs ->
            match fst x with
            | i when i = indx -> 
                match split (snd x) with
                | "Forward"::NUM n::tail -> collect i xs commands@[Forward 
n]
                | "Turn"::ARG a::NUM n::tail -> collect i xs 
commands@[Turn(a,n)]
                | "Repeat"::NUM n::tail -> commands@([(Repeat (n, (collect 
(i+1) xs [])))] |> List.rev)
            | i when i < indx ->
                match split (snd x) with
                | "Forward"::NUM n::tail -> collect (i-1) xs 
commands@[Forward n]
                | "Turn"::ARG a::NUM n::tail -> collect (i-1) xs 
commands@[Turn(a,n)]
                | "Repeat"::NUM n::tail -> commands@([(Repeat (n, (collect 
(i-1) xs [])))] |> List.rev)
    collect 0 diagram [] |> List.rev

How do you create a recursive discriminated union at runtime based on different inputs?

Answer 1

What you're trying to do there is to write a parser for your indentation-based syntax that would produce values of type Command.

You can certainly roll one by hand, but the general advice would be to use a parser combinator library such as FParsec. FParsec does have a steep learning curve, but it's "the way to go" for writing parsers in F#.

You will find this article particularly helpful if you decide to go with that - Parsing indentation based syntax with FParsec.