(*
Wojciech Muła, $Id: mylist.ml,v 1.5 2006-06-03 20:56:12 wojtek Exp $
*)
(* converts string to list of chars
explode "Ocaml" = ['O'; 'c'; 'a'; 'm'; 'l']
*)
let explode s =
let rec worker = function
| (l, -1) -> l
| (l, i) -> worker (s.[i]::l, (i-1))
in
worker ([], String.length s - 1)
(* convert char to string *)
let string_of_char c =
String.make 1 c
(* convert list of chars to string
implode ['O'; 'c'; 'a'; 'm'; 'l'] = "Ocaml"
*)
let rec implode l =
List.fold_left (fun s c -> s ^ (string_of_char c)) "" l
(* returns last element of list
last [1; 2; 3; 4; 5] = 5
*)
let rec last = function
| [] -> failwith "last"
| [x] -> x
| _::xs -> last xs
(* returns all but one elements of list
allbutone [1; 2; 3; 4; 5] = [1; 2; 3; 4]
*)
let rec allbutone = function
| [] -> raise (Failure "allbutone: empty string")
| [x] -> []
| x::xs -> x::allbutone xs
(* returns first n element of list l
take [1; 2; 3; 4; 5] 2 = [1; 2]
*)
let take l n =
let rec worker l' l i =
if i = 0 then
l'
else
match l with
[] -> l'
| x::xs -> worker (l' @ [x]) xs (i-1)
in
worker [] l n
let allbut l n =
let n' = (List.length l - n) in
if n' < 0 then [] else take l n'
(* returns all but first n-elements of list l
drop [1; 2; 3; 4; 5] 2 = [3; 4; 5]
(take l n) @ (drop l n) = l
*)
let rec drop l i =
match l with
[] -> []
| _::xs as l -> if i > 0 then
drop xs (i-1)
else
l
(* returns sublist of list l
cut [1; 2; 3; 4; 5] 1 4 = [2; 3; 4]
*)
let cut l f t =
assert (f >= 0);
assert (f < t);
take (drop l f) (t-f)
(* splits list l into two list at n-th element
splitat [1; 2; 3; 4; 5] 0 = ([], [1; 2; 3; 4; 5])
splitat [1; 2; 3; 4; 5] 1 = ([1], [2; 3; 4; 5])
splitat [1; 2; 3; 4; 5] 2 = ([1; 2], [3; 4; 5])
splitat [1; 2; 3; 4; 5] 3 = ([1; 2; 3], [4; 5])
splitat [1; 2; 3; 4; 5] 4 = ([1; 2; 3; 4], [5])
splitat [1; 2; 3; 4; 5] 5 = ([1; 2; 3; 4; 5], [])
*)
let splitat l n =
let rec worker before after i =
if i = 0 then
(before, after)
else
match after with
[] -> (before, after)
| x::after' -> worker (before @ [x]) after' (i-1)
in
worker [] l n
(* returns copy of list l with changed i-th element
change [1; 2; 3; 4; 5] 0 100 = [100; 2; 3; 4; 5]
change [1; 2; 3; 4; 5] 3 100 = [1; 2; 3; 100; 5]
*)
let rec change l i n =
match l with
[] -> []
| x::xs -> if i > 0 then
x::(change xs (i-1) n)
else
n::xs
(* inset element n into list l at position i
insert [1; 2; 3; 4; 5] 0 100 = [100; 1; 2; 3; 4; 5]
insert [1; 2; 3; 4; 5] 1 100 = [1; 100; 2; 3; 4; 5]
insert [1; 2; 3; 4; 5] 2 100 = [1; 2; 100; 3; 4; 5]
insert [1; 2; 3; 4; 5] 3 100 = [1; 2; 3; 100; 4; 5]
insert [1; 2; 3; 4; 5] 4 100 = [1; 2; 3; 4; 100; 5]
insert [1; 2; 3; 4; 5] 5 100 = [1; 2; 3; 4; 5; 100]
*)
let insertat l i n =
let rec worker before after i =
if i = 0 then
before @ [n] @ after
else
match after with
[] -> before @ after @ [n]
| x::after' -> worker (before @ [x]) after' (i-1)
in
worker [] l i
(* returns index of first occurence of y,
or -1 if y is not member of list
index [11; 44; 33; 44; 55] 44 = 1
*)
let index l y =
let rec worker l i =
match l with
[] -> -1
| x::xs -> if x=y then i else worker xs (i+1)
in
worker l 0
(* returns index of last occurence of y,
or -1 if y is not member of list
rindex [11; 44; 33; 44; 55] 44 = 3
*)
let rindex l y =
let rec worker l i found =
match l with
[] -> found
| x::xs -> if x=y then
worker xs (i+1) i
else
worker xs (i+1) found
in
worker l 0 (-1)
(* returns list of integeres [lo..hi)
range -5 10 = [-5; -4; -3; -2; -1; 0; 1; 2; 3; 4; 5; 6; 7; 8; 9]
*)
let range lo hi =
assert (lo < hi);
let rec worker l i =
if i >= lo then
worker (i::l) (i-1)
else
l
in
worker [] (hi-1)
(* List.map f (range lo hi)
irange 0 10 (fun x -> x*x) = [0; 1; 4; 9; 16; 25; 36; 49; 64; 81]
*)
let tabulate lo hi f =
assert (lo < hi);
let rec worker l i =
if i >= lo then
worker ((f i)::l) (i-1)
else
l
in
worker [] (hi-1)
let imap fn l =
let rec aux l i =
match l with
[] -> []
| x::xs -> (fn i x)::aux xs (i+1)
in
aux l 0
let ifilter fn l =
let rec aux l i =
match l with
[] -> []
| x::xs -> if fn i x then
x::aux xs (i+1)
else
aux xs (i+1)
in
aux l 0
(*
let take' l n = ifilter (fun i _ -> i < n) l
let drop' l n = ifilter (fun i _ -> i >= n) l
let cut' l k n = ifilter (fun i _ -> i >= k && i < n) l
*)
let count pred l =
List.fold_left (fun i x -> (if pred x then i+1 else i)) 0 l