gruppo6.ml

let rec find p = function
    | [] -> failwith("Proprietà non soddisfatta")
    | x::xs -> if p x then x else find p xs

let takewhile p lst =
    let rec aux taken = function
        | [] -> taken
        | x::xs -> if p x then aux (x::taken) xs else taken
    in List.rev(aux [] lst)

let rec dropwhile p = function
    | [] -> []
    | x::xs -> if p x then dropwhile p xs else x::xs

let partition p lst =
    let rec aux (yes,no) = function
        | [] -> (yes,no)
        | x::xs -> aux (if p x then (x::yes,no) else (yes,x::no)) xs
    in aux ([],[]) (List.rev lst)

let pairwith y = List.map (fun x -> (y,x))

let rec matrice n = function
    | [] -> false
    | xs::ys -> (List.for_all (fun x -> x < n) xs) || matrice n ys

find (fun x -> x*x < 30) [6; 7; 9; 10; 5; 8; 2]

let setdiff xs ys = List.filter ( fun x -> not (List.mem x ys) ) xs

let subset xs = List.for_all (fun x -> List.mem x xs)

let duplica = List.map (fun x -> (x,x))

let intesta x = List.map (fun (y,xs) -> (y,x::xs))

let rec aux n x y lista =
    if n == 3 then lista else aux (n+1) y x (x::lista)
in aux 0 0 1 []

(*
 * 1) x for x in [0,1]
 * 2) ((x::y for y in [0,1]) for x in [0,1])
 *
 * values=(A,B)
 * res=[(A,A), (A,B), (B,A), (B,B)]
 *)

(* O(n) tail-recursive *)
let rev list =
    let rec aux res = function
        | [] -> res
        | x::xs -> aux (x::res) xs
    in aux [] list

(* O(2a) tail-recursive *)
let append a b =
    let rec aux res = function
        | [] -> res
        | x::xs -> aux (x::res) xs
    in aux b (rev a)

let product repeat values =
    let rec step lista n =
        let rec aux res = function
            | [] -> res
            | x::xs -> aux (res @ (List.map (fun y -> x::y) lista)) xs
        in if n < repeat then step (aux [] values) (n+1) else lista
    in step [[]] 0

let interleave x lst =
    let rec aux res xs =
        (* @ : 'a list -> 'a list -> 'a list
         * funzione di supporto che concatena due liste invertendo la prima
         * [1; 2] @ [3; 4] => [2; 1] @ [3; 4] *)
        let rec (@) xs ys = match xs with
            | [] -> ys
            | x::xs -> xs @ (x::ys)
        in function
            | [] -> (xs@[x])::res
            | y::ys -> aux ((xs@x::y::ys)::res) (y::xs) ys
    in aux [] [] lst


(* Calcola le permutazioni di una lista non vuota. La lista con un solo
 * elemento è considerata un caso base. *)
let rec permut lst =
    (* Data una lista xs @ y::ys calcola le permutazioni della lista composta da
     * tutti gli elementi tranne y con (permut (xs@ys)) e aggiunge y in testa ad
     * ogni permutazione. Poi si mette y in xs e si prende come nuovo y il primo
     * elemento di ys. Si continua finché ys non è vuota. *)
    let rec aux res xs = function
        | [] -> res
        | y::ys ->
            aux ((List.map (fun zs -> y::zs) (permut (xs@ys)))@res) (y::xs) ys
    in match lst with
        | [] -> (failwith "permutation of an empty list")
        | [x] -> [[x]]
        | _ -> aux [] [] lst


let in_riga (dim, labirinto) i v =
    List.exists (fun ((r,_),c) -> r = i && c = v) labirinto

let trova_colonna (dim, labirinto) i v =
    snd (fst (List.find (fun ((r,_),c) -> r = i && c = v) labirinto))

let rec in_tutte (dim, lab) v =
    if dim = 0 then true else
        let i = dim-1 in in_riga (dim, lab) i v && in_tutte (i, lab) v

let find x lst =
    let rec aux xs = function
        | [] -> failwith "il valore 'x' non è presente nella lista"
        | y::ys -> if y = x then ((List.rev xs),ys) else aux (y::xs) ys
    in aux [] lst

let spezza x lst = find x (snd (find x lst))


let prendi p lst =
    let rec aux xs = function
        | [] -> failwith "nessun elemento soddisfa la condizione"
        | y::ys -> if p y then (y, xs@ys) else aux (y::xs) ys
    in aux [] lst