Analyse de l'arborescence d'expressions en listes imbriquées

Question

Je suis relativement nouveau à F # et j'ai vraiment du mal à analyser un arbre d'expression qui contient des listes imbriquées. De morceaux sur le web j'ai bricolé ensemble ce qui suit.

Mon type standard est défini:

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

Je fais un appel de fonction à une application externe, qui retourne quelque chose comme:

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

et que j'ai besoin d'analyser en

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

Ma première pensée naïve était sur le modèle de

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

mais il se plaint des différences de type, que je comprends maintenant. Ma deuxième pensée est peut-être d'utiliser List.fold récursif (comme je peux replier la liste des Reals et obtenir les listes internes, mais ne peux pas comprendre comment généraliser dans une fonction récursive sans que le compilateur se plaint type de sortie). Au-delà de mon pouvoir de feu intellectuel actuel. Ma troisième pensée est que peut-être le retour que je reçois de l'application externe rend cela trop difficile, car il n'y a aucune indication dans le tuple fst sur ce qui est dans le tndle snd, en dehors du fait qu'il s'agit d'une "liste de quelque chose"?

Il y a ceci: Convert tree to list mais c'est aussi énigmatique que les solutions que j'essaye tbh.

Toute indication quant à l'avenue que je poursuis serait vraiment appréciée.

Answer 1

Quel est le type de l'objet que vous voulez que votre fonction parse renvoie?

Si votre sortie désirée est [ [1.0; 2.0; 3.0] ; [1.0; 2.0; 3.0] ; [1.0; 2.0; 3.0] ], il semble que ce que vous voulez revenir est ni float list ni float list list, mais plutôt une liste imbriquée arbitrairement de float.

Mais cela n'existe pas comme un type standard, et vous aurez besoin de définir vous-même comme une union discriminée récursif (nous allons le faire générique pour les bonnes pratiques):

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

Regardez bien à ce! C'est juste une reskin fine sur votre type original Return. En effet, le type d'origine est à peu près déjà une implémentation de liste imbriquée standard, à l'exception de la propriété d'étiquette "List".

La fonction parse a alors presque pas de travail réel à faire:

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

Parfois, il est bon d'annoter la fonction que vous implémentez. Ensuite, il devient explicite de ce que vous essayez de faire:

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" 

Votre x |> List.map parse a un type float list list mais autre branche votre expression a un type float. Ai-je raison de dire que vous avez essayé de retourner float list?