树元素 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

如何修复这些错误？

奖励：如何使用 fold 实现此功能？

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

并且会给出几乎相同的 "product":

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

树元素 SMLNJ 的乘积

Product of Tree Elements SMLNJ

sml

smlnj