为什么我执行的 "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]returns[1; 2; 3]，上面的代码打印：

3
2
1

似乎正在倒序处理列表！发生了什么事？

Answer 1

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

f hd :: map f tl

被允许在调用 f.

之前评估对 map 的调用

可以使用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

为什么我执行的 "map" 处理元素的顺序是相反的？

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

ocaml