F# - 在运行时创建递归可区分联合

Question

我正在尝试使用 F# 编写一个简单的解释器来控制 Turtle。
我创建了以下递归联合类型来表示 Turtle 将接受的少数命令。该代码将由 "Command list" 表示，使用简单的递归函数执行起来应该不会太难。

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

我想把这个解释器画成白色 space 以便源代码看起来如下。

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

然后我使用这个函数根据缩进级别将所有内容分隔到一个 int*string 列表中。所以 Repeat 4 会变成 (0, "Repeat 4")，Forward 10 会变成 (1, "Forward 10")，Turn Left 30 会变成 (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

现在这就是我卡住的地方。我有命令列表及其缩进级别，但我不知道如何动态创建递归可区分联合。我知道如何对其进行硬编码。它看起来像这样，

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]

但我不知道如何根据不同的输入字符串生成这样的东西。

我已经阅读了许多 Whosebug 上与树、可区分联合和动态创建递归类型相关的帖子，但我没有找到适合我需要的内容。我尝试修改我找到的几个例子，我找到的最接近的例子是 Tomas Petricek 在 F# transform list to a tree 的回答。插入联合案例和模式匹配让他们工作让我更接近，但它遗漏了很多命令并重复了一些其他命令。

这是迄今为止我想出的最好的，但它并没有得到所有的命令。

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

如何根据不同的输入在运行时创建递归的可区分联合？

Answer 1

您要做的是为基于缩进的语法编写解析器，该解析器将生成 Command 类型的值。

您当然可以手动滚动一个，但一般建议是使用解析器组合器库，例如 FParsec。 FParsec 确实有一个陡峭的学习曲线，但它是 "the way to go" 用于在 F# 中编写解析器。

如果您决定使用这篇文章，您会发现这篇文章特别有用 - Parsing indentation based syntax with FParsec。

F# - 在运行时创建递归可区分联合

F# - Create a Recursive Discriminated Union at Runtime

recursion

f#

interpreter

unions