Standard ML: Simplifying Recursive Calls

Question

My book has the following definition of inorder traversal (it computes a list with the elements of the tree in the inorder order within a list:

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

What's the convention / standard for simplifying the calls in the second line (namely, trav t_1 and x::trav t_2)? I know I simplify both of them before making use of the @ operator but I'd like to know whether the first trav call evaluates completely before the other call, vice versa (unlikely), or both simultaneously.

Thanks

bclayman

Answer 1

Your intuition is correct, trav t_1 gets evaluated first as function arguments are evaluated in left to right order. This might seem a little strange, since @ is an infix operator, but [1, 2, 3] @ [4, 5, 6] can actually be rewritten as (op @)([1, 2, 3], [4, 5, 6]). You can verify that @ evaluates its left argument first by doing:

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
- 

Essentially what you have is equivalent to:

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