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