製品

Question

私は、次のqtreeデータ型があります。

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

例えば次のようにツリーが定義されています。ここでは

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

はtr1の視覚的な表現です：

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

を

以下の関数を定義しましたtree_prodをfin D 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) 

しかし、私が原因qtreeと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 

がどのように修正すればよいですこれらのエラー？

ボーナス：foldを使用してこの機能を実装するにはどうすればよいですか？

Answer 1

私は自分で答えを見つけました。これを2つの別々の関数に分割することで、どのタイプを扱いたいのかを指定することができます。 - あなたは、2つの機能を必要と動作しません。両方のタイプに適用する

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

あなたtree_prodの試み：ここ

は、実用的なソリューションです。あなたはタイプを変更することが可能なら

は、あなたが'a branchesが'a qtree（nilとしてEmptyとし、Branchconsなど）のリストに同型であるという事実を使用することができます。

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

、その後、あなたは枝の上に折り畳むことができます。

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 

あなたはタイプを変更したくない場合は、リストと同じ形式以下、'a branches上で、独自の倍に書くことができます - 倍。このような
何かがそれを行う可能性があります：

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

とほとんど同じ "製​​品" 与えるだろう：

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

を