Esercitazione261114.ml

3;;
type 'a bstree = Empty | Node of 'a * 'a bstree * 'a bstree;;

(*5) visitC : 'a bstree -> 'a list*)
(*La funzione visitC produce una visita di tuti i nodi che non sono foglie.*)
let rec visitC tree = match tree with
Empty -> []
  |Node (a, Empty, Empty) -> []
  |Node (a, t1, t2) -> [a]@(visitC t1)@(visitC t2);;

let a = Node ("A", Node ("B", Node ("C", Empty, Empty), Empty), Empty);;

visitC a;;


(*1) isLesser  'a bstree  -> 'a bstree -> bool*)
(*La funzione isLesser restituisce true se tutte le chiavi dei nodi di t1 sono piu’ piccole di quelle in t2 alla stessa posizione.*)
let rec isLesser t1 t2 = match t1, t2 with
(Empty, Empty) -> true
  | (Node (a, l1, r1), Node (b, l2, r2)) -> (a <= b) && (isLesser l1 l2) && (isLesser r1 r2)
  |_ -> true;;

(*3)getLevel : 'a -> 'a bstree ->int*)
(*La funzione getLevel restituisce il livello del nodo con chiave data.*)
let rec getLevelR k t acc = match t with
   Empty -> 0
  | Node (key, l, r) -> (if (key = k) then acc else let leftLevel = (getLevelR k l (acc + 1)) in
                            if (leftLevel = 0) then (getLevelR k r (acc+1))
                            else leftLevel);;
let getLevel k t = getLevelR k t 0;;
getLevel "B" a;;

(*6) mapTree : ('a -> 'b) -> 'a bstree -> 'b bstree*)
(*La funzione  mapTree f t  applica la funzione f ad ogni key dell’albero *)
let rec mapTree f t = match t with
Empty -> Empty
  | Node (a, l, r) -> Node ((f a), (mapTree f l), (mapTree f r));;

(*7) Fold su alberi
Definire la seguente  funzione :
    foldTree : ('a -> 'b -> 'b -> 'b) -> 'a bstree -> 'b -> 'b
La funzione foldTree f t z scorre su tutti i nodi dell’albero in e applica la funzione f alla chiave corrente, al risultato del sottoalbero sinistro e del destro (si comporta come la fold_right ma agisce su alberi e non su liste)
*)

let rec foldTree f t z = match t with
Empty -> z
  |Node (a, l, r) -> f a (foldTree f l z) (foldTree f r z);;

(*Implemento la visita in profondità usando la foldTree*)
let prof t = foldTree (fun a b c -> b@[a]@c) t [];;

prof a;;

(*Implemento la mapTree che ho definito prima con la foldTree*)
let mapTree f t = foldTree (fun a b c -> Node ((f a), b, c)) t Empty;;

mapTree (fun x -> x^"Ciao") a;;

type boolean = One
             | Zero
             | LAnd of  boolean list
             | LXOr of  boolean list
         ;;

(*8) Definire una funzione eval che assegni ad un’ espressione di tipo boolean  un valore di tipo bool, interpretando:
One e Zero con i booleani true e false,
LAnd list con true  se tutte le espressioni della lista  sono vere
LXOr list con true se esattamente  una espressione della lista e’ vera *)

let rec eval exp = match exp with
   One -> true
  |Zero -> false
  |LAnd l -> List.fold_right (fun a b -> eval a && b) l true
  |LXOr l -> if (List.fold_right (fun a b -> if (eval a) then (b+1) else b ) l 0) = 1 then true else false;;

let e = LAnd [One;Zero;LXOr[One]];;
eval e;;


type exp = Pippo
             | Add of int * exp
             | Alternate of exp * exp
         ;;

(*Definire una funzione eval che assegni ad un’ espressione di tipo exp  un valore di tipo int list, interpretando:
Pippo  con la lista [0,1]
Add n e1   con la concatenazione di n con il valore ottenuto dall’espressione e1
Alternate e1 e2 con la concatenazione del valore di e1 con il valore di e2 prendendo alternativamente un elemento da e1 e uno da e2 finche’ possibile e poi troncando.*)

let rec eval exp = match exp with
   Pippo -> [0;1]
  |Add (v, e) -> v :: (eval e)
  |Alternate (e1, e2) -> let val1 = eval (e1) in
                         let val2 = eval e2 in
                         let rec merge l1 l2 = match (l1, l2) with
             (l, []) | ([], l) -> []
            |((hd1::tl1), (hd2::tl2)) -> hd1::hd2::(merge tl1 tl2) in
            merge val1 val2;;


let e1 = Pippo;;                   (*[0;1]*)
let e2 = Add (5, e1);;             (*[5;0;1]*)
let e3 = Alternate (e2, e2);;      (*[5;5;0;0;1;1]*)
let e4 = Alternate (e1, e2);;      (*[0;5;1;0]*)

eval e1;;
eval e2;;
eval e3;;
eval e4;;