Why is my implementation of "map" processing elements in reverse order?

Question

This is my implementation of map:

let rec map f lst =
    match lst with
    | [] -> []
    | hd :: tl -> f hd :: map f tl

I tried to run it like this:

(* Print the given int, then return the given int. *)
let print_id n =
    print_int n;
    print_newline ();
    n

let () = ignore (map print_id [1; 2; 3])

Although map print_id [1; 2; 3] returns [1; 2; 3], the code above prints:

3
2
1

It seems that the list is being processed in reverse order! What is happening?

Answer 1

OCaml doesn't guarantee an order for evaluation of an expression. So this expression:

f hd :: map f tl

is permitted to evaluate the call to map before the call to f.

You can use let to guarantee an evaluation order:

let x = f hd in
x :: map f tl

Answer 2

With following reduction order for the function map, things will be clear enough to you hopefully.

map print_id [1; 2; 3]
print_id 1 :: map print_id [2; 3]
print_id 1 :: print_id 2 :: map print_id [3]
print_id 1 :: print_id 2 :: print_id 3 :: map print_id []
print_id 1 :: print_id 2 :: print_id 3 :: []      (* print_id 3, prints 3 and returns 3 *)
print_id 1 :: print_id 2 :: 3 :: []               (* print_id 2, prints 2 and returns 2 *)        
print_id 1 :: 2 :: 3 :: []                        (* print_id 1, prints 1 and returns 1 *)
1 :: 2 :: 3 :: []                                 (* List Construction yields [1; 2; 3] *)