// autor: Pawel Schmidt

// Drzewa wyrazen, obliczanie wartosci, postac prefiksowa oraz postfiksowa
// Symboliczne obliczanie pochodnej funkcji z jedna zmienna

open System

// Reprezentacja operatora binarnego
type BinOpType = 
    | Plus  // Dodawanie
    | Sub   // Odejmowanie
    | Mult  // Mnozenie
    | Div   // Dzielenie
    | Pow   // Potegowanie
    // funkcja zwracajaca napis bedacy reprezentacja operatora
    override this.ToString() : string = 
        match this with
        | Plus  -> "+" 
        | Sub   -> "+"
        | Mult  -> "*"
        | Div   -> "/"
        | Pow   -> "^"

// reprezentacja drzewa wyrazenia (pozniej: funkcji jednej zmiennej X)
type Expression = 
    // | X             // reprezentacja zmiennej jako wyrazenia
    // // powyzsza linia celowo jest zakomentowana, w dalszej czesci dodamy ja do definicji drzewa wyrazenia
    | Num of double // reprezentacja liczb
    | BinNode of Expression * BinOpType * Expression   
        // dwa wyrazenia polaczone operatorem dwuargumentowym, np X + 3
    | Sin of Expression // funkcja sinus
    | Cos of Expression // funkcja cosinus
    | Log of Expression // logarytm naturalny
// definicje operatorow ulatwiajacych tworzenie wyrazen (brzydkie, ale efekt ladny)
    static member (  +  ) (left, right) = BinNode (left,        Plus, right)
    static member (  +  ) (left, right) = BinNode (Num left,    Plus, right)
    static member (  +  ) (left, right) = BinNode (left,        Plus, Num right)
    static member (  -  ) (left, right) = BinNode (left,        Sub, right)
    static member (  -  ) (left, right) = BinNode (Num left,    Sub, right)
    static member (  -  ) (left, right) = BinNode (left,        Sub, Num right)
    static member (  *  ) (left, right) = BinNode (left,        Mult, right)
    static member (  *  ) (left, right) = BinNode (Num left,    Mult, right)
    static member (  *  ) (left, right) = BinNode (left,        Mult, Num right)
    static member (  /  ) (left, right) = BinNode (left,        Div, right)
    static member (  /  ) (left, right) = BinNode (Num left,    Div, right)
    static member (  /  ) (left, right) = BinNode (left,        Div, Num right)
    static member ( *** ) (left, right) = BinNode (left,        Pow, right)
    static member ( *** ) (left, right) = BinNode (Num left,    Pow, right)
    static member ( *** ) (left, right) = BinNode (left,        Pow, Num right)
    
// Przyklady:

// drzewo wyrazenia 7 (jedna liczba)
let t1 = Num 7.

// drzewo wyrazenia 7 + 23
// mozemy zdefiniowac na dwa sposoby

// wezel z operatorem dwuargumentowym
// po lewej stronie t1, 
// operator to Plus
// po prawej stronie jest 23
let t2 = BinNode(t1, Plus, Num 23.)

// uzywajac operatorow zdefiniowanych powyzej mozemy napisac tez
let t2o = t1 + 23.

// sprawdz, ze oba wyrazenia daja takie samo drzewo
// t2 = t2o

// drzewo wyrazenia 2 + 3 * 12
// ostatnia operacja jest dodawanie, ktore po lewej stronie ma 2,
// a po prawej stronie mnozenie 3 i 12
let t3 = BinNode(Num 2., Plus, BinNode( Num 3., Mult, Num 12.))

// zdefiniowane operatory +, -, *, /, *** 
// nie radza sobie jesli po obu stronach znajduja sie liczby
// jesli jedna ze stron jest wyrazeniem (na przyklad Num 12),
// zadziala poprawnie
let t3o = 2. + 3. * (Num 12.)

// drzewo wyrazenia (2 * 12) *** (-2 * 19)


let yetAnotherTree = ((Num 2.) * 12.) *** ((Num -2.) * 19.)

// zadanie 1:
// a) Zbuduj drzewo powyzszego wyrazenia wprost, uzywajac typu Expression


// b) Zbuduj drzewo wyrazenia (1+2)***(2*(2+2))


// Czytanie takich zagniezdzonych wyrazen bywa dosc trudne.
// Funkcja print moze byc przydatna do ogladania struktury drzewa - wypisuje ona drzewo na standardowe wyjscie 
// w pewien dziwny sposob (obroc glowe o 90 stopni w lewo).
// funkcja nie zwraca zadnej wartosci, a jedynie wypisuje na konsole, stad wynikowy typ unit
let print (expr:Expression) : unit = 
    let rec print2 (pref:string) (tree:Expression) : unit =
        match tree with
        // | X     -> printfn "%sX" pref
        | Num n -> printfn "%s%O" pref n
        | BinNode (left, op, right) ->
            let pref2 = "   " + pref
            print2 pref2 right
            printfn "%s%O" pref op 
            print2 pref2 left
    
    print2 "" expr

let printTest =
    print yetAnotherTree

// Czesc pierwsza: obliczanie wartosci wyrazenia (drzewa)
// Na poczatek zdefiniujemy funkcje evalBinOp, ktora jako argument przyjmie operator binarny
// oraz dwie liczby, a nastepnie zwroci wartosc 

let evalBinOp (op : BinOpType) (left : double) (right:double) : double = 
    match op with
    | Plus  -> left + right
    | Sub   -> left - right
    | Mult  -> left * right
    | Div   -> left / right
    | Pow   -> pown left right

// Teraz jestesmy gotowi do obliczaia wartosci wyrazen w postaci drzewa.

// Zadanie 2:
// Zdefiniuj funkcje eval, ktora jako argument przyjmie drzewo wyrazenia
// oraz zwroci wartosc tego wyrazenia. Uzyj funkcji evalBinOp
let rec eval (tree:Expression) : double = 
    failwith "Uzupelnij..."


// eval t3 = 38.

// eval (Num 3.) = 3.


// --------------------------------------------------------------------------------------------------------------------

// Zadanie 3: 
// zdefiniuj funkcje postfix, ktora zwroci napis
// bedacy zapisem wyrazenia w odwrotnej notacji polskiej
let rec postfix (tree:Expression) : string = 
    failwith "Uzupelnij..."

// postfix t3

// Zadanie 3.5: 
// zdefiniuj funkcje prefix, ktora zwroci napis
// bedacy zapisem wyrazenia w notacji polskiej
let rec prefix (tree:Expression) : string = 
    failwith "Uzupelnij..."

// prefix t3

// W definicji wyrazenia odkomentuj linie definiujaca uzycie zmiennej X
// Zresetuj tryb interaktywny (tak, by zapomnial wszystko co do tej pory robilismy)
// Zauwaz, ze monodevelop teraz informuje o bledach w funkcjach
// zamieniajacych na notacje prefiksowa i postfiksowa

// Zadanie 4: 
// Odkometuj linie zawierajace X w funkcji print oraz w typie Expression
// Popraw funkcje prefix i postfix 
// sprawdz, ze ponizsze drzewo poprawnie sie wypisuje

let withX = X * 12. + 7. + X

// Zadanie 5:
// Zmodyfikuj funkcje eval, tak by obliczala wartosc wyrazenia przy ustalonej wartosci zmiennej X
// Zacznij od zmiany sygnatury funkcji na
// let rec eval (xValue : double) (tree:Expression) : double = 


// Zadanie 6:
// Typ Expression mozna interpretowac jako reprezentacje funkcji zmiennej X
// Uzupelnij ponizsza funkcje, ktora rozniczkuje funkcje bedaca argumentem.
// Uwaga! dla drzewa
let x2 = X * 2.
// pochodna bedzie na przyklad
let x2d = BinNode( BinNode(Num 1., Mult, Num 2.),  Plus, BinNode(X, Mult, Num 0.))
// ktore mozna uproscic do 
let x2d' = Num 2.
// nie przejmujemy sie tym (choc jak chce to moze)
// W tym zadaniu zalezy nam jedynie na zaimplementowaniu kilku
// rekurencyjnych regul obliczania pochodnej

let rec derivative (tree:Expression) : Expression = 
    failwith "Uzupelnij..."

// Zadanie dodatkowe A:
// Zdefiniuj funkcje infix, ktora zwraca reprezentacje funkcji w postaci infiksowej 
// (czyli tak, jak zazwyczaj piszemy)
// Tym razem konieczne jest uzycie nawiasow. 
// Zadbaj, by nie uzywac zbednych nawiasow wynikajacych z kolejnosci dzialan
// Na przyklad dla drzewa
// BinNode(2., Plus, BinNode(X, Mult, 7.))
// wynikiem powinno byc
// 2+X*7, a nie 2+(X*7)
let rec infix (tree:Expression) : string = 
    failwith "Uzupelnij..."

// Zadanie dodatkowe B:
// Rozwiaz problem powstaly w poprzednim zadaniu
// zdefiniuj funkcje, ktora uprosci czesciowo drzewo
// na przyklad usunie mnozenia przez zero
// W tym zadaniu nie ma oczekiwanego rozwiazania.
// Warto sie pobawic wymyslajac wlasne reguly.

let rec simplify (tree:Expressionn) : Expression = 
    failwith "Uzupelnij..."