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

user_5916915 0
Viewed 110

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?

ocaml
3 Answers

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
user_8216790

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] *)
user_116979360

One more point, in addition to the excellent answers already offered. The standard library implements both List.map and List.iter. The latter has the type ('a -> unit) -> 'a list -> unit and is typically used when side effects are the point of iterating over a list, rather than constructing a new list.

You can trivially implement this yourself. It has the benefit of making evaluation order explicitly what you want, and it's naturally tail-recursive.

let rec iter f = function
  | [] -> ()
  | hd::tl -> f hd; iter f tl
user_152613150
Related