Source file list.ml
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
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 -> Exn.code_error "List.find_exn" []
let rec last = function
| [] -> None
| [x] -> Some x
| _::xs -> last xs
let destruct_last =
let rec loop acc = function
| [] -> None
| [x] -> Some (rev acc, x)
| x :: xs -> loop (x :: acc) xs
in
fun xs -> loop [] 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 sort_uniq t ~compare =
Dune_caml.List.sort_uniq (fun a b -> Ordering.to_int (compare a b)) t
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.(==)
let init =
let rec loop acc i n f =
if i = n then
rev acc
else
loop (f i :: acc) (i + 1) n f
in
fun n ~f -> loop [] 0 n f
let hd_opt = function
| [] -> None
| x :: _ -> Some x
let rec equal eq xs ys =
match xs, ys with
| [], [] -> true
| x :: xs, y :: ys -> eq x y && equal eq xs ys
| _, _ -> false
let hash f xs = Dune_caml.Hashtbl.hash (map ~f xs)