list.cd 1.81 KB
Newer Older
Julien Lopez's avatar
Julien Lopez committed
1 2
let length (l : ['a*]) : Int =
  let aux (l : ['a*])(res : Int) : Int = match l with
3 4 5 6
    | [] -> res
    | [_; rest] -> aux rest (res + 1) in
  aux l 0

Julien Lopez's avatar
Julien Lopez committed
7
let hd (['a+] -> 'a) [el _*] -> el
8

Julien Lopez's avatar
Julien Lopez committed
9
let tl (['a+] -> ['a*])
10
  | [el] -> [el]
11 12
  | [_; rest] -> rest

Julien Lopez's avatar
Julien Lopez committed
13 14
let nth (l : ['a*])(n : Int) : 'a =
  let aux (l : ['a*])(n : Int) : 'a = match l with
15 16 17 18
    | [] -> raise "Failure \"List.nth\""
    | [el; rest] -> if n >> 0 then aux rest (n - 1) else el in
  if n << 0 then raise "Invalid_argument \"List.nth\"" else aux l n

Julien Lopez's avatar
Julien Lopez committed
19 20
let rev (l : ['a*]) : ['a*] =
  let aux (l : ['a*])(res : ['a*]) : ['a*] = match l with
21 22 23
    | [] -> res
    | [el; rest] -> aux rest ([el] @ res) in
  aux l []
24

Julien Lopez's avatar
Julien Lopez committed
25 26 27 28 29 30 31 32 33 34 35 36
let append (l1 : ['a*])(l2 : ['a*]) : ['a*] = l1 @ l2

let rev_append (l1 : ['a*])(l2 : ['a*]) : ['a*] = (rev l1) @ l2

let concat (l : [['a*]*]) : ['a*] =
  let aux (l : [['a*]*])(res : ['a*]) : ['a*] = match l with
    | [] -> res
    | [el; rest] -> aux rest (res @ el) in
  aux l []

let flatten = concat

37 38
(* Iterators *)

Julien Lopez's avatar
Julien Lopez committed
39
let iter (f : ('a -> []))(l : ['a*]) : [] = match l with
40
  | [] -> []
41 42
  | [el; rest] -> f el; iter f rest

Julien Lopez's avatar
Julien Lopez committed
43 44
let iteri (f : (Int -> 'a -> []))(l : ['a*]) : [] =
  let aux (f : (Int -> 'a -> []))(l : ['a*])(pos : Int) : [] = match l with
45 46 47 48
    | [] -> []
    | [el; rest] -> f pos el; aux f rest (pos + 1)
  in
  aux f l 0
Julien Lopez's avatar
Julien Lopez committed
49 50 51

let mapf (f : 'a -> 'b)(l : ['a*]) : ['b*] =
  let aux (f : 'a -> 'b)(l : ['a*])(acc : ['b*]) : ['b*] = match l with
52
    | [] -> acc
53
    | [el; rest] -> aux f rest (acc @ [(f el)]) in
54
  aux f l []
Julien Lopez's avatar
Julien Lopez committed
55

Julien Lopez's avatar
Julien Lopez committed
56 57 58 59 60 61 62 63 64
let mapi (f : Int -> 'a -> 'b)(l : ['a*]) : ['b*] =
  let aux (f : Int -> 'a -> 'b)(l : ['a*])(pos : Int)(acc : ['b*]) : ['b*] =
  match l with
    | [] -> acc
    | [el; rest] -> aux f rest (pos + 1) (acc @ [(f pos el)]) in
  aux f l 0 []

(* let rev_map (f : 'a -> 'b)(l : ['a*]) : ['b*] = rev (mapf f l) *)

65
(* List scanning *)