Gruppo 10

------------------------------------------ GRUPPO 10 -------------------------------

type 'a ntree = Tr of 'a * 'a ntree list

type multi_expr =
  MultiInt of int
| MultiVar of string
| MultiDiff of multi_expr * multi_expr
| MultiDiv of multi_expr * multi_expr
| MultiSum of multi_expr list
| MultiMult of multi_expr list

(* subexpr: multi_expr -> multi_expr -> bool *)
let rec subexpr expr1 expr2 =
    match expr1 with
    | MultiInt p -> MultiInt p = expr2
    | MultiVar p -> MultiVar p = expr2
    | MultiDiff (p,q) -> MultiDiff (p,q) = expr2 || subexpr p expr2 || subexpr q expr2
    | MultiDiv (p,q) -> MultiDiv (p,q) = expr2 || subexpr p expr2 || subexpr q expr2
    | MultiSum lst -> MultiSum lst = expr2 || List.for_all (fun a -> subexpr a expr2) lst
    | MultiMult lst -> MultiMult lst = expr2 || List.for_all (fun a -> subexpr a expr2) lst

(*subst: multi_expr -> string -> multi_expr -> multi_expr*)
let rec subst expr var sub =
    match expr with
    | MultiInt p -> MultiInt p
    | MultiVar p -> if p = var then sub else MultiVar p
    | MultiDiff (p,q) -> MultiDiff(subst p var sub, subst q var sub)
    | MultiDiv (p,q) -> MultiDiv(subst p var sub, subst q var sub)
    | MultiSum lst -> MultiSum (List.map (fun x -> subst x var sub) lst)
    | MultiMult lst -> MultiMult (List.map (fun x -> subst x var sub) lst)

(* postorder: ’a ntree -> ’a list *)
let rec postorder = function
  | Tr(a,[]) -> [a]
  | Tr(a,lst)->  (List.flatten (List.map postorder lst)) @[a]

(* inorder: ’a ntree -> ’a list  *)
let rec inorder = function
  | Tr(a,[]) -> [a]
  | Tr(a,lst) -> a::(List.flatten (List.map inorder lst))

(* foglie_in_lista: ’a list -> ’a ntree -> bool *)
let rec foglie_in_lista lst = function
    | Tr(a,[]) -> List.mem a lst
    | Tr(a,nlst) -> List.for_all (fun a -> a) (List.map (foglie_in_lista lst) nlst)

(* sumof: int list -> int
   Data una lista di interi restituisce la somma di tutti i suoi elementi *)
let rec sumof = function
    | [] -> 0
    | a::rest -> a + (sumof rest)

(* num_di_foglie: ’a ntree -> int *)
let rec num_di_foglie = function
    | Tr(a,[]) -> 1
    | Tr(a,nlst) -> sumof (List.map num_di_foglie nlst)

(* listaGuida: ’a list -> ’a ntree -> ’a *)
let rec listaGuida lst ntree =
    match (lst, ntree) with
    | ([],Tr(a,_)) -> a
    | (a::rest,Tr(_,nlst)) ->  try (listaGuida rest (List.nth nlst a)) with _ -> failwith "Sottoalbero non trovato"

(* maxCosto : int*int list -> int*int
   Prende in input una lista di coppie di interi e restituisce la coppia con il secondo
   valore più alto*)
let rec maxCosto = function
    | [a] -> a
    | (fgl,cst)::rest -> let (fgl2,cst2) = maxCosto rest
                         in if(cst > cst2) then (fgl,cst)
                                           else (fgl2,cst2)

(* foglia_costo: ’int ntree ->(int * int)
   aux : int -> int ntree -> (int*int)
   Prendendo in input un intero e un albero, restituisce una coppia di interi
   i quali rappresentano il valore della foglia con il massimo valore dell'accumulatore intero
   che si ottiene sommando i valori degli alberi del cammino*)
let foglia_costo ntree =
    let rec aux costo = function
      | Tr(a,[]) -> (a,costo)
      | Tr(a,lst) -> maxCosto (List.map (aux (costo+a)) lst)
    in aux 0 ntree


(* tutte_foglie_costi: int ntree -> (int * int) list
   aux : int -> int ntree -> int*int list
   Prendendo in input un intero e un albero, restituisce una lista di coppie di interi
   i quali rappresentano il valore della foglia e il valore dell'accumulatore intero
   che si ottiene sommando i valori degli alberi del cammino*)
let tutte_foglie_costi ntree =
    let rec aux costo = function
      | Tr(a,[]) -> [(a,costo)]
      | Tr(a,lst) -> List.flatten (List.map (aux (costo+a)) lst)
    in aux 0 ntree

(* ramo_da_lista: ’a ntree -> ’a list -> ’a -> ’a list
   path_list : a list -> a -> a ntree list
   Prende in input una lista,un etichetta e una lista di alberi e restituisce il cammino
   per il quale ogni elemento della lista sia stato visitato esattamete solo una volta,
   altrimenti restituisce un errore*)
let rec ramo_da_lista alb lst etic =
    match alb with
    | Tr(a,[]) -> if a = etic && lst = [a] then [a] else failwith "Not Found"
    | Tr(a,nlst) -> if List.mem a lst then a::(path_list (List.filter ((<>)a) lst) etic nlst)
                                      else failwith "Not Found"
    and path_list lst etic = function
       | [] -> failwith "Not Found"
       | alb::rest -> try ramo_da_lista alb lst etic
                      with _ -> path_list lst etic rest

(* isPrimo : int -> bool
   Controlla se il numero è primo
   aux : int -> int -> bool
   Prende in input un numero ed il suo successivo, e decide se il secondo numero
   è primo o meno*)
let isPrimo num =
    let rec aux cont num =
        if cont = 1 || cont = 0 then true
        else num mod cont <> 0 && aux (cont-1) num
    in aux (num-1) num

(* ramo_di_primi: int ntree -> int
   path_plist : int ntree list -> int
   Prende in input una lista di alberi e riporta se esiste la foglia per il quale
   tutti gli elementi del cammino siano numeri primi essa compresa*)
let rec ramo_di_primi = function
    | Tr(a,[]) -> if isPrimo a then a else failwith "Non Trovato"
    | Tr(a,nlst) -> if isPrimo a then path_plist nlst
                                 else failwith "Non Trovato"
    and path_plist = function
       | [] -> failwith "Not Found"
       | alb::rest -> try ramo_di_primi alb
                      with _ -> path_plist rest


(* path_non_pred: (’a -> bool) -> ’a ntree -> ’a list
   path_pred : (a->bool)-> a' ntree list
   Prende in input un predicato ed una lista di alberi, restituisce un cammino
   dove tutti i nodi non soddisfano il predicato*)
let rec path_non_pred p = function
        | Tr(a,[]) -> if not (p a) then [a] else failwith "Not Found"
        | Tr(a,nlst) -> if not (p a) then a::(path_pred p nlst)
                                                           else failwith "Not Found"
and path_pred p = function
      | [] -> failwith "Not Found"
          | a::rest -> try path_non_pred p a with _ -> path_pred p rest

(* listAnd : bool list -> bool
   Prende in input una lista di booleani e calcola il loro
   valore mettendoli tutti in and*)
let rec listAnd = function
        | [] -> true
        | a::rest -> a && listAnd rest

(* same_structure: ’a ntree -> ’b ntree -> bool *)
let rec same_structure alb1 alb2 =
        match (alb1, alb2) with
        | (Tr(_,[]),Tr(_,[])) -> true
        | (Tr(_,lst1),Tr(_,lst2)) -> listAnd(try List.map2 same_structure lst1 lst2
                                             with _ -> failwith "Diversa Struttura")
        | _ -> false

type col = Rosso | Giallo | Verde | Blu
type 'a col_assoc = (col * 'a list) list

(* colore: ’a -> ’a col_assoc -> col *)
let rec colore num = function
         (Rosso,lst)::rest -> if( List.mem num lst) then Rosso else colore num rest
   | (Giallo,lst)::rest-> if( List.mem num lst) then Giallo else colore num rest
   | (Verde,lst)::rest -> if( List.mem num lst) then Verde else colore num rest
   | (Blu,lst)::rest   -> if( List.mem num lst) then Blu else colore num rest

(* ramo_colorato: ’a -> ’a col_assoc -> ’a ntree -> ’a list
   path_clist : col -> a -> a col_assoc -> a ntree list -> a list
   Presi in input un colore, un etichetta, una lista associativa di colori e una lista di alberi
   restituisce il cammino il quale ha nodi adiacenti con colori diversi e come foglia il lo stesso
   valore dell'etichetta, se non esiste tale cammino solleverà un eccezione*)
let rec ramo_colorato x assoc = function
        | Tr(a,[]) -> if a = x then [a] else failwith "Non trovato"
        | Tr(a,lst) -> a::(path_clist (colore a assoc) x assoc lst)
and path_clist color x assoc = function
        | [] -> failwith "Non Trovato"
        | (Tr(a,lst))::rest -> if color <> colore a assoc
                                                        then try ramo_colorato x assoc (Tr(a,lst))
                                                                 with _ -> path_clist color x assoc rest
                                                        else
                                                                 path_clist color x assoc rest

let alb = (Tr(1, [Tr(2,[Tr(5,[]);
                        Tr(6,[])]);
                  Tr(3,[Tr(7,[]);
                        Tr(8,[])]);
                  Tr(4,[Tr(9,[]);
                        Tr(10,[])])]))

let lst = [(Rosso,[1;2;4;7;10]); (Giallo,[3;8;11]);
(Verde,[0;5;6;13]); (Blu,[9;12;14;15])]