struct
open Sugar;;
(** Generalization*) |
(** Head and tail generalisation *) |
(** Similar to the standard List.hd , but retrieve the list of first elements (by default n=1 as in List.hd ).
Thus, the result is a list. *) |
let rec head ?(n:int=1) (l:'a list) : ('a list) =
if n<=0 then [] else let n = (n-1) in
match l with
| [] -> []
| x::r -> x::(head ~n r)
;;
(** Similar to the standard List.tl , but the tail is extracted from the given index
(by default i=1 as in List.tl ) *) |
let rec tail ?(i:int=1) (l:'a list) =
if (i=0) then l else tail ~i:(i-1) (List.tl l)
;;
(** Set operations*) |
(** Substract the second argument from the first *) |
let substract = fun u d -> let p=(fun y -> not (List.mem y d)) in (List.filter p u)
;;
(** subset a b check if a is a subset of b , i.e. if all elements of a belong to b. *) |
let subset a b = List.for_all (fun x->(List.mem x b)) a
;;
(** eqset a b check if a and b represent the same set of values. *) |
let eqset a b = (subset a b) && (subset b a)
;;
(** Intersection of list: AvB=A\(A\B) . *) |
let intersection a b = substract a (substract a b)
;;
(** Shortcut for List.iter with arguments in the opposite order: before the list, then the action to perfom. *) |
let foreach l f = List.iter f l
;;
(** Returns a list with no duplicates. For large lists we suggest to use Hashset.uniq instead. *) |
let rec uniq = function
| [] -> []
| x::r -> if (List.mem x r) then (uniq r) else x::(uniq r)
;;
(** Indexes*) |
(** range a b returns the list [a; (a+1); .. ; (b-1); b] containing all the values between the given limits (included) . *) |
let range (a:int) (b:int) =
let rec range a b acc = if a>b then acc else (range a (b-1) (b::acc)) in
range a b []
;;
(** Alias for range. *) |
let interval = range
;;
(** The list of indexes of a list. The first index is 0 as usually. *) |
let indexes l = range 0 ((List.length l)-1);;
(** Consider a list as a function from indexes to its content. The function is the identity outside the indexes of the list. *) |
let asFunction l = fun i -> try (List.nth l i) with _ -> i;;
(** Selecting by indexes *) |
(** Considering a list as a record and select some fields (indexes). Example:
*) |
let select (l:'a list) (fieldlist:int list) =
let a = Array.of_list l in
let rec loop a = function
| [] -> []
| f::fl -> (Array.get a f)::(loop a fl)
in loop a fieldlist
;;
(** Removing by indexes *) |
(** Remove the element with the given index. *) |
let rmindex l i =
let rec rmindex acc = function
| (0,x::xs) -> List.append (List.rev acc) xs
| (i,x::xs) -> rmindex (x::acc) (i-1,xs)
| (_,[]) -> failwith "rmindex: index out of bounds" in
rmindex [] (i,l)
;;
(** Searching for indexes *) |
(** Heuristic searching for the index of an element satisfying a property. *) |
let indexSuchThat (pred:'a->bool) (l:'a list) : (int option) =
let rec indexOf pred l i = (match l with
| [] -> None
| y::r when (pred y) -> Some i
| y::r -> indexOf pred r (i+1) )
in indexOf pred l 0
;;
(** Heuristic searching the first index of an element in a list *) |
let indexOf (x:'a) (l:'a list) : (int option) = indexSuchThat ((=)x) l
;;
(** Alias for indexOf . *) |
let firstIndexOf = indexOf
;;
(** Heuristic searching the last index of an element in a list *) |
let lastIndexOf x l =
let n = List.length l in
match indexOf x (List.rev l) with
| None -> None
| Some i -> Some (n-1-i)
;;
(** Permutations*) |
(** Returns a permutation of the list. *) |
let rec shuffle l = if l = [] then [] else
let i = Random.int (List.length l) in
let l' = (rmindex l i) in
(List.nth l i)::(shuffle l')
;;
(** List permutation. The first argument is the function f that represents the permutation
(we suppose that this function will be a bijection w.r.t. the set of indexes of the given list).
In other words permute f l is the list [(f 0) ; (f 1) ; (f 2) ; ... ] . *) |
let permute f l = List.map (fun i -> List.nth l (f i)) (indexes l)
;;
(** Returns a random permutation function for the given list. *) |
let shuffler l = l => (indexes || shuffle || asFunction )
;;
(** Returns a random list of indexes for the given list. *) |
let shuffleIndexes l = l => (indexes || shuffle)
;;
(** Folding*) |
(** The folding of lists is simply a List.fold_left specialization:
Big when
maximum generality is requested. *) |
let big f = function
| [] -> failwith "big"
| [x] -> x
| x::r -> List.fold_left f x r
;;
(** Common foldings *) |
(** The polymorphic maximum of a list. *) |
let max (l:'a list) : 'a = big max l;;
(** The polymorphic minimum of a list. *) |
let min (l:'a list) : 'a = big min l;;
(** List of lists*) |
(** Transpose the matrix (list of lists). Example:
*) |
let transpose l =
let get_nths i l = List.map (fun x->List.nth x i) l in
match l with
| [] -> []
| x::l' ->
begin
let n = (List.length x) in match List.for_all (fun y -> n = List.length y) l' with
| false -> raise (Invalid_argument "transpose")
| true -> List.map (fun j->get_nths j l) (range 0 (n-1))
end
;;
end