为什么我的“map”处理元素的实现顺序是相反的？

Question

这是我的实现

map

：

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

我尝试像这样运行它：

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

虽然

map print_id [1; 2; 3]

返回

[1; 2; 3]

，但上面的代码打印：

3
2
1

列表似乎正在以相反的顺序处理！发生什么事了？

Answer 1

OCaml 不保证表达式求值的顺序。所以这个表达：

f hd :: map f tl

允许在调用

map

之前评估对

f

的调用。

您可以使用

let

来保证评估订单：

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

Answer 2

通过以下函数的归约顺序

map

，希望事情对您来说足够清楚。

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

Answer 3

除了已经提供的出色答案之外，还有一点。标准库同时实现了

List.map

和

List.iter

。后者的类型为

('a -> unit) -> 'a list -> unit

，通常在副作用是迭代列表而不是构造新列表时使用。

您可以自己简单地实现这一点。它的好处是可以明确地按照您想要的顺序进行评估，并且它自然是尾递归的。

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