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:

# select ["aaa";"bbb";"ccc"] [1;2;0;1];; 
  : string list = ["bbb"; "ccc"; "aaa"; "bbb"]
*)

 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:

  • the first element is the head of the list
  • the folding is performed on the tail of the list.
This function is adequate for most common cases. Use the module 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:
# List.transpose [[1;2;3]; [4;5;6]; [7;8;9]];;
  : int list list = [[1; 4; 7]; [2; 5; 8]; [3; 6; 9]]
*)

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