树元积SMLNJ

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来查找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

如何纠正这些错误？

奖励:如何使用折叠实现此功能？

Answer 1

我自己找出了答案。通过将其划分为两个独立的函数，我能够指定我想要使用的类型。

以下是工作解决方案：

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的列表同构( Empty为nil，Branch为cons)。

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