为什么我实现的OCaml map函数处理元素时输出顺序是反向的？

原因说明 #

这个现象是OCaml默认的函数参数求值顺序规则导致的：

• OCaml中所有函数调用的参数默认按从右到左的顺序求值
• 你代码中递归分支的f hd :: map f tl本质是调用列表构造函数(::)，等价于(::) (f hd) (map f tl)：::接收两个参数，第一个是新列表的头元素，第二个是处理完成的尾列表
• 按照从右到左的求值规则，会先计算第二个参数map f tl的结果，再计算第一个参数f hd的结果

执行过程拆解（输入为[1;2;3]时） #

1. 调用map print_id [1;2;3]，匹配到hd=1, tl=[2;3]，要计算(::) (print_id 1) (map print_id [2;3])，优先计算右参数map print_id [2;3]
2. 调用map print_id [2;3]，匹配到hd=2, tl=[3]，要计算(::) (print_id 2) (map print_id [3])，优先计算右参数map print_id [3]
3. 调用map print_id [3]，匹配到hd=3, tl=[]，要计算(::) (print_id 3) (map print_id [])，优先计算右参数map print_id []返回空列表
4. 接下来计算当前层::的左参数print_id 3，触发打印3，得到列表[3]返回上一层
5. 上一层计算::的左参数print_id 2，触发打印2，得到列表[2;3]返回上一层
6. 最上层计算::的左参数print_id 1，触发打印1，得到最终返回值[1;2;3]

这个过程正好对应你观察到的「打印顺序是3、2、1，返回列表还是正序」的结果。

修复方案 #

如果需要打印顺序和列表顺序保持一致，只需要调整代码强制先求值f hd再递归即可：

let rec map f lst =
    match lst with
    | [] -> []
    | hd :: tl -> 
        let processed_hd = f hd in (* 先执行f hd，触发打印 *)
        processed_hd :: map f tl

修改后运行测试代码，控制台就会按1、2、3的顺序打印，返回值依然为[1;2;3]。

内容的提问来源于stack exchange，提问作者Flux