1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
include ListLabels
type 'a t = 'a list
let map ~f t = rev (rev_map ~f t)
let is_empty = function
| [] -> true
| _ -> false
let rec filter_map l ~f =
match l with
| [] -> []
| x :: l ->
match f x with
| None -> filter_map l ~f
| Some x -> x :: filter_map l ~f
let rec filter_opt l =
match l with
| [] -> []
| x :: l ->
match x with
| None -> filter_opt l
| Some x -> x :: filter_opt l
let filteri l ~f =
let rec filteri l i =
match l with
| [] -> []
| x :: l ->
let i' = succ i in
if f i x
then x :: filteri l i'
else filteri l i'
in
filteri l 0
let concat_map l ~f = concat (map l ~f)
let rev_partition_map =
let rec loop l accl accr ~f =
match l with
| [] -> (accl, accr)
| x :: l ->
match (f x : (_, _) Either.t) with
| Left y -> loop l (y :: accl) accr ~f
| Right y -> loop l accl (y :: accr) ~f
in
fun l ~f -> loop l [] [] ~f
let partition_map l ~f =
let l, r = rev_partition_map l ~f in
(rev l, rev r)
type ('a, 'b) skip_or_either =
| Skip
| Left of 'a
| Right of 'b
let rev_filter_partition_map =
let rec loop l accl accr ~f =
match l with
| [] -> (accl, accr)
| x :: l ->
match f x with
| Skip -> loop l accl accr ~f
| Left y -> loop l (y :: accl) accr ~f
| Right y -> loop l accl (y :: accr) ~f
in
fun l ~f -> loop l [] [] ~f
let filter_partition_map l ~f =
let l, r = rev_filter_partition_map l ~f in
(rev l, rev r)
let rec find_map l ~f =
match l with
| [] -> None
| x :: l ->
match f x with
| None -> find_map l ~f
| Some _ as res -> res
let rec find l ~f =
match l with
| [] -> None
| x :: l -> if f x then Some x else find l ~f
let find_exn l ~f =
match find l ~f with
| Some x -> x
| None -> invalid_arg "List.find_exn"
let rec last = function
| [] -> None
| [x] -> Some x
| _::xs -> last xs
let sort t ~compare =
sort t ~cmp:(fun a b -> Ordering.to_int (compare a b))
let stable_sort t ~compare =
stable_sort t ~cmp:(fun a b -> Ordering.to_int (compare a b))
let rec compare a b ~compare:f : Ordering.t =
match a, b with
| [], [] -> Eq
| [], _ :: _ -> Lt
| _ :: _, [] -> Gt
| x :: a, y :: b ->
match (f x y : Ordering.t) with
| Eq -> compare a b ~compare:f
| ne -> ne
let rec assoc t x =
match t with
| [] -> None
| (k, v) :: t -> if x = k then Some v else assoc t x
let singleton x = [x]
let rec nth t i =
match t, i with
| [], _ -> None
| x :: _, 0 -> Some x
| _ :: xs, i -> nth xs (i - 1)
let physically_equal = Pervasives.(==)