CODEWITHSUNDEEP
functional-programmingsml
anon_swe
anon_swe

Reputation: 9355

Standard ML: Simplifying Recursive Calls

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

Upvotes: 1

Views: 65

Answers (1)

Matt
Matt

Reputation: 4049

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

Upvotes: 1

Related Questions