Higher-Order Functions & the List Module

fold_left is tail-recursive; fold_right is not (but preserves order naturally).

14.1 Implementing the big three yourself

fold_left is tail-recursive; fold_right is not (but preserves order naturally).

let rec map f = function [] -> [] | x :: xs -> f x :: map f xs

let rec filter p = function
  | [] -> []
  | x :: xs -> if p x then x :: filter p xs else filter p xs

let rec fold_left f acc = function
  | [] -> acc
  | x :: xs -> fold_left f (f acc x) xs

let rec fold_right f lst acc = match lst with
  | [] -> acc
  | x :: xs -> f x (fold_right f xs acc)

14.2 The List module tour

List.length [1;2;3]                   (* 3 *)
List.rev [1;2;3]                      (* [3;2;1] *)
List.nth [10;20;30] 1                 (* 20 *)
List.nth_opt [] 0                     (* None *)
List.append [1] [2]                   (* [1;2] *)
List.concat [[1];[2;3]]               (* [1;2;3] *)
List.flatten                          (* same as concat *)
List.map (fun x -> x * 2) [1;2]       (* [2;4] *)
List.mapi (fun i x -> i + x) [10;20]  (* [10;21] *)
List.filter_map (fun x -> if x > 0 then Some (x*10) else None) [-1;2]  (* [20] *)
List.concat_map (fun x -> [x;x]) [1;2] (* [1;1;2;2] *)
List.iter print_int [1;2;3]
List.iteri (fun i x -> Printf.printf "%d:%d " i x) [5;6]
List.fold_left (+) 0 [1;2;3]          (* 6 *)
List.fold_right (fun x acc -> x :: acc) [1;2] []
List.fold_left_map
List.for_all (fun x -> x > 0) [1;2]   (* true *)
List.exists (fun x -> x > 1) [1;2]    (* true *)
List.mem 2 [1;2;3]                    (* true *)
List.find (fun x -> x > 1) [1;2;3]    (* 2, raises Not_found *)
List.find_opt
List.find_map
List.partition (fun x -> x mod 2 = 0) [1;2;3;4]   (* ([2;4],[1;3]) *)
List.split [(1,'a');(2,'b')]          (* ([1;2],['a';'b']) *)
List.combine [1;2] ['a';'b']        
…

14.3 Typical functional pipelines

type employee = { name : string; dept : string; salary : float }

let total_salary_by dept employees =
  employees
  |> List.filter (fun e -> e.dept = dept)
  |> List.map (fun e -> e.salary)
  |> List.fold_left ( +. ) 0.

let names_sorted_by_salary es =
  es
  |> List.sort (fun a b -> Float.compare b.salary a.salary)
  |> List.map (fun e -> e.name)

14.4 Association lists

Fine for small data; use Map / Hashtbl for large data.

let phonebook = [("alice", "555-1234"); ("bob", "555-9876")]
List.assoc_opt "alice" phonebook