logica

Laboratorul 8

-----------------------------------teo-----------------------------------

(* Exercitiul 1 *)

open Printf

type 'a bintree = L of 'a | T of 'a bintree * 'a * 'a bintree

let postorder =

let rec postord lst= function

| L t-> t :: lst

| T (l, v, r) ->

let urm = postord (postord lst l) r

in v :: urm (*printf "%d: %d\n" urm v; urm+1*)

in postord []

;;

let t1 = T((T (L 1,2,L 3)),5,L 4);;

postorder t1;;

(* Exercitiul 2*)

printf "\n Exercitiul 2\n"

type 'a tree = L of 'a | T of 'a tree list

let inorder =

let rec inord cnt = function

| L v -> printf "%d \n" v; cnt

| T [] -> cnt

| T (h :: t) -> let urm = inord cnt h

in List.fold_left inord urm t

in inord 1

;;

let t2 = T[L 1; T [ L 2 ; L 3 ]; T [ L 4 ; T [ L 5 ; L 1] ; L 10 ]; L 5];;

inorder t2;;

printf "\nExercitiul 3: \n";;

(* Exercitiul 3*)

let rec spatii acc n = if n = 1 then acc else spatii (acc ^ " ") (n-1);;

let tip_spatii n = spatii "" n;;

type 'a bintree = Nil | T of 'a bintree * 'a * 'a bintree

let preorder =

let rec preord cnt = function

| Nil -> ()

| T (l, v, r) -> printf "%s" (tip_spatii cnt); printf "%d\n" v; preord (cnt+1) l; preord (cnt +1) r

in preord 1

;;

(*let preorder =

let rec preord cnt acc = function

| Nil -> cnt

| T (l, v, r) -> printf "%s %d\n" acc v;

let acc2 = acc ^ " "

in

let urm = preord (cnt+1) acc l in preord urm acc2 r

in preord 1 " "

;;*)

preorder (T ( Nil, 5, T ( T ( Nil, 4, Nil), 9, Nil)));;

let t3 = T (T(Nil, 2, Nil), 7,

T(T(Nil, 5, Nil), 6, T(Nil, 11, Nil)));;

printf "\n";;

preorder t3;;

--------------------------------------------------------------------------------

(* ----2---- *)

type 'a tree = T of 'a * 'a tree list

;;

let t = T(23,[T(12,[T(15,[])]); T(19,[]);

T(30,[T(29, [T(28,[])]);T(23,[])])])

(*

let inorder =


| Nil -> cnt

| T (l, v, r) ->

let urm = inord cnt l in

printf "%d: %d\n" urm v; inord (urm+1) r

in inord 1

*)

let inorder =


| T ( r, [] ) -> Printf.printf "%d: %d\n" cnt r ; cnt +1

| T ( r , h::t )->

let urm = inord cnt h in

Printf.printf "%d: %d\n" urm r ; List.fold_left ( fun e x -> inord ( e + 1 ) x ) urm t

in inord 1

;;

inorder t ;;

(*---3---*)

type 'a btree = Nil | T of 'a btree * 'a * 'a btree

;;

let t2 = T (T(Nil, 2, Nil), 7,

T(T(Nil, 5, Nil), 6, T(Nil, 11, Nil)));;

let rec put_space number = if ( number <= 1 ) then Printf.printf " " else (

Printf.printf " "; put_space ( number -1 ))

;;

let preorder =

let rec preord lvl = function

| Nil -> lvl

| T (l, v, r) -> put_space ( 2 * lvl ) ; Printf.printf "%d\n" v;

let urm = preord (lvl+1) l in preord (lvl +1) r

(* sau direct: preord (preord (cnt + 1) l) r *)

in preord 1 (* pornim de la 1 *)

;;

preorder t2 ;;

laboratorul 7 teo-----------------------------------------------------------------

type expr= B of bool

|V of string

|Neg of expr

|And of expr * expr

|Or of expr * expr

exception Foundvar of string

let findvar f =

let rec findv = function

|B _ -> ()

|V p -> raise (Foundvar p)

|Neg f -> findv f

|And (f1,f2) | Or (f1,f2) -> findv f1; findv f2

in try

findv f; raise Not_found

with Foundvar v -> v

;;

let simplify_var var b=

let v = findvar f

in ITE (v, make_ite (simplify_var v true f), make_ite (simplify_var v false f))

;;

make_ite (And (V "p", Or(V "q", B true)));;

make_ite (And (B true, Or(V "q",B false)));;

-----------------------------------------------------------------------------------------

Laboratorul 7

(* ---5---*)

type iteform = C of bool | P of string | N of string | ITE of string * iteform * iteform

let print_l lista = List.iter ( fun ( h1 , h2 ) -> if h2 = true then Printf.printf "*%s" h1

else Printf.printf "*~%s" h1 ) lista ;;

let do_solve expr =

let rec _make_prod lista ex = match ex with

| C true -> print_l lista ; print_newline()

| ITE ( p , f_true , f_false ) -> _make_prod ( ( p , true ) :: lista ) f_true;

_make_prod ( ( p ,false ) :: lista ) f_false

| P p -> print_l ( ( p , true ) :: lista ) ; print_newline()

| N p -> print_l ( ( p ,false ) :: lista ) ; print_newline()

| C false -> ()

in _make_prod [] expr

;;

do_solve ( ITE ( "a" , ITE ( "b" , P "c" , P "c") , ITE ("d" , C true , N "c")) ) ;;

(*mi se pare ex 2 lab 7*)

type bexp = B of bool

| V of string

| Neg of bexp

| And of bexp * bexp

| Or of bexp * bexp

type iteform = C of bool | P of string | N of string | ITE of string * iteform * iteform

let rec findvar = function (* parcurge formula pana la prima variabila *)

| B _ -> raise Not_found (* caz de baza: nu avem propoziție *)

| V p -> p (* am găsit, returnăm *)

| Neg f -> findvar f (* caută în unica subformulă *)

| And (f1, f2) | Or (f1, f2) ->

try findvar f1 (* caută în prima subformulă *)

type expr= B of bool (* declararea tipului unei expresii binare clasice. astea

de obicei ni le da proful.

ce vezi inainte de "of" ii o

denumire aleasa de noi. putea foarte bine sa fie si

zoo of bool | foofoo of string | bunica of Neg, etc

ce ii dupa of ii tipul. daca vrei un exemplu mai simplu:

type chestie (numele tipului declarat de mine) =

|A of int | B of bool | C of float.

asta inseamna ca pot sa scriu 5 asa: 5(evident) sau (A 5)

sau false pot sa scriu: false sau (B false) etc.

e pur si simplu o declarare a unui tip cum vrem noi.

putem avea si type chestie = A of int| B of bool| C of chestie

putem defini un tip cu ajutorul unui tip deja definit de noi*)

|V of string

|Neg of expr

|And of expr * expr (* '*' inseamna pereche. aici un exemplu ar fi And( B true, B false) *)

|Or of expr * expr

exception Foundvar of string (* asa se declara o exceptie in ml. este putin mai greu

sa intelegi exceptiile, astea de obicei se fac la

OOP (Object Oriented Programming). Daca esti curios

de exceptii cauta pe net java exceptions. Au

cam acelasi mecanism de functionare ca si astea.

Dar deocamdata iti ajunge sa intelegi ca asta ii o

exceptie. Practic ne declaram un tip care atunci cand

programul nostru indeplineste o anumita conditie,

se "arunca" exceptia (raise, dupa cum vezi mai jos),

si se opreste executia programului. Imagineazati-l

ca si un break din C :) *)

(* Potrivirea de tipare:

sa zicem ca eu am o functie care vreau sa se comporte diferit in functie de ce parametrii ii dau.

De exemplu cum am folosit tiparul meu: type chestie = A of int | B of bool | C of float

sa zicem ca eu vreau sa scriu o functie care atunci cand ii dau ca si parametru un int,

sa faca ceva, cand ii dau ca si parametru un bool altceva, etc.

asta s-ar scrie asa:

let functie = function

|A i -> printf "integer"

|B b -> printf "boolean"

|C f -> printf "float"

i,b,f sunt denumiri alese de noi. trebuie sa le atribuim o valoare ca sa o putem folosi

dupa aceea. in marea majoritate a cazurilor o sa avem nevoie sa o folosim.

functia de mai sus e ca si cum as zice:

let functie x = match x with

|A i -> [...]

sau fie functie x = if x e intreg atunci printf "intreg" else if x e boolean atunci printf "boolean",etc

potrivirea de tiapre ii super important sa o intelegi, ca ii cam baza programarii

functionale. aici compilatorul este foarte sensibil la tipuri. *)

(* findvar e p functie data de prof. ce face ea? ii dai ca si argument o formula/expresie

binara si o variabila. Functia iti cauta prin toata expresia si

cauta acea variabila. cand o gaseste,arunca expresia Foundvar, si

ne returneaza variabila gasita, iar programul se opreste.

incearca sa faci findvar pe un exemplu sa vezi ce iti da. asa intelegi

cel mai bine ce fac functiile *)

let findvar f =

let rec findv = function (* incepem potrivirea de tipare *)

|B _ -> () (* decursul este recursiv. nu e asa de important sa intelegi cum face si mai degraba ce face :)) *)

|V p -> raise (Foundvar p) (* uite vezi? aici cand am gasit tipul V p (p fiind string daca te uiti in definirea tipului, inseamna ca am dat de o variabila. variabila intr-o expresie booleana inseamna de exemplu "a" din And (V "a", B false). Nu are nici o valoarea booleana atribuita *)

|Neg f -> findv f

|And (f1,f2) | Or (f1,f2) -> findv f1; findv f2

in try

findv f; raise Not_found (* ceva chestie ce tre pusa in lucrul cu exceptii. nu e neaparat sa intelegi asta, poti trai si fara ea *)

with Foundvar v -> v

;;

let simplify_var var b= (* functie data de prof. ce face? iti ia o expresie booleana si o simplifica inlocuind o variabila data de tine cu o valoare data de tine. adica efectiv dintr-un carnat imens de And-uri,

Or-uri si de dumnezo mai e pe acolo, el aplicand regulile care le stie (De Morgan, whatever, vezi in curs, nu-i important sa ti minte pentru asta) reduce formula initiala la una mai simpla. daca avem de exemplu o formula f = And (B true, Or( B false, V "a")) si apelam: ( simplify_var "a" (B true) f ) o sa il inlocuiasca pe a din f cu B true. daca avem formule mai complicate acestea se simplifica (true || false = true, etc) *)


|Neg e -> (match simplify e with (* magical implementation a 'la prof. nu ma intreba exact ce se intampla ca nici eu nu prea stiu *)

|B b -> B (not b)

|r -> Neg r)

|And (e1,e2) -> (match (simplify e1, simplify e2) with (* aici avem din nou potriviri de tipare. e ca si cum as zice: daca e1 are tipul asta si e2 are tipul asta, fa ce scrie dupa -> (daca primul termen al And-ului e un Boolean false, si al doilea nu conteaza ( asta isneamna _, nu ne intereseaza) atunci returneaza B false. cand pui intre tipuri | inseamna ca ce este dupa sageata se aplica la tot ce este inaintea ei *)

|(B false, _) | (_, B false) -> B false

|(B true, e) | (e, B true) -> e

|(r1,r2) -> And (r1,r2) )

|Or (e1,e2) -> ( match (simplify e1, simplify e2) with

|(B false, e) | (e, B false) -> e

|(B true, _) | (_, B true) -> B true

|(r1, r2) -> Or (r1, r2) )

|V p when p = var -> B b (* conditie la tipar, putem face si if then else, dar e mai bine asa *)

|e -> e

in simplify (* asta e in principal scrisa de prof. nu e neaparat sa intelegi la fiecare linie de cod ce se intampla logic, dar sintactic ar fi ok de inteles. *)

;;

type dec_tree = C of bool (* declararea unui tip arbore binar de decizie. ca sa intelegi ce este ala, citeste in curs *)

|P of string

|N of string

|ITE of string * dec_tree * dec_tree (* ITE vine de la If Then Else. cum scrie si in laborator, avem tipul ITE (a,b,c). asta se traduce ca si:

if a then b else c. deci daca a este ceva adevarat atunci returnam b. altfel c. *)

(* functia make_ite transforma o expresie booleana intr-un arbore binar de decizie.

practic tot ce trebuie sa faci este sa potrivesti tiparul lui expr cu tiparul lui dec_tree.

astfel totul devine mai usor: *)

let rec make_ite = function

|B b -> C b (* daca expresia noastra este un simplu true sau false atunci returnam un C true sau C false (C este tipul corespondent din dec_tree pentru B din expr. uita-te atent *)

|V p -> P p (* daca este o variabila, returnam acea variabila- dar ca si tip corespondent!! *)

|Neg (V p) -> N p (* daca este pur si simplu o negatie de variabila, din nou facem corespondenta tipului *)

|f -> (* aici devine mai greu. dac anu avem doar o variabila sau un boolean si o fosmula din aia lunga cu Or si And si etc?*)

let v = findvar f (*prima data cautam o variabila in formula noastra. oricare. citeste arborii de decizie din curs ca sa intelegi mai bine.

si o denumim v. ca putem, si ca sa nu facem findvar de fiecare data cand avem nevoie sa cautam o variabila, ci ne folosim direct de v let...in e mai ciudat dar cu timpul te obinuiesti cu el, nici eu in ziua de azi nu stiu exact cum se face ca de fiecare data il folosesc diferit

:D *)

in ITE (v, make_ite (simplify_var v true f), make_ite (simplify_var v false f))

(* aici creem direct arborele de decizie binara. cum s-ar traduce asta dupa ceea ce am scris mai sus cu if then else?

cautam o variabila si prima oara o inlocuim cu true si facem simplificarea astfel pe formula. dupa aceea o inlocuim cu false si facem simplificare in sensul asta ( cu simplify var v -boolean- f. adica? variabila v din f o inlocuim cu valoarea booleana din -boolean- si facem simplificarea *)

;;

make_ite (And (V "p", Or(V "q", B true)));; (* apelam functia pe cateva exemple sa vedem ca merge bine. poti sa cauti niste exemple mai complicate *)

make_ite (And (B true, Or(V "q",B false)));;

logica

Documents