f# - 将表达式树解析为嵌套列表

Question

我对 F# 比较陌生，在解析包含嵌套列表的表达式树时确实遇到了困难。我根据网上的零碎内容拼凑了以下内容。

我的标准类型已定义:

type Return = 
    | Real of float
    | Func of string * Return list

我对外部应用程序进行函数调用，它返回如下内容:

val out : Return =
    Func
        ("List",
             [Func ("List",[Real 1.0; Real 2.0; Real 3.0]);
              Func ("List",[Real 1.0; Real 2.0; Real 3.0]);
              Func ("List",[Real 1.0; Real 2.0; Real 3.0])])

我需要解析它

[ [1.0; 2.0; 3.0] ; [1.0; 2.0; 3.0] ; [1.0; 2.0; 3.0] ]

我最初天真的想法是这样的

let rec parse data =
    match data with
    | Real(y) -> y
    | Func("List", x) -> x |> List.map parse 
    | _ -> failwithf "Unrecognised"

但它提示类型差异，我现在明白了。

我的第二个想法是也许使用一些递归 List.fold (因为我可以折叠 Reals 列表并获取内部列表，但无法弄清楚如何将其概括为递归函数而不让编译器提示类型)。超出我目前的智力火力。

我的第三个想法是，也许我从外部应用程序获得的返回使这变得太困难，因为元组 fst 中没有任何关于元组 snd 中内容的指示，除了它是一个“列表”之外，某事”？

有这个:Convert tree to list但它和我正在尝试的解决方案一样神秘。

任何关于我追求哪条道路的指示将不胜感激。

Answer 1

您希望 parse 函数返回的对象类型是什么？

如果您想要的输出是[ [1.0; 2.0； 3.0]； [1.0； 2.0； 3.0]; [1.0； 2.0； 3.0] ]，看起来你想要返回的既不是float list也不是float list list，而是一个任意嵌套的列表 float 。

但这并不作为标准类型存在，您需要自己将其定义为递归可区分联合(我们将使其通用以获得良好的实践):

type NestedList<'a> = 
    | Single of 'a
    | Collection of NestedList<'a> list

好吧，看看那个!它只是对原始 Return 类型进行了薄层重新设计。这是因为原始类型几乎已经是标准的嵌套列表实现，除了 "List" 标签之外。

parse 函数几乎没有什么实际工作要做:

let rec parse = function
    | Real y ->  Single y
    | Func ("List", returns) -> Collection (returns |> List.map parse)
    | Func (l, _) -> failwithf "Unrecognised label %s" l