Analysieren des Ausdrucksbaums in verschachtelte Listen

Question

Ich bin relativ neu in F # und habe wirklich einen echten Kampf mit dem Parsen eines Ausdrucksbaums, der verschachtelte Listen enthält. Aus Kleinigkeiten im Internet habe ich folgendes zusammengeschustert.

Mein Standardtyp definiert:

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

ich einen Funktionsaufruf an eine externe Anwendung zu machen, die wie etwas zurückgibt:

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

und die ich in

zu analysieren bin benötigen

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

Mein ursprünglicher naive Gedanke war entlang der Linien

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

aber es beschwert sich über die Typenunterschiede, die ich jetzt verstehe.

Mein zweiter Gedanke ist, vielleicht einige rekursive List.fold zu verwenden (wie ich kann über die Liste der Reals und die inneren Listen, aber nicht herausfinden, wie es in eine rekursive Funktion zu verallgemeinern, ohne den Compiler beschweren aus Typ). Jenseits meiner gegenwärtigen intellektuellen Feuerkraft.

Mein dritter Gedanke ist, dass vielleicht die Rückkehr, die ich von der externen Anwendung bekomme, dies zu schwierig macht, da es im Tupel fst keinen Hinweis darauf gibt, was in dem Tupel-Snd ist, abgesehen davon, dass es eine "Liste" ist von etwas"?

Es ist das: Convert tree to list aber es ist so kryptisch wie die Lösungen, die ich tbh versuche.

Irgendwelche Hinweise, auf welche Avenue ich verfolge, würde wirklich geschätzt werden.

Answer 1

Was ist der Typ des Objekts, das die parse-Funktion zurückgeben soll?

Wenn Sie die gewünschte Ausgabe [ [1.0; 2.0; 3.0] ; [1.0; 2.0; 3.0] ; [1.0; 2.0; 3.0] ] ist, scheint es, dass Sie wollen, was zurückzukehren ist weder ein float list noch ein float list list, sondern eine willkürlich Liste von float verschachtelt.

Aber das ist nicht als Standardausführung gibt es, und Sie werden es definieren, müssen Sie sich als rekursive diskriminiert Vereinigung (wir es für eine gute Praxis Generika machen):

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

Nun suchen dabei! Es ist nur eine dünne Reskin über Ihrem ursprünglichen Return Typ. Das liegt daran, dass der Originaltyp bereits eine Standard-Implementierung einer verschachtelten Liste ist, mit Ausnahme der "List" Label-Sache.

Die parse Funktion hat dann fast keine wirkliche Arbeit noch zu tun:

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

Answer 2

Manchmal ist es gut, die Funktion zu notieren, die Sie implementieren. Dann wird es explizit von dem, was Sie zu tun versuchen:

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

let rec parse (data : Return) : float list = 
    match data with 
    | Real y -> [ y ] 
    | Func (_, returns) -> returns |> List.collect parse 
    | _ -> failwithf "Unrecognised" 

Ihre x |> List.map parse hat einen Typen float list list aber auf anderem Zweig Ihres Ausdruck hat einen Typen float. Habe ich Recht, dass Sie versucht haben, float list zurückzugeben?