Produit d'arbre Éléments smlnj

Question

Je le qtree datatype suivant:

datatype 'a qtree = Leaf of 'a 
| Node of 'a branches 
and 'a branches = Empty 
| Branch of 'a qtree * 'a branches 

Un arbre exemple est défini comme suit:

val tr1 = 
Node(Branch(Leaf(2), 
    Branch(Node(Branch(Leaf(6), 
    Branch(Leaf(5),Empty))), 
Branch(Node(Empty),Empty)))) 

Voici une représentation visuelle de tr1:

/|\ 
/| \ 
2/\ 
/ \ 
6  5 

J'ai défini la fonction suivante tree_prod à fin d le produit des valeurs dans un qtree:

fun tree_prod(Leaf(n)) = n 
| tree_prod(Empty) = 1 
| tree_prod(Node(br)) = tree_prod(br) 
| tree_prod(Branch(n, br)) = tree_prod(n) * tree_prod(br) 

Mais je reçois les erreurs suivantes, qui semblent se produire en raison d'un type mixup entre qtree et branches:

stdIn:10.5-13.42 Error: parameter or result constraints of clauses don't 
agree [tycon mismatch] 
    this clause:  'Z branches -> 'Y 
    previous clauses:  'X qtree -> 'Y 
    in declaration: 
    tree_prod = 
     (fn Leaf n => n 
     | Empty => 1 
     | Node br => tree_prod br 
     | Branch (<pat>,<pat>) => tree_prod <exp> * tree_prod <exp>) 
stdIn:10.5-13.42 Error: parameter or result constraints of clauses don't 
agree [tycon mismatch] 
    this clause:  'Z branches -> 'Y 
    previous clauses:  'X qtree -> 'Y 
    in declaration: 
    tree_prod = 
     (fn Leaf n => n 
     | Empty => 1 
     | Node br => tree_prod br 
     | Branch (<pat>,<pat>) => tree_prod <exp> * tree_prod <exp>) 
stdIn:12.19-12.27 Error: operator and operand don't agree [tycon mismatch] 
    operator domain: [int ty] qtree 
    operand:   [int ty] branches 
    in expression: 
    tree_prod br 
stdIn:13.24-13.42 Error: operator and operand don't agree [tycon mismatch] 
    operator domain: [int ty] qtree 
    operand:   [int ty] branches 
    in expression: 
    tree_prod br 

Comment puis-je résoudre ces erreurs?

Bonus: Comment implémenter cette fonction en utilisant fold?

Answer 1

J'ai trouvé la réponse par moi-même. En divisant cela en deux fonctions distinctes, je suis en mesure de spécifier les types avec lesquels je veux travailler.

Voici la solution de travail:

fun tree_prod (Leaf(n)) = n 
| tree_prod (Node(br)) = branches_prod(br) 
and branches_prod (Empty) = 1 
| branches_prod (Branch(n, br)) = 
    tree_prod(n) * branches_prod(br) 

Answer 2

Vos tree_prod tentatives d'appliquer aux deux types, qui ne fonctionnent pas - vous avez besoin de deux fonctions.

S'il est possible pour vous de changer le type, vous pouvez utiliser le fait que 'a branches est isomorphe à une liste de 'a qtree (avec Empty comme nil et Branch comme cons).

datatype 'a qtree = Leaf of 'a 
        | Node of ('a qtree) list 

et vous pouvez replier sur les branches:

fun tree_prod (Leaf n) = n 
    | tree_prod (Node br) = List.foldl (fn (tree, acc) => tree_prod tree * acc) 1 br 

val tr1 = Node [Leaf 2, Node [Leaf 6, Leaf 5], Node []] 
- tree_prod tr1; 
val it = 60 : int 

Si vous ne voulez pas changer le type, vous pouvez écrire votre propre fois sur 'a branches, suivant la même forme que la liste -plier.
Quelque chose comme cela pourrait le faire:

fun branch_fold f x Empty = x 
    | branch_fold f x (Branch t bs) = branch_fold f (f (t, x)) bs 

et donnerait un "produit" presque identique:

fun tree_prod (Leaf n) = n 
    | tree_prod (Node br) = branch_fold (fn (tree, acc) => tree_prod tree * acc) 1 br