OCaml子列表长度排序代码疑问：比较函数与List.map snd解析

let rec insert cmp e = function 
  | [] -> [e] 
  | h :: t as l -> 
    if cmp e h <= 0 then e :: l 
    else h :: insert cmp e t

let rec sort cmp = function
  | [] -> []
  | h :: t -> insert cmp h (sort cmp t)

let length_sort lists =
  let lists = List.map (fun list -> List.length list, list) lists in
  let lists = sort (fun a b -> compare (fst a) (fst b)) lists in
  List.map snd lists;;

问题1：fun a b -> compare (fst a) (fst b) 函数的工作机制是什么？ #

这个匿名函数是给排序逻辑提供比较规则的：

• 它接收两个元组参数a和b（每个元组都是(子列表长度, 原列表)的结构）
• 用fst分别取出两个元组的第一个元素，也就是对应子列表的长度值
• 调用OCaml内置的compare函数对这两个长度值做比较，返回的结果会决定a和b在排序后的列表里的先后位置

问题2：compare 函数的返回值是否仅为1或-1？ #

不是。OCaml的compare函数返回值有三种情况：

• 若第一个参数小于第二个，返回-1
• 若两个参数相等，返回0
• 若第一个参数大于第二个，返回1
  它支持所有可比较类型（整数、字符串、元组等）的比较操作。

问题3：传递给 sort 函数的变量具体是什么？ #

传递给sort的有两个部分：

1. 第一个参数是上述的匿名比较函数，用来定义排序的依据规则
2. 第二个参数是经过List.map转换后的列表——这个列表里的每个元素都是(子列表长度, 原子列表)的元组，是从输入的lists转换而来的

问题4：List.map snd lists 是否会移除列表中每个子列表的第一个元素？ #

不会。这里的lists里的元素是(长度, 原列表)的元组，snd函数的作用是取出元组的第二个元素（也就是原子列表本身），所以List.map snd lists只是把所有元组里的原子列表提取出来组成新列表，完全不会修改子列表内部的元素。

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