fonction SML pour retourner une liste d'éléments d'un arbre soulève une exception

Question

J'ai une mission de PMG et l'une des questions est de mettre en œuvre une fonction

findAll : (int -> bool) -> binary search tree -> int list 

Je donne les résultats suivants jusqu'à présent:

datatype 'a tree = Empty | Node of (int * 'a tree * 'a tree) 

exception answer of int list 

fun findAll f Empty = raise answer [] 
    | findAll f (Node(x, l, r)) = 
    if (f x) then raise answer(x)::(findAll f l)::(findAll f r) 
    else 
     (findAll f l)::(findAll f r) 

Fondamentalement, findAll prend dans une fonction booléenne et renvoie tous les nœuds qui satisfont cette fonction sous la forme d'une exception. Je sais pourquoi mon code ne fonctionne pas, car il y aura une réponse (raise response) à l'intérieur de l'original (raise answer) mais de toute façon ce n'est pas la compilation. Je me demandais ce que je devrais faire pour résoudre ce problème. Je ne peux pas appeler une fonction d'assistance qui récupère tous les éléments et appelle simplement l'exception, je devrais cependant utiliser l'exception de transport de valeur. Je devrais aussi être capable de retourner tous les éléments dans l'ordre.

Answer 1

Vous ne citez pas les messages d'erreur ou ne dites pas quel compilateur vous utilisez. Voici ce que je reçois de SML/NJ:

3867615/john316.sml:7.25-7.64 Error: operator and operand don't agree [tycon mismatch] 
    operator domain: int list 
    operand:   int 
    in expression: 
    answer x 
3867615/john316.sml:7.25-7.64 Error: operator and operand don't agree [circularity] 
    operator domain: 'Z * 'Z list 
    operand:   'Z * 'Z 
    in expression: 
    (findAll f) l :: (findAll f) r 
3867615/john316.sml:7.25-7.64 Error: argument of raise is not an exception [tycon mismatch] 
    raised: _ list 
    in expression: 
    raise (answer x :: (findAll <exp>) l :: (findAll <exp>) r) 
3867615/john316.sml:9.9-9.37 Error: operator and operand don't agree [circularity] 
    operator domain: 'Z * 'Z list 
    operand:   'Z * 'Z 
    in expression: 
    (findAll f) l :: (findAll f) r 

La première erreur devrait être assez claire: answer est déclaré attendre un argument int list, mais answer x utilise un x qui vient d'un Node et doit être un int. La troisième erreur est probablement un problème de précédence: vous pouvez voir comment le compilateur a analysé votre expression, et ce n'est probablement pas ce que vous vouliez. La deuxième et la quatrième erreur sont dues au fait que vous confondiez le constructeur :: ("cons"), qui ajoute un élément au début de une liste, avec l'opérateur @ ("append"), qui concatène deux listes.

Maintenant, je reviens à l'exception answer. Pourquoi est-ce? Votre fonction doit trouver toutes les occurrences, elle doit donc traverser l'arbre entier. Il n'y a aucune circonstance qui vous obligerait à revenir tôt. Ainsi, vous n'avez pas besoin d'exception. Vous avez essentiellement l'algorithme correct (dans une arborescence vide, il n'y a pas de correspondance donc retournez la liste vide, dans un nœud, ajoutez la correspondance au résultat de l'appel récursif si présent), ne compliquez pas les choses.

Faire les deux corrections, nous obtenons le code suivant (qui compile):

fun findAll f Empty = [] 
    | findAll f (Node(x, l, r)) = 
    if f x then x :: findAll f l @ findAll f r 
    else findAll f l @ findAll f r