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
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
|
(***********************************************************************)
(* *)
(* Objective Caml *)
(* *)
(* Xavier Leroy, projet Cristal, INRIA Rocquencourt *)
(* *)
(* Copyright 1996 Institut National de Recherche en Informatique et *)
(* en Automatique. All rights reserved. This file is distributed *)
(* under the terms of the GNU Library General Public License. *)
(* *)
(***********************************************************************)
(* $Id$ *)
(* List operations *)
let rec length_aux len = function
[] -> len
| a::l -> length_aux (len + 1) l
let length l = length_aux 0 l
let hd = function
[] -> failwith "hd"
| a::l -> a
let tl = function
[] -> failwith "tl"
| a::l -> l
let rec nth l n =
match l with
[] -> failwith "nth"
| a::l ->
if n = 0 then a else
if n > 0 then nth l (n-1) else
invalid_arg "List.nth"
let append = (@)
let rec rev_append l1 l2 =
match l1 with
[] -> l2
| a :: l -> rev_append l (a :: l2)
let rev l = rev_append l []
let rec flatten = function
[] -> []
| l::r -> l @ flatten r
let concat = flatten
let rec map f = function
[] -> []
| a::l -> let r = f a in r :: map f l
let rev_map f l =
let rec rmap_f accu = function
| [] -> accu
| a::l -> rmap_f (f a :: accu) l
in
rmap_f [] l
;;
let rec iter f = function
[] -> ()
| a::l -> f a; iter f l
let rec fold_left f accu l =
match l with
[] -> accu
| a::l -> fold_left f (f accu a) l
let rec fold_right f l accu =
match l with
[] -> accu
| a::l -> f a (fold_right f l accu)
let rec map2 f l1 l2 =
match (l1, l2) with
([], []) -> []
| (a1::l1, a2::l2) -> let r = f a1 a2 in r :: map2 f l1 l2
| (_, _) -> invalid_arg "List.map2"
let rev_map2 f l1 l2 =
let rec rmap2_f accu l1 l2 =
match (l1, l2) with
| ([], []) -> accu
| (a1::l1, a2::l2) -> rmap2_f (f a1 a2 :: accu) l1 l2
| (_, _) -> invalid_arg "List.rev_map2"
in
rmap2_f [] l1 l2
;;
let rec iter2 f l1 l2 =
match (l1, l2) with
([], []) -> ()
| (a1::l1, a2::l2) -> f a1 a2; iter2 f l1 l2
| (_, _) -> invalid_arg "List.iter2"
let rec fold_left2 f accu l1 l2 =
match (l1, l2) with
([], []) -> accu
| (a1::l1, a2::l2) -> fold_left2 f (f accu a1 a2) l1 l2
| (_, _) -> invalid_arg "List.fold_left2"
let rec fold_right2 f l1 l2 accu =
match (l1, l2) with
([], []) -> accu
| (a1::l1, a2::l2) -> f a1 a2 (fold_right2 f l1 l2 accu)
| (_, _) -> invalid_arg "List.fold_right2"
let rec for_all p = function
[] -> true
| a::l -> p a && for_all p l
let rec exists p = function
[] -> false
| a::l -> p a || exists p l
let rec for_all2 p l1 l2 =
match (l1, l2) with
([], []) -> true
| (a1::l1, a2::l2) -> p a1 a2 && for_all2 p l1 l2
| (_, _) -> invalid_arg "List.for_all2"
let rec exists2 p l1 l2 =
match (l1, l2) with
([], []) -> false
| (a1::l1, a2::l2) -> p a1 a2 || exists2 p l1 l2
| (_, _) -> invalid_arg "List.exists2"
let rec mem x = function
[] -> false
| a::l -> a = x || mem x l
let rec memq x = function
[] -> false
| a::l -> a == x || memq x l
let rec assoc x = function
[] -> raise Not_found
| (a,b)::l -> if a = x then b else assoc x l
let rec assq x = function
[] -> raise Not_found
| (a,b)::l -> if a == x then b else assq x l
let rec mem_assoc x = function
| [] -> false
| (a, b) :: l -> a = x || mem_assoc x l
let rec mem_assq x = function
| [] -> false
| (a, b) :: l -> a == x || mem_assq x l
let rec remove_assoc x = function
| [] -> []
| (a, b as pair) :: l -> if a = x then l else pair :: remove_assoc x l
let rec remove_assq x = function
| [] -> []
| (a, b as pair) :: l -> if a == x then l else pair :: remove_assq x l
let rec find p = function
| [] -> raise Not_found
| x :: l -> if p x then x else find p l
let find_all p =
let rec find accu = function
| [] -> rev accu
| x :: l -> if p x then find (x :: accu) l else find accu l in
find []
let filter = find_all
let rec partition p l =
let rec part yes no = function
| [] -> (rev yes, rev no)
| x :: l -> if p x then part (x :: yes) no l else part yes (x :: no) l in
part [] [] l
let rec split = function
[] -> ([], [])
| (x,y)::l ->
let (rx, ry) = split l in (x::rx, y::ry)
let rec combine l1 l2 =
match (l1, l2) with
([], []) -> []
| (a1::l1, a2::l2) -> (a1, a2) :: combine l1 l2
| (_, _) -> invalid_arg "List.combine"
|
