Control.Print.printDepth := 100;

datatype expression =  Constant of int |
        Variable of string |
        Operator of string * expression |
        Pair of expression list |
        List of expression list

datatype pattern = ConstantP of int
    | VariableP of string
    | OperatorP of string * pattern
    | PairP of pattern list
    | ListP of pattern list
    | UnorderedListP of pattern list
    | Wildcard

(*cross*)
fun cross(tp) =
    case tp of
        (nil, xs) => nil
        |(xs, nil) => nil
        |(h::t, xs) => (List.map (fn x => (h, x) ) xs) @ cross(t, xs)

(*match*)
fun match(ex: expression, pt: pattern) =
    case pt of
        Wildcard => SOME nil
        | VariableP s => (case ex of
                     Constant x => SOME[(s, Constant x)]
                    | Variable y => SOME[(s, Variable y)]
                    | Operator z => SOME[(s, Operator z)]
                    | Pair w => SOME[(s, Pair w)]
                    | List l => SOME[(s, List l)] )

        | ConstantP x => (case ex of
                    Constant y => if(x = y) then SOME nil else NONE
                    | _ => NONE)

        | ListP ps => ((
            case ex of
                List xs => if(List.length(xs) <> List.length(ps)) then NONE else case (xs, ps) of
                    (h::nil, g::nil) => match(h, g)
                    | (h::t, g::r) => case match(h, g) of
                        SOME v => SOME (v @ Option.valOf(match(List t, ListP r)))
                        | NONE => NONE
                    )handle Option => NONE)

        | PairP([a1, a2]) => (case ex of
            Pair([b1,b2]) => (if(match(b2, a2) = NONE orelse match(b1, a1) = NONE) then NONE else SOME (Option.valOf(match(b1, a1)) @ Option.valOf(match(b2, a2)))))

        |OperatorP(a, x) => (case ex of
            Operator(b, y) => if(a = b) then ( case(x,y) of (x,y) => match(y, x)) else NONE)
(*eval*)
exception InvalidVariable of string
exception InvalidExpression  of expression

fun dobi(xs, var) =
    case xs of
        (a, b)::[] => if(a = var) then b else raise InvalidVariable a
        |(a, b)::t => if(a = var) then b else dobi(t, var)

fun eval xs exp =
    case exp of
        Operator("+", a) => let
            fun calc a =   case a of
                Constant a => a
                | Variable a => dobi(xs, a)
                | Pair [a1, a2] => calc(a1) + calc(a2)
                | Pair a => raise InvalidExpression (Pair a)
                | Operator(a, b) => eval xs (Operator(a,b))
                | List b => case b of
                    nil => 0
                    | b =>List.foldl (fn(x,y) => y + calc(x)) (calc(hd b)) (tl b)
        in
            calc a
        end
        | Operator("-", a) => let
            fun calc a =   case a of
                Constant a => a
                | Variable a => dobi(xs, a)
                | Pair [a1, a2] => calc(a1) - calc(a2)
                | Pair a => raise InvalidExpression (Pair a)
                | Operator(a, b) => eval xs (Operator(a,b))
                | List b => raise InvalidExpression (List b)
        in
            calc a
        end
         | Operator("*", a) => let
            fun calc a =   case a of
                Constant a => a
                | Variable a => dobi(xs, a)
                | Pair [a1, a2] => calc(a1) * calc(a2)
                | Pair a => raise InvalidExpression (Pair a)
                | Operator(a, b) => eval xs (Operator(a,b))
                | List b => case b of
                    nil => 1
                    | b => List.foldl (fn(x,y) => y * calc(x)) (calc(hd b)) (tl b)
        in
            calc a
        end
        | Operator("/", a) => let
            fun calc a =   case a of
                Constant a => a
                | Variable a => dobi(xs, a)
                | Pair [a1, a2] => if(calc(a2) = 0) then raise InvalidExpression (Pair [a1, a2]) else calc(a1) div calc(a2)
                | Pair a => raise InvalidExpression (Pair a)
                | Operator(a, b) => eval xs (Operator(a,b))
                | List b => raise InvalidExpression (List b)
        in
            calc a
        end
        | Operator("%", a) => let
            fun calc a =   case a of
                Constant a => a
                | Variable a => dobi(xs, a)
                | Pair [a1, a2] => if(calc(a2) = 0) then raise InvalidExpression (Pair [a1, a2]) else calc(a1) mod calc(a2)
                | Pair a => raise InvalidExpression (Pair a)
                | Operator(a, b) => eval xs (Operator(a,b))
                | List b => raise InvalidExpression (List b)
        in
            calc a
        end
        | Operator(a, b) => raise InvalidExpression(Operator(a, b))

(* derivative *)
fun derivative exp s = case exp of
    Variable a => if(a = s) then Constant 1 else Constant 0
    | Constant c => Constant 0
    | Operator("+", Pair [a, b]) => Operator("+", Pair [derivative a s , derivative b s])
    | Operator("-", Pair [a, b]) => Operator("-", Pair [derivative a s , derivative b s])
    | Operator("/", Pair([a, b])) => Operator("/", Pair([ Operator("-", Pair([Operator("*", Pair([derivative a s, b])), Operator("*", Pair([a, derivative b s]))])), Operator("*", Pair([b, b]))]))
    | Operator("*", Pair [a, b]) =>
    case ([a,b]) of
        ([Constant a, b]) => Operator("*", Pair([Constant a, derivative b s]))
        | ([a, Constant b]) => Operator("*", Pair([derivative a s, Constant b]))
        | ([a, b]) => Operator("+", Pair([Operator("*", Pair([derivative a s, b])), Operator("*", Pair([a, derivative b s]))]))

(*removeEmpty *)
    fun obdelajkrat l = case (List.exists (fn x => if(x = Constant 0) then true else false) ((hd l)::(List.filter (fn x => if(x = Constant 1) then false else true) (tl l)))) of
                true => Constant 0
                | false => List ((hd l)::(List.filter (fn x => if(x = Constant 1) then false else true) (tl l)))

    fun removeEmpty exp = case exp of
        Operator("+", b) => (case b of
            List l => (case (List.length(List.filter (fn x => if(x = Constant 0) then false else true) (List.map (fn x => removeEmpty(x)) l) )) of
                0 => Constant 0
                | 1 => hd(List.filter (fn x => if(x = Constant 0) then false else true) (List.map (fn x => removeEmpty(x)) l))
                | _ => Operator("+", List (List.filter (fn x => if(x = Constant 0) then false else true) (List.map (fn x => removeEmpty(x)) l))))

            | Pair p => (case (List.length(List.filter (fn x => if(x = Constant 0) then false else true) (List.map (fn x => removeEmpty(x)) p) )) of
                0 => Constant 0
                | 1 => hd(List.filter (fn x => if(x = Constant 0) then false else true) (List.map (fn x => removeEmpty(x)) p))
                | _ => Operator("+", List (List.filter (fn x => if(x = Constant 0) then false else true) (List.map (fn x => removeEmpty(x)) p))) )
            | Constant c => Constant c
            | Variable v => Variable v)

        | Operator("-", b) => (case b of
            List l => (case (List.length(List.filter (fn x => if(x = Constant 0) then false else true) (List.map (fn x => removeEmpty(x)) l))) of
                0 => Constant 0
                | 1 => hd(List.filter (fn x => if(x = Constant 0) then false else true) (List.map (fn x => removeEmpty(x)) l))
                | _ => Operator("-", List (List.filter (fn x => if(x = Constant 0) then false else true) (List.map (fn x => removeEmpty(x)) l))))

            | Pair p => (case (List.length(List.filter (fn x => if(x = Constant 0) then false else true) (List.map (fn x => removeEmpty(x)) p))) of
                0 => Constant 0
                | 1 => hd(List.filter (fn x => if(x = Constant 0) then false else true) (List.map (fn x => removeEmpty(x)) p))
                | _ => Operator("-", List (List.filter (fn x => if(x = Constant 0) then false else true) (List.map (fn x => removeEmpty(x)) p))))
            | Constant c => Constant c
            | Variable v => Variable v)

        | Operator("/", b) => (case b of
            List l => (case (List.length((List.filter (fn x => if(x = Constant 1) then false else true) (List.map (fn x => removeEmpty(x)) l)))) of
                 0 => hd l
                | 1 => hd(List.filter (fn x => if(x = Constant 1) then false else true) (List.map (fn x => removeEmpty(x)) l))
                | _ => Operator("/", List((List.filter (fn x => if(x = Constant 1) then false else true) (List.map (fn x => removeEmpty(x)) l)))))

            | Pair p => (case (List.length((List.filter (fn x => if(x = Constant 1) then false else true) (List.map (fn x => removeEmpty(x)) p)))) of
                 0 => hd p
                | 1 => hd(List.filter (fn x => if(x = Constant 1) then false else true) (List.map (fn x => removeEmpty(x)) p))
                | _ => Operator("/", List((List.filter (fn x => if(x = Constant 1) then false else true) (List.map (fn x => removeEmpty(x)) p)))))
            | Constant c => Constant c
            | Variable v => Variable v)

        | Operator("*", b) => (case b of
            List l => (case (List.exists (fn x => if(x = Constant 0) then true else false) ((List.filter (fn x => if(x = Constant 1) then false else true) l))) of
                true => Constant 0
                | false => case (List.length((List.filter (fn x => if(x = Constant 1) then false else true) (List.map (fn x => removeEmpty(x)) l)))) of
                    0 => hd l
                    | 1 => hd (List.filter (fn x => if(x = Constant 1) then false else true) (List.map (fn x => removeEmpty(x)) l))
                    | 2 => Operator("*", List((List.filter (fn x => if(x = Constant 1) then false else true) (List.map (fn x => removeEmpty(x)) l)))))

            | Pair p => (case (List.exists (fn x => if(x = Constant 0) then true else false) ((List.filter (fn x => if(x = Constant 1) then false else true) p))) of
                true => Constant 0
                | false => case (List.length((List.filter (fn x => if(x = Constant 1) then false else true) (List.map (fn x => removeEmpty(x)) p)))) of
                    0 => hd p
                    | 1 => hd (List.filter (fn x => if(x = Constant 1) then false else true) (List.map (fn x => removeEmpty(x)) p))
                    | 2 => Operator("*", List((List.filter (fn x => if(x = Constant 1) then false else true) (List.map (fn x => removeEmpty(x)) p)))))
            | Constant c => Constant c
            | Variable v => Variable v)

        | Constant c => Constant c
        | Variable v => Variable v



























fun combinations a: 'a list list = a
fun flatten exp = List [exp]
fun joinSimilar exp = List [exp]
fun divide(exp, exp1) = List [exp, exp1]



(*;;;; "type tests"  ;;;;

val test_cross_type: 'a list * 'b list -> ('a * 'b) list = cross

val test_match_type: expression * pattern -> (string * expression) list option = match

val test_eval_type: (string * int) list -> expression -> int = eval

val test_derivative_type: expression -> string -> expression = derivative

val test_removeEmpty_type: expression -> expression = removeEmpty

val test_combinations_type: 'a list list -> 'a list list = combinations

val test_flatten_type: expression -> expression = flatten

val test_joinSimilar_type: expression -> expression = joinSimilar

val test_divide_type: expression * expression -> expression = divide *)