(*

   ITT8060 -- Advanced Programming 2016
   Department of Computer Science
   Tallinn University of Technology
   ------------------------------------

   Coursework 3: User defined types

   ------------------------------------
   Name: Taavi Gilden
   TUT Student ID: a155835
   ------------------------------------


   Answer the questions below.  You answers to questions 1--7 should be
   correct F# code written after the question. This file is an F#
   script file, it should be possible to load the whole file at
   once. If you can't then you have introduced a syntax error
   somewhere.

   This coursework will be graded. It has to be submitted to the TUT
   git system using the instructions on the course web page by October 9, 2015.
 *)

 // 1. Consider expression trees of type ExprTree declared in the lecture.
 // Extend the type with if-then-else expression of the form:
 // if b then e1 else e2
 // where b is a boolean expression and e1 and e2 are expressions.
 // An example expression could be:

 type ExpressionTree =
     | Const of int
     | Ident of string
     | Minus of ExpressionTree
     | Sum of ExpressionTree * ExpressionTree
     | Diff of ExpressionTree * ExpressionTree
     | Prod of ExpressionTree * ExpressionTree
     | Let of string * ExpressionTree * ExpressionTree
     | BiggerThan of ExpressionTree * ExpressionTree
     | LesserThan of ExpressionTree * ExpressionTree
     | BiggerEq of ExpressionTree * ExpressionTree
     | LesserEq of ExpressionTree * ExpressionTree
     | Equal of ExpressionTree * ExpressionTree
     | And of ExpressionTree * ExpressionTree
     | Or of ExpressionTree * ExpressionTree
     | Not of ExpressionTree
     | Logical of ExpressionTree * ExpressionTree * ExpressionTree
     | Match of ExpressionTree
-
+
+(*
+  FEEDBACK:
+
+    The Match alternative is wrong.
+*)
+
 // match p with [p1, ex1; p2,ex2 ...]
 // match "a" with ["a", 1; "b", 2]
 let expr2 = Match(Logical(Equal(Ident("a"), Ident("a")),Const(1),Logical(Equal(Ident("a"),Ident("b")),Const(2), Const(0))))

 // if a+3 > b+c && a>0 then c+d else e
 let expr1 = Logical(And(BiggerThan(Sum(Ident("a"), Const(3)),Sum(Ident("b"),Ident("c"))), BiggerThan(Ident("a"), Const(0))), Sum(Ident("c"),Ident("d")),Ident("e"))

 // a* (-3 + let x = 5 in x + a)
 let expr = Prod(Ident "a", Sum( Minus(Const(3)), Let("x", Const(5), Sum(Ident "x", Ident "a"))))

 // 2. Extend the function eval defined in the lecture to support the
 // if-then-else expressions defined in Q1.

 // eval ExprTree -> map<string, int> -> int
 let rec eval t env =
     match t with
     | Const n -> n
     | Ident s -> Map.find s env
     | Minus t -> - (eval t env)
     | Sum (t1, t2) -> eval t1 env + eval t2 env
     | Diff (t1, t2) -> eval t1 env - eval t2 env
     | Prod (t1, t2) -> eval t1 env * eval t2 env
     | Let (s, t1, t2) ->
             let v1 = eval t1 env
             let env1 = Map.add s v1 env
             eval t2 env1
     | Logical (t1, t2, t3) ->
         if (eval t1 env) = 1
         then eval t2 env
         else eval t3 env
     | BiggerThan (t1, t2) ->
         if eval t1 env > eval t2 env
         then 1
         else 0
     | LesserThan (t1, t2) ->
         if eval t1 env < eval t2 env
         then 1
         else 0
     | BiggerEq (t1, t2) ->
         if eval t1 env >= eval t2 env
         then 1
         else 0
     | LesserEq (t1, t2) ->
         if eval t1 env <= eval t2 env
         then 1
         else 0
     | Equal (t1, t2) ->
         if eval t1 env = eval t2 env
         then 1
         else 0
     | And (t1, t2) ->
         if (eval t1 env + eval t2 env) = 2
         then 1
         else 0
     | Or (t1, t2) ->
         if (eval t1 env + eval t2 env) >= 1
         then 1
         else 0
     | Not (t1) ->
         if eval t1 env = 1
         then 0
         else 1
     | Match (t1) ->
         eval t1 env

+(*
+  FEEDBACK:
+
+    OK
+*)

 let map1 = Map.ofList[("a",1);("b",2);("c",3);("d",4);("e",5)]

 eval expr1 map1
 eval expr2 map1
 // 3-4: Given the type definition:
 type BList =
   | BEmpty
   | Snoc of BList * int

 // 3. Make the function filterB: (prop: int -> bool) BList -> BList that will return a list for the elements of which
 // the function prop returns true.

 let rec filterB (prop: int -> bool) (input: BList): BList =
     match input with
     | BEmpty -> BEmpty
     | Snoc(head, tail) ->
         let filtered = filterB prop head
         if prop tail
         then Snoc (filtered, tail)
         else filtered

+(*
+  FEEDBACK:
+
+    OK
+*)
+
 let testList = Snoc(Snoc(BEmpty,3),2)
 let func = (>) 3
 filterB func testList

 // 4. Make the function mapB: (trans: int -> int) BList -> BList that will return a list where the function trans has
 // been applied to each element.

 let rec mapB (trans: int -> int) (input: BList): BList =
     match input with
     | BEmpty -> BEmpty
     | Snoc (head, tail) -> Snoc(mapB trans head, trans tail)

+(*
+  FEEDBACK:
+
+    OK
+*)
+
 let addOne = (+) 1
 mapB addOne testList

 // 5-7. Given the type definition
 type Tree =
   | Nil
   | Branch2 of Tree * int * Tree
   | Branch3 of Tree * int * Tree * int * Tree
 //
 // 5. Define the value exampleTree : Tree that represents the following
 //    tree:
 //
 //        2
 //       / \
 //      *  3 5
 //        / | \
 //       *  *  *

 let exampleTree: Tree = Branch2(Nil, 2, Branch3(Nil, 3, Nil, 5, Nil))

+(*
+  FEEDBACK:
+
+    OK
+*)
+
 // 6. Define a function sumTree : Tree -> int that computes the sum of
 //    all labels in the given tree.

 let rec sumTree (tree: Tree): int =
     match tree with
     | Nil -> 0
     | Branch2(tree1, int1, tree2) -> sumTree tree1 + int1 + sumTree tree2
     | Branch3(tree1, int1, tree2, int2, tree3) -> sumTree tree1 + int1 + sumTree tree2 + int2 + sumTree tree3

+(*
+  FEEDBACK:
+
+    OK
+*)
+
 sumTree exampleTree

 // 7. Define a function productTree : Tree -> int that computes the
 //    product of all labels in the given tree. If this function
 //    encounters a label 0, it shall not look at any further labels, but
 //    return 0 right away.

 let rec productTree (tree: Tree): int =
     match tree with
     | Nil -> 1
     | Branch2(tree1, int1, tree2) ->
         if int1 = 0
         then 0
         else productTree tree1 * int1 * productTree tree2
     | Branch3(tree1, int1, tree2, int2, tree3) ->
         if (int1 = 0 || int2 = 0)
         then 0
         else productTree tree1 * int1 * productTree tree2 * int2 * productTree tree3

+(*
+  FEEDBACK:
+
+    While your implementation does not look at the subtrees if it encounters a
+    labelĀ 0, it still looks at all other remaining parts of the tree, which it
+    should not do.
+*)
+
 let exampleTree2 = Nil
 productTree exampleTree

 // ** Bonus questions **

 // 8. Extend the ExprTree type with a pattern match expression
 // match p with [p1, ex1; p2,ex2 ...]

 // 9. Extend the eval function to support match expressions.