annotate ppc/util.ml @ 0:bfdcc3820b32

Basis
author Mike Spivey <mike@cs.ox.ac.uk>
date Thu, 05 Oct 2017 08:04:15 +0100
parents
children
rev   line source
0
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
1 (* ppc/util.ml *)
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
2 (* Copyright (c) 2017 J. M. Spivey *)
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
3
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
4 (* |copy n x = [x; x; ...; x]| with |n| copies of |x| *)
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
5 let rec copy n x = if n <= 0 then [] else x :: copy (n-1) x
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
6
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
7 (* |take n [x1; x2; ...] = [x1; x2; ...; xn]| *)
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
8 let rec take n =
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
9 function
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
10 [] -> []
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
11 | x::xs -> if n = 0 then [] else x :: take (n-1) xs
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
12
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
13 (* |drop n [x1; x2; ...] = [x_{n+1}; x_{n+2}; ...]| *)
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
14 let rec drop n =
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
15 function
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
16 [] -> []
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
17 | x::xs -> if n = 0 then x::xs else drop (n-1) xs
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
18
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
19 (* |can f x| is true if |f x| doesn't raise |Not_found| *)
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
20 let can f x = try f x; true with Not_found -> false
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
21
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
22 (* |make_hash n [(x1, y1); ...]| creates a hash table of size |n|
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
23 that initially contains the pairs |(x1, y1)|, ... *)
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
24 let make_hash n ps =
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
25 let table = Hashtbl.create n in
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
26 List.iter (function (x, y) -> Hashtbl.add table x y) ps;
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
27 table
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
28
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
29 (* |accum f [x1; x2; ...; xn] a| computes f xn (... (f x2 (f x1 a)) ...) *)
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
30 let rec accum f ys a =
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
31 match ys with
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
32 [] -> a
Mike Spivey <mike@cs.ox.ac.uk>
parents:
diff changeset
33 | x::xs -> accum f xs (f x a)