标准 ML：简化递归调用

Question

我的书对中序遍历有以下定义（它计算一个列表，其中树的元素在列表中按顺序排列：

fun trav Empty = []
    | trav(Node(t_1, x, t_2)) = trav t_1 @ (x::trav t_2);

简化第二行调用的约定/标准是什么（即 trav t_1 和 x::trav t_2）？我知道我在使用 @ 运算符之前简化了它们，但我想知道第一个 trav 调用是否在另一个调用之前完全评估，反之亦然（不太可能），或者两者同时进行.

谢谢

克莱曼

Answer 1

您的直觉是正确的，trav t_1 首先被求值，因为函数参数是按从左到右的顺序求值的。这可能看起来有点奇怪，因为 @ 是一个中缀运算符，但 [1, 2, 3] @ [4, 5, 6] 实际上可以重写为 (op @)([1, 2, 3], [4, 5, 6])。您可以通过执行以下操作来验证 @ 首先评估其左参数：

Standard ML of New Jersey v110.78 [built: Sun Jun  7 20:21:33 2015]
- (print "test1\n"; [1, 2, 3]) @ (print "test2\n"; [4, 5, 6]);
test1
test2
val it = [1,2,3,4,5,6] : int list
-

基本上你所拥有的相当于：

fun trav Empty = []
  | trav(Node(t_1, x, t_2)) = 
     let val l = trav t_1 
         val r = trav t_2
     in l @ (x::r) end

标准 ML：简化递归调用

Standard ML: Simplifying Recursive Calls

functional-programming

sml