SML/ML Int conversion chaîne

Question

J'ai ce code:

datatype 'a Tree = Empty | LEAF of 'a | NODE of ('a Tree) list; 
val iL1a = LEAF 1; 
val iL1b = LEAF 2; 
val iL1c = LEAF 3; 
val iL2a = NODE [iL1a, iL1b, iL1c]; 
val iL2b = NODE [iL1b, iL1c, iL1a]; 
val iL3 = NODE [iL2a, iL2b, iL1a, iL1b]; 
val iL4 = NODE [iL1c, iL1b, iL3]; 
val iL5 = NODE [iL4]; 

fun treeToString f Node = let 
    fun treeFun (Empty) = ["(:"] 
    | treeFun (NODE([])) = [")"] 
    | treeFun (LEAF(v)) = [f v] 
    | treeFun (NODE(h::t)) = [""] @ (treeFun (h)) @ (treeFun (NODE(t))) 
    in 
    String.concat(treeFun Node) 
end; 

treeToString Int.toString iL5; 

Quand je lance ma fonction je reçois la sortie: "32123) 231) 12)))".

La réponse devrait être "((32 ((123) (231) 12)))".

J'ai essayé de modifier ma fonction d'ajouter (dans tous les endroits que je peux penser, mais je ne peux pas savoir où je devrais ajouter « (» Où ai-je foiré

Edit:.? Je crois que je dois pour utiliser map ou List.filter quelque part, mais je ne suis pas sûr où

Answer 1

Il semble que votre méthode de récursion sur la queue d'un noeud de liste est le problème. Au lieu de treeFun h ajouté à treefun (NODE(t)), essayez d'utiliser ceci pour le nœud case:

treeFun (NODE(items)) = ["("] @ List.concat (map treeFun items) @ [")"] 

C'est-à-dire, la carte treeFun sur tout le contenu du nœud, et entourer les résultats avec "(" et ")". Cette définition pourrait être un peu trop laconique pour vous de comprendre ce qui se passe, alors voici une forme plus bavard que vous trouverez peut-être plus claire:

| treeFun (NODE(items)) = 
    let val subtree_strings : string list list = map treeFun items 
     val concatenated_subtrees : string list = List.concat subtree_strings 
     in ["("] @ concatenated_subtrees @ [")"] 
     end 

subtree_strings est le résultat de prendre toutes les sous-arbres dans le noeud donné, et transformer chacun d'entre eux en une liste de chaînes en appelant récursivement treeFun sur chaque sous-arbre. Puisque treeFun renvoie une liste de chaînes à chaque fois qu'elle est appelée, et que nous l'appelons sur une liste entière de sous-arborescences, le résultat est une liste correspondante de listes de sous-arborescences. Ainsi, par exemple, si nous appelions map treeFun [LEAF 1, LEAF 2, LEAF 3], nous obtiendrions [["1"], ["2"], ["3"]].

Ce n'est pas la réponse que nous voulons, car c'est une liste de listes de chaînes plutôt qu'une liste de chaînes de caractères. Nous pouvons corriger cela en utilisant List.concat, qui prend une liste de listes, et forme une seule liste de tous les éléments sous-jacents. Par exemple, List.concat [["1"], ["2"], ["3"]] renvoie ["1", "2", "3"]. Maintenant tout ce que nous avons à faire est de mettre les parenthèses autour du résultat, et nous avons fini.

Notez que cette stratégie fonctionne aussi bien pour les noeuds complètement vides que pour les noeuds avec un ou plusieurs sous-arbres, ce qui élimine le besoin du deuxième cas de treeFun dans votre définition d'origine. Généralement, dans ML, c'est une odeur de code si une fonction d'un argument n'a pas exactement un cas pour chaque constructeur du type de l'argument.