(* 基本列表 *)
let empty = []
let numbers = [1; 2; 3; 4; 5]
let names = ["Alice"; "Bob"; "Charlie"]

(* 嵌套列表 *)
let nested = [[1; 2]; [3; 4]; [5; 6]]

(* 多类型列表需要使用变体类型 *)
type value = Int of int | Str of string
let mixed = [Int 1; Str "hello"; Int 42]

(* cons 操作 *)
let lst = 1 :: [2; 3; 4]
(* => [1; 2; 3; 4] *)

let lst' = 0 :: lst
(* => [0; 1; 2; 3; 4] *)

(* 列表字面量就是 cons 的语法糖 *)
let lst'' = 1 :: 2 :: 3 :: []
(* => [1; 2; 3] *)

(* 模式匹配中使用 :: *)
let head_tail lst =
  match lst with
  | [] -> (None, [])
  | x :: rest -> (Some x, rest)

let _ = head_tail [1; 2; 3]  (* => (Some 1, [2; 3]) *)
let _ = head_tail []          (* => (None, []) *)

let combined = [1; 2] @ [3; 4; 5]
(* => [1; 2; 3; 4; 5] *)

let with_head = [0] @ List.init 10 Fun.id
(* => [0; 0; 1; 2; 3; 4; 5; 6; 7; 8; 9] *)

(* O(n) 时间，O(n) 空间 *)
let squares = List.map (fun x -> x * x) [1; 2; 3; 4; 5]
(* => [1; 4; 9; 16; 25] *)

let upper = List.map String.uppercase_ascii ["hello"; "world"]
(* => ["HELLO"; "WORLD"] *)

(* mapi — 带索引的 map *)
let indexed = List.mapi (fun i x -> (i, x)) ["a"; "b"; "c"]
(* => [(0, "a"); (1, "b"); (2, "c")] *)

(* O(n) *)
let evens = List.filter (fun x -> x mod 2 = 0) [1; 2; 3; 4; 5; 6]
(* => [2; 4; 6] *)

let non_empty = List.filter (fun s -> s <> "") [""; "hello"; ""; "world"]
(* => ["hello"; "world"] *)

(* filteri — 带索引的 filter *)
let even_indexed = List.filteri (fun i _ -> i mod 2 = 0) [10; 20; 30; 40; 50]
(* => [10; 30; 50] *)

(* O(n)，尾递归，推荐使用 *)
let sum = List.fold_left (+) 0 [1; 2; 3; 4; 5]
(* => 15 *)

let product = List.fold_left ( * ) 1 [1; 2; 3; 4; 5]
(* => 120 *)

(* 构建字符串 *)
let csv = List.fold_left
  (fun acc s -> if acc = "" then s else acc ^ "," ^ s)
  ""
  ["name"; "age"; "city"]
(* => "name,age,city" *)

(* 计算平均值 *)
let average lst =
  let (sum, count) = List.fold_left
    (fun (s, c) x -> (s +. x, c + 1))
    (0.0, 0) lst
  in
  sum /. float_of_int count

let _ = average [10.0; 20.0; 30.0]  (* => 20.0 *)

(* 计数器 *)
let count_chars c str =
  List.fold_left
    (fun acc ch -> if ch = c then acc + 1 else acc)
    0
    (List.init (String.length str) (String.get str))

let _ = count_chars 'l' "hello world"  (* => 3 *)

(* O(n)，非尾递归（注意栈深度） *)
let lst = List.fold_right (fun x acc -> x :: acc) [1; 2; 3] []
(* => [1; 2; 3]，等价于 List.copy *)

(* fold_right 的常见用法：构建新列表 *)
let doubled = List.fold_right (fun x acc -> (x * 2) :: acc) [1; 2; 3] []
(* => [2; 4; 6] *)

(* fold_left vs fold_right *)
let left = List.fold_left (fun acc x -> acc ^ x) "" ["a"; "b"; "c"]
(* => "abc" *)

let right = List.fold_right (fun x acc -> x ^ acc) ["a"; "b"; "c"] ""
(* => "abc" *)

(* 顺序差异示例 *)
let left_sub = List.fold_left (-) 10 [1; 2; 3]
(* => ((10 - 1) - 2) - 3 = 4 *)

let right_sub = List.fold_right (-) [1; 2; 3] 10
(* => 1 - (2 - (3 - 10)) = 1 - (2 - (-7)) = 1 - 9 = -8 *)

(* 默认升序 *)
let sorted = List.sort compare [3; 1; 4; 1; 5; 9; 2; 6]
(* => [1; 1; 2; 3; 4; 5; 6; 9] *)

(* 降序 *)
let desc = List.sort (fun a b -> compare b a) [3; 1; 4; 1; 5]
(* => [5; 4; 3; 1; 1] *)

(* 按字符串长度排序 *)
let by_length = List.sort (fun a b ->
  compare (String.length a) (String.length b))
  ["banana"; "apple"; "kiwi"; "fig"]
(* => ["fig"; "kiwi"; "apple"; "banana"] *)

(* 按记录字段排序 *)
type person = { name : string; age : int }
let people = [
  { name = "Alice"; age = 30 };
  { name = "Bob"; age = 25 };
  { name = "Charlie"; age = 35 };
]
let by_age = List.sort (fun a b -> compare a.age b.age) people

(* 返回第一个满足条件的元素，未找到抛出 Not_found *)
let first_even = List.find (fun x -> x mod 2 = 0) [1; 3; 4; 5; 6]
(* => 4 *)

(* 安全版本：使用 find_opt *)
let result = List.find_opt (fun x -> x > 10) [1; 2; 3]
(* => None *)

let result' = List.find_opt (fun x -> x > 2) [1; 2; 3; 4]
(* => Some 3 *)

(* 查找记录 *)
let alice = List.find_opt (fun p -> p.name = "Alice") people
(* => Some { name = "Alice"; age = 30 } *)

(* for_all：所有元素都满足条件 *)
let all_positive = List.for_all (fun x -> x > 0) [1; 2; 3; 4]
(* => true *)

let all_even = List.for_all (fun x -> x mod 2 = 0) [2; 4; 5]
(* => false *)

(* exists：至少一个元素满足条件 *)
let has_negative = List.exists (fun x -> x < 0) [1; -2; 3]
(* => true *)

let has_zero = List.exists (fun x -> x = 0) [1; 2; 3]
(* => false *)

(* List.length — 长度 O(n) *)
let len = List.length [1; 2; 3]  (* => 3 *)

(* List.rev — 反转 O(n) *)
let reversed = List.rev [1; 2; 3]  (* => [3; 2; 1] *)

(* List.append — 同 @ *)
let appended = List.append [1; 2] [3; 4]

(* List.concat — 扁平化嵌套列表 *)
let flat = List.concat [[1; 2]; [3; 4]; [5]]
(* => [1; 2; 3; 4; 5] *)

(* List.concat_map — map + concat *)
let expanded = List.concat_map (fun x -> [x; x * 10]) [1; 2; 3]
(* => [1; 10; 2; 20; 3; 30] *)

(* List.flatten — 同 concat *)
let flat' = List.flatten [[1; 2]; [3; 4]]

(* List.iter — 遍历（副作用） *)
let () = List.iter (fun x -> print_int x; print_char ' ') [1; 2; 3]
(* 输出: 1 2 3 *)

(* List.init — 创建列表 *)
let range = List.init 5 (fun i -> i)
(* => [0; 1; 2; 3; 4] *)

let squares = List.init 5 (fun i -> i * i)
(* => [0; 1; 4; 9; 16] *)

(* List.combine — 拉链 *)
let pairs = List.combine [1; 2; 3] ["a"; "b"; "c"]
(* => [(1, "a"); (2, "b"); (3, "c")] *)

(* List.split — 解拉链 *)
let (nums, strs) = List.split [(1, "a"); (2, "b"); (3, "c")]
(* => ([1; 2; 3], ["a"; "b"; "c"]) *)

(* List.mem — 成员检查 O(n) *)
let _ = List.mem 3 [1; 2; 3; 4; 5]  (* => true *)

(* List.assoc — 关联列表查找 *)
let config = [("host", "localhost"); ("port", "8080")]
let host = List.assoc "host" config  (* => "localhost" *)

(* List.partition — 分区 *)
let (pos, neg) = List.partition (fun x -> x > 0) [1; -2; 3; -4; 5]
(* => ([1; 3; 5], [-2; -4]) *)

(* List.split_at / List.take / List.drop (需要 OCaml 5.1+) *)
let left = List.filteri (fun i _ -> i < 3) [1; 2; 3; 4; 5]
(* => [1; 2; 3] *)

(* 模拟 [x * y | x <- [1..3], y <- [1..3], x <> y] *)
let pairs = List.init 3 (fun i -> i + 1) |> List.concat_map (fun x ->
  List.init 3 (fun i -> i + 1) |> List.filter_map (fun y ->
    if x <> y then Some (x * y) else None
  )
)
(* => [2; 3; 3; 6; 2; 6; 4; 6; 6; 8] — 顺序取决于嵌套 *)

(* 使用 let 定义辅助函数 *)
let flat_map f lst = List.concat_map f lst
let range n = List.init n (fun i -> i + 1)

let products =
  flat_map (fun x ->
    List.filter_map (fun y ->
      if x <> y then Some (x, y, x * y) else None
    ) (range 3)
  ) (range 3)

(* 尾递归的 length *)
let length lst =
  let rec aux acc = function
    | [] -> acc
    | _ :: rest -> aux (acc + 1) rest
  in
  aux 0 lst

(* 尾递归的 map *)
let map f lst =
  let rec aux acc = function
    | [] -> List.rev acc
    | x :: rest -> aux (f x :: acc) rest
  in
  aux [] lst

(* 尾递归的 filter *)
let filter pred lst =
  let rec aux acc = function
    | [] -> List.rev acc
    | x :: rest ->
      if pred x then aux (x :: acc) rest
      else aux acc rest
  in
  aux [] lst

(* 尾递归的 flatten *)
let flatten lst =
  let rec aux acc = function
    | [] -> acc
    | inner :: rest -> aux (List.rev_append inner acc) rest
  in
  List.rev (aux [] lst)

(* 数组基本操作 *)
let arr = [|1; 2; 3; 4; 5|]
let _ = arr.(0)          (* 读取索引 0，=> 1 *)
let () = arr.(0) <- 10   (* 修改索引 0 *)
let len = Array.length arr

(* 列表转数组 *)
let arr = Array.of_list [1; 2; 3; 4; 5]

(* 数组转列表 *)
let lst = Array.to_list arr

(* analysis.ml — 使用列表进行数据分析 *)

type student = {
  name : string;
  score : float;
  grade : string;
}

let students = [
  { name = "Alice"; score = 92.5; grade = "A" };
  { name = "Bob"; score = 78.0; grade = "B" };
  { name = "Charlie"; score = 85.5; grade = "A" };
  { name = "Diana"; score = 95.0; grade = "A" };
  { name = "Eve"; score = 62.0; grade = "C" };
]

(* 计算平均分 *)
let avg =
  let (sum, count) = List.fold_left
    (fun (s, c) stu -> (s +. stu.score, c + 1))
    (0.0, 0) students
  in
  sum /. float_of_int count

(* 找出最高分学生 *)
let top_student =
  List.fold_left
    (fun acc stu -> if stu.score > acc.score then stu else acc)
    (List.hd students)
    (List.tl students)

(* 按分数排序 *)
let ranked = List.sort
  (fun a b -> compare b.score a.score)
  students

(* 筛选及格学生（>=60）并格式化 *)
let passing_report =
  students
  |> List.filter (fun s -> s.score >= 60.0)
  |> List.sort (fun a b -> compare b.score a.score)
  |> List.mapi (fun i s ->
    Printf.sprintf "%d. %s: %.1f (%s)" (i + 1) s.name s.score s.grade
  )

let () =
  Printf.printf "平均分: %.2f\n" avg;
  Printf.printf "最高分: %s (%.1f)\n" top_student.name top_student.score;
  print_endline "\n排名:";
  List.iter print_endline passing_report