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
|
(***********************************************************************)
(* *)
(* Caml Special Light *)
(* *)
(* Xavier Leroy, projet Cristal, INRIA Rocquencourt *)
(* *)
(* Copyright 1995 Institut National de Recherche en Informatique et *)
(* Automatique. Distributed only by permission. *)
(* *)
(***********************************************************************)
(* $Id$ *)
(* List operations *)
let rec length = function
[] -> 0
| a::l -> 1 + length 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 nth l (n-1)
let rec rev_append accu = function
[] -> accu
| a::l -> rev_append (a :: accu) l
let rev l = rev_append [] l
let rec flatten = function
[] -> []
| l::r -> l @ flatten r
let rec map f = function
[] -> []
| a::l -> let r = f a in r :: map 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 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 or 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
([], []) -> true
| (a1::l1, a2::l2) -> p a1 a2 or exists2 p l1 l2
| (_, _) -> invalid_arg "List.exists2"
let rec mem x = function
[] -> false
| a::l -> a = x or mem x l
let rec memq x = function
[] -> false
| a::l -> a == x or 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 mem_assoc x = function
[] -> false
| (a,b)::l -> a = x or mem_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 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"
|
