OperationsInductiveDefinitions.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Operations on Inductively Defined Structures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Previously, we examined inductive definitions starting with numbers, lists, binary trees, arithmetic expressions and a simple imperative language. However, beyond defining them, we did not do much else with them. In this lecture, we will fix this by performing a variety of exciting operations on inductively defined structures we have defined so far.\n",
    "\n",
    "We will examine two mechanisms for defining these operations: \n",
    "1. Using a _visitor_: i.e, implement the operation as a member function as we will see.\n",
    "2. Using pattern matching: this is a special feature of functional languages like Scala, Lisp, Caml and Haskell. Although you will find libraries in Python (https://github.com/grantjenks/python-pattern-matching) and C++ (https://github.com/solodon4/Mach7) that can mimic this very powerful feature. \n",
    "\n",
    "The first option is generically applicable to most languages. The second one is very special and very powerful. We will focus extensively on the second option of pattern matching, while mentioning what a visitor pattern is.\n",
    "\n",
    "## Operations on Numbers\n",
    "\n",
    "Let us recall the grammar for inductively defining numbers.\n",
    "\n",
    "$$\\textbf{NatNum} \\ \\rightarrow\\ Z\\; |\\; Succ(\\textbf{NatNum}) $$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mtrait\u001b[39m \u001b[36mNatNum\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mZ\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mSucc\u001b[39m"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sealed trait NatNum\n",
    "\n",
    "case object Z extends NatNum\n",
    "\n",
    "case class Succ(n : NatNum) extends NatNum\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The simplest function we can imagine is to add one to a given NatNum. This is easy to write since this is exactly what *Succ* does."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36maddOne\u001b[39m"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def addOne(n:NatNum) = Succ(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mtwo\u001b[39m: \u001b[32mSucc\u001b[39m = Succ(Succ(Z))\n",
       "\u001b[36mthree\u001b[39m: \u001b[32mSucc\u001b[39m = Succ(Succ(Succ(Z)))"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val two = Succ(Succ(Z))\n",
    "val three = addOne(two)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we wish to write a function _minusOne_ that given a number subtracts one from it. Before we do so, we have to understand how to handle the zero case. We could raise an error/exception saying that it is undefined. This is the best way to do it since it is the most honest.\n",
    "\n",
    "Here is how we should do it. \n",
    "\n",
    "~~~\n",
    "minusOne(s) =  if s is of the form Succ(t) then return t, else s must be Z and return Error\n",
    "~~~\n",
    "\n",
    "Therefore we need a construct that checks if a given input NatNum is of the form Succ(t) and extracts this inner stuff t, but how?\n",
    "\n",
    "There are two solutions to this.  First is to redefine things to have the _minusOne_ function implemented inside each class. This solves the problem using the way object oriented programs work.\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mtrait\u001b[39m \u001b[36mNatNum1\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mZ1\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mSucc1\u001b[39m"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sealed trait NatNum1 {\n",
    "    def minusOne(): NatNum1\n",
    "}\n",
    "\n",
    "case object Z1 extends NatNum1{\n",
    "    def minusOne(): NatNum1  = {\n",
    "        throw (new IllegalArgumentException(\"minusOne cannot be called on Zero\"))\n",
    "    }\n",
    "}\n",
    "\n",
    "case class Succ1(n: NatNum1) extends NatNum1 {\n",
    "    def minusOne(): NatNum1 =  {\n",
    "        return this.n\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "NatNum1 is the base class (it is an abstract class or a trait in scala). What this means is that any class that inherits from it must have all the members that are defined in it. We define a member minusOne() corresponding to the function we wish to implement. Therefore, when we call the minusOne function on an instance of NatNum1, the instance can be either a Z1 or a Succ1 class. In either case, the object system in scala ensures that the right function gets called. This is an indirect but effective way of finding out the question if a given NatNum1 is of the form Z1 or Succ1(t)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mt1\u001b[39m: \u001b[32mZ1\u001b[39m.type = Z1\n",
       "\u001b[36mt2\u001b[39m: \u001b[32mSucc1\u001b[39m = Succ1(Succ1(Succ1(Z1)))\n",
       "\u001b[36mt3\u001b[39m: \u001b[32mNatNum1\u001b[39m = Succ1(Succ1(Z1))"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val t1 = Z1\n",
    "val t2 = Succ1(Succ1(Succ1(Z1)))\n",
    "val t3 = t2.minusOne()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[31mjava.lang.IllegalArgumentException: minusOne cannot be called on Zero\u001b[39m",
      "  $sess.cmd3Wrapper$Helper$Z1$.minusOne(\u001b[32mcmd3.sc\u001b[39m:\u001b[32m7\u001b[39m)",
      "  $sess.cmd5Wrapper$Helper.<init>(\u001b[32mcmd5.sc\u001b[39m:\u001b[32m1\u001b[39m)",
      "  $sess.cmd5Wrapper.<init>(\u001b[32mcmd5.sc\u001b[39m:\u001b[32m127\u001b[39m)",
      "  $sess.cmd5$.<init>(\u001b[32mcmd5.sc\u001b[39m:\u001b[32m86\u001b[39m)",
      "  $sess.cmd5$.<clinit>(\u001b[32mcmd5.sc\u001b[39m:\u001b[32m-1\u001b[39m)"
     ]
    }
   ],
   "source": [
    "val t4 = t1.minusOne() // This will throw an exception"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The second way to do it is using the idea of _pattern matching_: a very powerful feature that is available in some functional programming languages including scala. Here is how it works.\n",
    "\n",
    "An instance object of type NatNum can be of two forms Succ(t) or Z. Scala provides a construct very similar to the case statement in C like languages, but much more powerful."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mminusOne\u001b[39m"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def minusOne(num: NatNum): NatNum = {\n",
    "    num match {\n",
    "        case Succ(t) => t // Is n of the form Succ(t), then return t\n",
    "        // The magic here is that the variable t gets assigned to the contents of num.n in this case.\n",
    "        case Z => throw new IllegalArgumentException(\"minusOne cannot be called on Zero\")\n",
    "        // Is n of the form Z, then throw an exception\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mt5\u001b[39m: \u001b[32mNatNum\u001b[39m = Succ(Succ(Z))"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val t5 = minusOne(Succ(Succ(Succ(Z))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[31mjava.lang.IllegalArgumentException: minusOne cannot be called on Zero\u001b[39m",
      "  $sess.cmd6Wrapper$Helper.minusOne(\u001b[32mcmd6.sc\u001b[39m:\u001b[32m5\u001b[39m)",
      "  $sess.cmd8Wrapper$Helper.<init>(\u001b[32mcmd8.sc\u001b[39m:\u001b[32m1\u001b[39m)",
      "  $sess.cmd8Wrapper.<init>(\u001b[32mcmd8.sc\u001b[39m:\u001b[32m143\u001b[39m)",
      "  $sess.cmd8$.<init>(\u001b[32mcmd8.sc\u001b[39m:\u001b[32m94\u001b[39m)",
      "  $sess.cmd8$.<clinit>(\u001b[32mcmd8.sc\u001b[39m:\u001b[32m-1\u001b[39m)"
     ]
    }
   ],
   "source": [
    "val t6 = minusOne(Z) // Boom!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us write code to add two NatNum. The basic idea is this: \n",
    "- If the first argument to the call is of the form Z, then the answer is the second argument since 0 + something = something.\n",
    "- If the first argument is of the form Succ(t) then simply make a recursive call to add t with Succ(second argument). We are simply saying (1 + t) + n = t + (1 + n)\n",
    "\n",
    "Let us see how pattern matching can help us do this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36maddNatNums\u001b[39m"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def addNatNums (n1: NatNum, n2: NatNum ): NatNum = {\n",
    "    n1 match {\n",
    "        case Z => n2  // If n1 == Z, then the result is just n2\n",
    "        case Succ(t) => addNatNums(t, Succ(n2)) // Otherwise, the result is to peel of a Succ from first argument \n",
    "        // and add it to the second argument.\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mtwo\u001b[39m: \u001b[32mSucc\u001b[39m = Succ(Succ(Z))\n",
       "\u001b[36mthree\u001b[39m: \u001b[32mSucc\u001b[39m = Succ(Succ(Succ(Z)))\n",
       "\u001b[36mfive\u001b[39m: \u001b[32mNatNum\u001b[39m = Succ(Succ(Succ(Succ(Succ(Z)))))\n",
       "\u001b[36mten\u001b[39m: \u001b[32mNatNum\u001b[39m = Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Z))))))))))"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val two = Succ(Succ(Z))\n",
    "val three = addOne(two)\n",
    "val five = addNatNums(two, three)\n",
    "val ten = addNatNums(five, five)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For curiosity, how would we implement it using the _visitor pattern_ ? Let us now redefine NatNum1 to require a new member function addNatNums. You can see how instead of pattern matching, we simply write the code for the zero case inside the object Z1 and the code for the successor case inside the object Succ1. The idea is the same as before but the two cases get split into two different member functions of Z1 and Succ1, respectively."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mtrait\u001b[39m \u001b[36mNatNum1\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mZ1\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mSucc1\u001b[39m"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sealed trait NatNum1 {\n",
    "    def minusOne(): NatNum1\n",
    "    def addNatNums(n1: NatNum1): NatNum1\n",
    "}\n",
    "\n",
    "case object Z1 extends NatNum1{\n",
    "    def minusOne(): NatNum1  = {\n",
    "        throw (new IllegalArgumentException(\"minusOne cannot be called on Zero\"))\n",
    "    }\n",
    "    \n",
    "    def addNatNums(n1: NatNum1): NatNum1 = n1 // return is optional\n",
    "    \n",
    "}\n",
    "\n",
    "case class Succ1(n: NatNum1) extends NatNum1 {\n",
    "    def minusOne(): NatNum1 =  {\n",
    "        return this.n\n",
    "    }\n",
    "    def addNatNums(n1: NatNum1): NatNum1 =  this.n.addNatNums(Succ1(n1)) // return is optional\n",
    "    \n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mtwo\u001b[39m: \u001b[32mSucc1\u001b[39m = Succ1(Succ1(Z1))\n",
       "\u001b[36mthree\u001b[39m: \u001b[32mSucc1\u001b[39m = Succ1(Succ1(Succ1(Z1)))\n",
       "\u001b[36mfive\u001b[39m: \u001b[32mNatNum1\u001b[39m = Succ1(Succ1(Succ1(Succ1(Succ1(Z1)))))\n",
       "\u001b[36mten\u001b[39m: \u001b[32mNatNum1\u001b[39m = Succ1(Succ1(Succ1(Succ1(Succ1(Succ1(Succ1(Succ1(Succ1(Succ1(Z1))))))))))"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val two = Succ1(Succ1(Z1))\n",
    "val three = Succ1(two)\n",
    "val five = two.addNatNums(three)\n",
    "val ten = five.addNatNums(five)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once we have addition, multiplication can now be implemented using recursion, as below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mmultiplyNatNums\u001b[39m"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def multiplyNatNums(n1: NatNum, n2: NatNum ): NatNum = {\n",
    "    n1 match {\n",
    "        case Z => { return Z }\n",
    "        case Succ(t) => { \n",
    "            // (t+1)* n2 = t * n2 + n2\n",
    "            val s1 = multiplyNatNums(t, n2) // t * n2\n",
    "            addNatNums(n2, s1) // n2 + t * n2 = (t+1)* n2 = n1 * n2!\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mfour\u001b[39m: \u001b[32mSucc\u001b[39m = Succ(Succ(Succ(Succ(Z))))\n",
       "\u001b[36mfive\u001b[39m: \u001b[32mSucc\u001b[39m = Succ(Succ(Succ(Succ(Succ(Z)))))\n",
       "\u001b[36mtwenty\u001b[39m: \u001b[32mNatNum\u001b[39m = Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Z))))))))))))))))))))\n",
       "\u001b[36mhundred\u001b[39m: \u001b[32mNatNum\u001b[39m = Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Succ(Z))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val four = Succ(Succ(Succ(Succ(Z))))\n",
    "val five = addOne(four)\n",
    "val twenty = multiplyNatNums(five, four)\n",
    "val hundred = multiplyNatNums(five, twenty)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Operations on List of Numbers\n",
    "\n",
    "Recall that we previously defined a grammar for lists.\n",
    "$$\\begin{array}{ccccc}\n",
    "\\textbf{NumList} & \\rightarrow & Nil &\\ |\\  & Cons(\\textbf{Num}, \\textbf{NumList}) \\\\\n",
    "\\textbf{Num} & \\rightarrow & 0 \\ |\\ 1\\ |\\ 2\\ |\\ 3\\ |\\ 4\\ |\\ \\cdots \\\\\n",
    "\\end{array}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mtrait\u001b[39m \u001b[36mNumList\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mNil\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mCons\u001b[39m"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sealed trait NumList\n",
    "\n",
    "case object Nil extends NumList\n",
    "\n",
    "case class Cons(hd: Int, tl: NumList) extends NumList"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are many exciting things we wish to do to lists. The simplest one is to find the length of a list.\n",
    "How do we do that in principle?\n",
    "- The length of the empty list Nil is zero\n",
    "- The length of the list of the form Cons(something, tail) is 1 + length(tail)\n",
    "\n",
    "Let us use pattern matching to implement this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mlistLength\u001b[39m"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def listLength(lst: NumList): Int = { lst match { // pattern match the lst\n",
    "    case Nil => 0\n",
    "    case Cons(_, tl) => 1 + listLength(tl) // _ here is to tell scala that I do not care what is the element.\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How would we do it using a visitor? Simple, the listLength function is going to become a member of the trait \n",
    "NumList and get implemented in all the classes that inherit from it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mtrait\u001b[39m \u001b[36mAltNumList\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mAltNil\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mAltCons\u001b[39m"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sealed trait AltNumList{\n",
    "    def listLength(): Int\n",
    "}\n",
    "\n",
    "case object AltNil extends AltNumList {\n",
    "    def listLength(): Int = 0\n",
    "}\n",
    "\n",
    "case class AltCons(hd: Int, tl: AltNumList)  extends AltNumList {\n",
    "    def listLength(): Int = {\n",
    "        1  + tl.listLength()\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36ml1\u001b[39m: \u001b[32mAltCons\u001b[39m = AltCons(1,AltCons(3,AltCons(7,AltNil)))\n",
       "\u001b[36mj1\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m3\u001b[39m"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val l1 = AltCons(1, AltCons(3, AltCons(7, AltNil)))\n",
    "val j1 = l1.listLength()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You may now be wondering why we are bothering describing both visitor functions and pattern matches. Aren't they just two different ways of achieving the same effect? The answer to that is yes for about 90% of the cases, but not always. Pattern matching can make life infinitely more easier. \n",
    "\n",
    "\n",
    "I would like to write a function now that does the following: given a list, check if it is sorted in ascending order.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36misAscendingOrder\u001b[39m"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def isAscendingOrder (l: NumList): Boolean = l match {\n",
    "    \n",
    "    case Nil => true // An empty list is ascending sure!\n",
    "    \n",
    "    case Cons(_, Nil) => true // A list with just one element is surely ascending ordered\n",
    "    \n",
    "    case Cons(j1, tl @ Cons(j2, _)) => (j1 <= j2) && isAscendingOrder(tl) \n",
    "    // We did something funky:\n",
    "    // We pattern matched the first two elements of the list to j1 and j2 respectively.\n",
    "    // Also, we told scala to call Cons(j2, _) by the name tl using the @ symbol. \n",
    "    // This is called pattern matching with names.\n",
    "    \n",
    "    \n",
    "    case _ => { assert(false); false } // This is the catch all case and should never happen.\n",
    "    \n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mb1\u001b[39m: \u001b[32mBoolean\u001b[39m = \u001b[32mtrue\u001b[39m"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val b1 = isAscendingOrder( Cons(1, Cons(3, Cons(3, Cons(5, Cons(10, Nil ))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mb2\u001b[39m: \u001b[32mBoolean\u001b[39m = \u001b[32mfalse\u001b[39m"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val b2 = isAscendingOrder( Cons(5, Cons(3, Cons(3, Cons(5, Cons(10, Nil ))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mb3\u001b[39m: \u001b[32mBoolean\u001b[39m = \u001b[32mfalse\u001b[39m"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val b3 = isAscendingOrder( Cons(0, Cons(3, Cons(3, Cons(5, Cons(4, Nil ))))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Things can be made even more funky with pattern matching. But this is where you should read a tutorial on pattern matching to acquaint yourself with all the funky features: https://docs.scala-lang.org/tour/pattern-matching.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36misAscendingOrderAlt\u001b[39m"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def isAscendingOrderAlt (l : NumList) : Boolean = l match {\n",
    "    case Nil => true\n",
    "    \n",
    "    case Cons(_, Nil) => true\n",
    "    \n",
    "    case Cons(j1, Cons(j2, _)) if (j1 > j2) => false // This case matches only if j1 > j2\n",
    "    \n",
    "    case Cons(_, tl) => isAscendingOrderAlt(tl) // We can reach this case only if j1 <= j2, \n",
    "                                                // so there is no need to expand tl out\n",
    "    \n",
    "    // A catch all case is not needed: can you argue why?\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mb4\u001b[39m: \u001b[32mBoolean\u001b[39m = \u001b[32mtrue\u001b[39m"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val b4 = isAscendingOrderAlt(Cons(1, Cons(3, Cons(3, Cons(5, Cons(10, Nil ))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mb5\u001b[39m: \u001b[32mBoolean\u001b[39m = \u001b[32mfalse\u001b[39m"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val b5 =  isAscendingOrderAlt( Cons(0, Cons(3, Cons(3, Cons(5, Cons(4, Nil ))))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pattern matching really helps us in this example: *isAscendingOrder* is not easy to implement as a visitor. It will require something messy such as storing the previous element of the array in a global variable, extra function argument or doing something akin to pattern matching to try and extract the next array element. Can you try some of these options?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One nice operation on list is to reverse the list. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mappendToEndHelper\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mreverseBad\u001b[39m"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// First consider a helper function that will take the list l and append an element e to its end\n",
    "def appendToEndHelper(l: NumList, e: Int): NumList = l match { \n",
    "    case Nil => Cons(e, Nil)\n",
    "    case Cons(j, tl) => Cons(j, appendToEndHelper(tl, e))\n",
    "}\n",
    "\n",
    "// Use the helper function appendToEndHelper to now define reverse\n",
    "def reverseBad(l: NumList): NumList = l match {\n",
    "    case Nil => Nil // Reverse of an empty list is empty\n",
    "    case Cons(n1, t1) => {\n",
    "        val r1 = reverseBad(t1) // reverse the tail\n",
    "        appendToEndHelper(r1, n1) // append n1 to the end.\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36ml1\u001b[39m: \u001b[32mCons\u001b[39m = Cons(1,Cons(3,Cons(5,Cons(7,Nil))))\n",
       "\u001b[36ml2\u001b[39m: \u001b[32mNumList\u001b[39m = Cons(7,Cons(5,Cons(3,Cons(1,Nil))))"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val l1 = Cons(1, Cons(3, Cons(5, Cons(7, Nil))))\n",
    "val l2 = reverseBad(l1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is the key question you should be asking. Why is the reverse method we wrote previously \"Bad\"?  The answer has to do with its complexity. It is often hard to understand what the complexity is when you write recursive functions. But imagine the same logic carried out on a linked list with a for loop. Can you now guess what the complexity would be on a list of length $n$?\n",
    "\n",
    "If you guessed $\\Theta(n^2)$, you are absolutely right. But this is a pity since we would like to reverse a list in time $\\Theta(n)$. How can we achieve that?\n",
    "\n",
    "Let us write a helper function with two arguments: the first argument is the tail of the list that we are yet to reverse, and the other argument is the reverse of the prefix of the list. Initially, the tail to be reversed is the entire list and the prefix is just Nil or the empty list. But as we \"peel off\" each element of the list, it joins the front of the reverse list so far. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mreverseHelper\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mreverseGood\u001b[39m"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def reverseHelper(l: NumList, resultSoFar: NumList): NumList = l match {\n",
    "    case Nil => resultSoFar\n",
    "    case Cons(n, tail) => {\n",
    "        val v1 = Cons(n, resultSoFar)\n",
    "        return reverseHelper(tail, v1 )\n",
    "    }\n",
    "}\n",
    "// This will now run in \\Theta(n^2) rather than \\Theta(n) time\n",
    "def reverseGood(l: NumList): NumList = reverseHelper(l, Nil)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36ml3\u001b[39m: \u001b[32mNumList\u001b[39m = Cons(7,Cons(5,Cons(3,Cons(1,Nil))))"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val l3 = reverseGood(l1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Operations on Trees with Numbers\n",
    "\n",
    "Let us now get to the grammar of trees with numbers. Recall the grammar\n",
    "\n",
    "$$\\begin{array}{rclclcl}\n",
    "\\textbf{NumTree} & \\rightarrow & Leaf & \\ |\\ & Node(\\textbf{Num}, \\textbf{NumTree}, \\textbf{NumTree}) \\\\\n",
    "\\textbf{Num} & \\rightarrow & 0 \\ |\\ 1\\ |\\ 2\\ | \\ 3 \\ |\\ \\cdots \\\\\n",
    "\\end{array}$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mtrait\u001b[39m \u001b[36mNumTree\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mLeaf\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mNode\u001b[39m"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sealed trait NumTree\n",
    "case object Leaf extends NumTree\n",
    "case class Node(n: Int, left: NumTree, right: NumTree) extends NumTree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Just like we defined length for a list, you can define functions like *depth* of a tree, *number* of leaves in a tree, *number* of nodes and so on.\n",
    "\n",
    "But let us do something more interesting here.  We would like to check if a tree has the binary search tree property. \n",
    "\n",
    "Recall this property that says that for every node all the elements of its left subtree (if not a leaf) must be smaller than the node and all right subtree elements must be larger than the node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36misBST_WrongCode\u001b[39m"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// A simple attempt is to check at each node if its left child is smaller and right child is larger.\n",
    "// This is wrong: you should be able to come up with an example why\n",
    "def isBST_WrongCode(t: NumTree): Boolean = t match {\n",
    "    case Leaf => true // Nothing to say for a leaf\n",
    "    case Node(n, Leaf, Leaf) => true // Nothing to check since both children are leaves\n",
    "    case Node(n1, Node(n2, _, _ ), _ ) if (n2 > n1) => false // Violates BST property \n",
    "    case Node(n1, _, Node(n3, _, _) )  if (n3 < n1) => false // Violates BST property\n",
    "    case Node(n1, leftChild, rightChild) => isBST_WrongCode(leftChild) && isBST_WrongCode(rightChild) // The previous two cases did not match\n",
    "    // Therefore, we conclude that n2 <= n1 and n3 >= n1, so all that remains is to \n",
    "    // check BST property of left and right children.\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mfindMaxElementHelper\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mfindMinElementHelper\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36misBST\u001b[39m"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def findMaxElementHelper(t: NumTree): Int = t match {\n",
    "    case Leaf => Int.MinValue // Make it a smallest number \n",
    "    case Node(n, t1, t2) => { val v1 = findMaxElementHelper(t1) \n",
    "                              val v2 = findMaxElementHelper(t2) \n",
    "                              return List(n, v1, v2).max } \n",
    "}\n",
    "\n",
    "def findMinElementHelper(t: NumTree): Int = t match {\n",
    "    case Leaf => Int.MaxValue \n",
    "    case Node(n, t1, t2) => {\n",
    "        val v1 = findMinElementHelper(t1)\n",
    "        val v2 = findMinElementHelper(t2)\n",
    "        return List(n, v1, v2).min\n",
    "    }\n",
    "    \n",
    "}\n",
    "\n",
    "def isBST(t: NumTree): Boolean = t match {\n",
    "    case Leaf => true\n",
    "    case Node(n1, lChild, rChild) => {\n",
    "        val maxLeft = findMaxElementHelper(lChild)\n",
    "        val minRight = findMinElementHelper(rChild)\n",
    "        (n1 >= maxLeft) && (n1 <= minRight)\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mtree1\u001b[39m: \u001b[32mNode\u001b[39m = Node(1,Node(2,Node(3,Leaf,Leaf),Node(2,Leaf,Leaf)),Node(4,Leaf,Leaf))\n",
       "\u001b[36mtree2\u001b[39m: \u001b[32mNode\u001b[39m = Node(6,Node(2,Node(1,Leaf,Leaf),Leaf),Node(10,Node(7,Leaf,Leaf),Leaf))"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val tree1 = Node(1, Node(2, Node(3, Leaf, Leaf), Node(2, Leaf, Leaf)), Node(4, Leaf, Leaf))\n",
    "val tree2 = Node(6, Node(2, Node(1, Leaf, Leaf), Leaf), Node(10, Node(7, Leaf, Leaf), Leaf))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mb1\u001b[39m: \u001b[32mBoolean\u001b[39m = \u001b[32mfalse\u001b[39m"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val b1 = isBST(tree1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mb2\u001b[39m: \u001b[32mBoolean\u001b[39m = \u001b[32mtrue\u001b[39m"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val b2 = isBST(tree2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We still have a problem here. This time it is a problem of efficiency. The `isBST` method we wrote is quite\n",
    "inefficient since it performs two passes over the tree. In the \"outer pass\" it visits each node in the tree and\n",
    "then at each node, it performs yet another pass to find max and min elements of left and right subtrees.\n",
    "\n",
    "What is the complexity of this approach: look at it from the point of view of each node. It is visited once in the outer iteration and for the inner loop, it is visited once for each parent. Thus the number of visits for each node is 1 + height of the node. Thus, total work done is the sum of the heights of all nodes in the tree. In the worst case this is $\\Theta(n^2)$ worst case being achieved for the completely unbalanced binary tree.\n",
    "\n",
    "Thus, we face the familiar problem we did when we tried to reverse a list: correct but inefficient code.\n",
    "\n",
    "Let us make it efficient: how? \n",
    "\n",
    "The idea is to keep a bit of extra information for each subtree as we descend down in the outer iteration. Suppose we are at the root, we have no limits on what the values of the individual nodes can be. Thus, we start at the root \n",
    "and allow nodes to be in the interval $(-\\infty, \\infty)$. Suppose the root had the number $r$, we know that \n",
    "everything to its left can only be in the interval $(-\\infty, r]$ and the right subtree in $[r, \\infty)$.\n",
    "If we keep going, at any node, we get an interval $[l, u]$ of allowable values. If the node value $v$ lies in that\n",
    "range, we know that the left subtree must be in the range $[l, v]$ and right subtree in $[v,r]$. This gives us the plan to move forward with a helper function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36misBST_Eff_Helper\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36misBST_Efficient\u001b[39m"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def isBST_Eff_Helper(t: NumTree, l: Int, r: Int): Boolean = t match {\n",
    "    case Leaf => true\n",
    "    case Node(j, lChild, rChild) if (l <= j && j <= r) => { \n",
    "        isBST_Eff_Helper(lChild, l, j) && isBST_Eff_Helper(rChild, j, r)\n",
    "    } \n",
    "    case _ => false\n",
    "}\n",
    "\n",
    "def isBST_Efficient(t: NumTree): Boolean = isBST_Eff_Helper(t, Int.MinValue, Int.MaxValue)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mb3\u001b[39m: \u001b[32mBoolean\u001b[39m = \u001b[32mfalse\u001b[39m"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val b3 = isBST_Efficient(tree1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mb4\u001b[39m: \u001b[32mBoolean\u001b[39m = \u001b[32mtrue\u001b[39m"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val b4 = isBST_Efficient(tree2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Arithmetic Expressions\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Arithmetic expressions are generated by the grammar we saw before.\n",
    "\n",
    "$$\\begin{array}{rcll}\n",
    "\\textbf{Expr} & \\rightarrow & Const(\\textbf{Double}) \\\\\n",
    "& |  & Ident(\\textbf{Identifier}) \\\\\n",
    "& | & Plus( \\textbf{Expr}^+) & \\text{Note:}\\ A^+ \\ \\text{is one or more reps of}\\ A \\\\\n",
    "& | & Minus( \\textbf{Expr}, \\textbf{Expr}^+) \\\\\n",
    "& | & Mult(\\textbf{Expr}^+) \\\\\n",
    "& | & Div(\\textbf{Expr}, \\textbf{Expr}) \\\\\n",
    "& | & Log(\\textbf{Expr}) \\\\\n",
    "& | & Exp(\\textbf{Expr}) \\\\\n",
    "& | & Sine(\\textbf{Expr}) \\\\\n",
    "& | & Cosine(\\textbf{Expr}) \\\\\\\\\n",
    "\\textbf{Double} & \\rightarrow & \\text{all double precision numbers in Scala}\\\\\n",
    "\\textbf{Identifier} & \\rightarrow & [a-zA-Z][a-z\\ A-Z\\ 0-9\\ \\_]* & \\text{Note: All strings that begin with letters}\\\\\n",
    "&&& \\text{a-z or A-Z and subsequently can contain a-z, A-Z, 0-9 or _ chars}\n",
    "\\end{array}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mtrait\u001b[39m \u001b[36mExpr\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mConst\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mIdent\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mPlus\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mMinus\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mMult\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mDiv\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mLog\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mExp\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mSine\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mCosine\u001b[39m"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sealed trait Expr\n",
    "case class Const(f: Double) extends Expr \n",
    "// 1. We cheated a bit and allowed all floating point numbers\n",
    "// Also, this deviates from the grammar\n",
    "case class Ident(s: String) extends Expr\n",
    "// 2. We allow any string to be an identifier for now instead of the regular expression shown in the grammar.\n",
    "case class Plus( eList: List[Expr] ) extends Expr\n",
    "case class Minus(e1: Expr, eList: List[Expr]) extends Expr\n",
    "case class Mult(eList: List[Expr]) extends Expr\n",
    "case class Div(e1: Expr, e2: Expr) extends Expr\n",
    "case class Log(e: Expr) extends Expr\n",
    "case class Exp(e: Expr) extends Expr\n",
    "case class Sine(e: Expr) extends Expr\n",
    "case class Cosine(e: Expr) extends Expr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The simplest function we wish to write will collect all the variables that are used in a given expression inside a Set data structure. Read about scala sets here: https://docs.scala-lang.org/overviews/collections/sets.html\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mcollectAllVariables\u001b[39m"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def collectAllVariables(e: Expr): Set[String] = {\n",
    "    def helperFunction(eList: List[Expr], startValue: Set[String]): Set[String] = {\n",
    "        // Iterate through the list eList and collect set of variables for each expression in eList.\n",
    "        // Next: take the union of all the sets with the given set startValue.\n",
    "            eList.foldLeft (startValue) {\n",
    "                case (setSoFar: Set[String], newExpr:Expr) => { val v = collectAllVariables(newExpr)\n",
    "                                              setSoFar union v\n",
    "                                            }\n",
    "        \n",
    "            }\n",
    "        // If you insist on a for loop, you have to use a var\n",
    "        // var setSoFar = startValue\n",
    "        // for (newExpr <- eList) {\n",
    "        //   setSoFar = setSoFar.union(collectAllVariables(newExpr))\n",
    "        //    }\n",
    "        // return setSoFar\n",
    "    }\n",
    "        \n",
    "    e match {\n",
    "        case Const(f) => Set() // Return the empty set\n",
    "        case Ident(s) => Set(s) // Return a singleton set with s in it.\n",
    "        case Plus(eList) => helperFunction(eList, Set())  //Union of all variables in eList\n",
    "        case Mult(eList) => helperFunction(eList, Set()) // Union of all variables in eList\n",
    "    \n",
    "        case Minus(e1, eList) => {\n",
    "            val e1Set = collectAllVariables(e1) // First collect variables in e1\n",
    "            helperFunction(eList, e1Set) // take union of all variables in eList with e1Set from prev. step\n",
    "        }\n",
    "    \n",
    "    \n",
    "        case Div(e1, e2) => {\n",
    "            (collectAllVariables(e1)) union (collectAllVariables(e2))\n",
    "        }\n",
    "        case Log(e1) => collectAllVariables(e1)\n",
    "        case Sine(e1) => collectAllVariables(e1)\n",
    "        case Cosine(e1) => collectAllVariables(e1)\n",
    "        case Exp(e1) => collectAllVariables(e1)\n",
    "        case _ => { assert(false); return Set()  } // This is the catch all. Should not happen but good coding practice\n",
    "    }\n",
    "}  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mx\u001b[39m: \u001b[32mIdent\u001b[39m = \u001b[33mIdent\u001b[39m(\u001b[32m\"x\"\u001b[39m)\n",
       "\u001b[36my\u001b[39m: \u001b[32mIdent\u001b[39m = \u001b[33mIdent\u001b[39m(\u001b[32m\"y\"\u001b[39m)\n",
       "\u001b[36mz\u001b[39m: \u001b[32mIdent\u001b[39m = \u001b[33mIdent\u001b[39m(\u001b[32m\"Zzz\"\u001b[39m)\n",
       "\u001b[36mexpr1\u001b[39m: \u001b[32mPlus\u001b[39m = Plus(List(Cosine(Ident(x)), Sine(Ident(y)), Exp(Minus(Ident(x),List(Ident(y), Ident(Zzz))))))"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// cos(x) + sin(y) + e^{x - y - Zzz}\n",
    "val x = Ident(\"x\")\n",
    "val y = Ident(\"y\")\n",
    "val z = Ident(\"Zzz\")\n",
    "val expr1 = Plus(List(Cosine(x), Sine(y), Exp(Minus(x, List(y,z)))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36ms1\u001b[39m: \u001b[32mSet\u001b[39m[\u001b[32mString\u001b[39m] = \u001b[33mSet\u001b[39m(\u001b[32m\"x\"\u001b[39m, \u001b[32m\"y\"\u001b[39m, \u001b[32m\"Zzz\"\u001b[39m)"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val s1 = collectAllVariables(expr1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mexpr2\u001b[39m: \u001b[32mPlus\u001b[39m = Plus(List(Exp(Const(1.5)), Sine(Const(2.0)), Cosine(Mult(List(Const(1.2), Const(2.4))))))"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val expr2 = Plus(List(Exp(Const(1.5)), Sine(Const(2.0)), Cosine(Mult(List(Const(1.2), Const(2.4))))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36ms2\u001b[39m: \u001b[32mSet\u001b[39m[\u001b[32mString\u001b[39m] = \u001b[33mSet\u001b[39m()"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val s2 = collectAllVariables(expr2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another important function is pretty print. We would like to pretty print our expression to Latex so that we can cut and paste it in our documents.\n",
    "\n",
    "Latex allows you to type formulae and have them displayed. Eg., let us take the formula\n",
    "\n",
    "$$ \\frac{M c^2}{ 1 + \\frac{1}{1 + c^2}}$$\n",
    "\n",
    "You would write it as\n",
    "\n",
    "\\$ \\\\frac{M c^2}{ 1 + \\\\frac{1}{1 + c^2} \\$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mtoLatex\u001b[39m"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def toLatex (e: Expr): String = {\n",
    "    e match {\n",
    "        case Const(f) => \"%2.2f\".format(f) // easy way to convert f to a string.\n",
    "        case Ident(str) => str\n",
    "        case Plus(eList) => { val strList = eList map { e =>  toLatex(e) }\n",
    "                         \"\\\\left(\"+ strList.mkString (\" + \") + \"\\\\right)\" // Join each expression into a string separated by \" + \"\n",
    "                       }\n",
    "        case Minus(e, eList) => {\n",
    "            val s1 = toLatex(e)\n",
    "            val strList = eList map {e => toLatex(e)} \n",
    "             \"\\\\left(\"+ s1 + \" - \" + (strList mkString \" - \")+ \"\\\\right)\" \n",
    "            \n",
    "        }\n",
    "        case Mult(eList) => {  \"\\\\left(\" + (eList map {toLatex(_)} mkString (\"\\\\ \")) + \"\\\\right)\"  }\n",
    "        \n",
    "        case Div(e1, e2) => { \"\\\\frac{\" + (toLatex(e1)) + \"}{\" + (toLatex(e2)) + \"}\" }\n",
    "        case Log(e) => { \"\\\\log(\" + (toLatex(e)) + \")\" }\n",
    "        case Exp(e) => { \"e^{\" + (toLatex(e)) + \"}\"}\n",
    "        case Sine(e) => { \"\\\\sin\\\\left(\"+ toLatex(e) + \"\\\\right)\" }\n",
    "        case Cosine(e) => {\"\\\\cos\\\\left(\"+ toLatex(e) + \"\\\\right)\" }\n",
    "    }\n",
    "    \n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\left(\\cos\\left(x\\right) + \\sin\\left(y\\right) + e^{\\left(x - y - Zzz\\right)}\\right)$"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36mstr1\u001b[39m: \u001b[32mString\u001b[39m = \u001b[32m\"\"\"\n",
       "$\\left(\\cos\\left(x\\right) + \\sin\\left(y\\right) + e^{\\left(x - y - Zzz\\right)}\\right)$\n",
       "\"\"\"\u001b[39m"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val str1= \"$\"+toLatex(expr1)+\"$\"\n",
    "publish.latex(str1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\frac{\\left(\\left(w + \\left(x\\ y\\right) + \\left(1.20 + w\\right)\\right) - 1.50 - w - x\\right)}{2.30}$"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36mw\u001b[39m: \u001b[32mIdent\u001b[39m = \u001b[33mIdent\u001b[39m(\u001b[32m\"w\"\u001b[39m)\n",
       "\u001b[36mexpr2\u001b[39m: \u001b[32mDiv\u001b[39m = Div(Minus(Plus(List(Ident(w), Mult(List(Ident(x), Ident(y))), Plus(List(Const(1.2), Ident(w))))),List(Const(1.5), Ident(w), Ident(x))),Const(2.3))"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val w = Ident(\"w\")\n",
    "val expr2 = Div(Minus( Plus(List(w, Mult(List(x, y)), Plus(List(Const(1.2), w))) ), List(Const(1.5), w, x) ), Const(2.3))\n",
    "\n",
    "publish.latex(\"$\"+ toLatex(expr2) + \"$\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### My First Eval Function\n",
    "\n",
    "Now we will write a very important operation called `eval`. This operation is the primary operation that an interpreter needs to carry out. \n",
    "\n",
    "But we will start small by writing an eval for our simple expression grammar. Before we do that, let us ask ourselves two questions: (a) what does it mean for the expressions to be evaluated? and (b) what is the missing information that we need before we can evaluate our arithmetic expressions defined above?\n",
    "The answers should be easy in this case:\n",
    "\n",
    "1. An arithmetic expression stands for a number which is the answer when we calculate it and \n",
    "2. Of course, the missing information is that we do not know what the valuations for the variables are to start with.\n",
    "\n",
    "Thus, we are ready to define the eval function.\n",
    "\n",
    "__Environment__ \n",
    "\n",
    "An environment $\\eta$ maps every identifier string to a numeric value. \n",
    "\n",
    "\n",
    "Example: \n",
    "\n",
    "$$ \\{ x \\mapsto 2, y \\mapsto 1.5, Zzz \\mapsto 2.8, w \\mapsto 15.2 \\}$$\n",
    "\n",
    "Scala has a Map data structure that is ideal for environments"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mmyEnvironment\u001b[39m: \u001b[32mMap\u001b[39m[\u001b[32mString\u001b[39m, \u001b[32mDouble\u001b[39m] = \u001b[33mMap\u001b[39m(\u001b[32m\"x\"\u001b[39m -> \u001b[32m2.0\u001b[39m, \u001b[32m\"y\"\u001b[39m -> \u001b[32m1.5\u001b[39m, \u001b[32m\"Zzz\"\u001b[39m -> \u001b[32m2.8\u001b[39m, \u001b[32m\"l\"\u001b[39m -> \u001b[32m129.3\u001b[39m, \u001b[32m\"w\"\u001b[39m -> \u001b[32m15.2\u001b[39m)"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val myEnvironment: Map[String, Double] = Map(\"x\" -> 2.0, \"y\" -> 1.5, \"Zzz\" -> 2.8, \"w\" -> 15.2, \"l\" -> 129.3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mevalExpr\u001b[39m"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def evalExpr (e: Expr, env: Map[String, Double]): Double = e match {\n",
    "    case Const (f) => f\n",
    "    case Ident (str) => { if (env.contains(str)){\n",
    "                                env(str)\n",
    "                            } else {\n",
    "        throw new IllegalArgumentException(s\"Environment does not contain mapping for $str\")\n",
    "    }\n",
    "                        }\n",
    "    case Plus(eList) => {\n",
    "        (eList map {evalExpr(_, env)}).sum\n",
    "    }\n",
    "    \n",
    "    case Minus(e, eList) => {\n",
    "        (evalExpr(e, env)) - ((eList map {evalExpr(_, env)}).sum )\n",
    "    }\n",
    "    \n",
    "    case Mult(eList) => {\n",
    "        (eList map {evalExpr(_, env)}).product\n",
    "    }\n",
    "    \n",
    "    case Div(e1, e2) => {\n",
    "        (evalExpr(e1, env)) / (evalExpr(e2, env))\n",
    "    }\n",
    "    \n",
    "    case Log(e) => math.log(evalExpr(e, env))\n",
    "    \n",
    "    \n",
    "    case Exp(e) => math.exp( evalExpr(e, env))\n",
    "    \n",
    "    case Sine(e) => math.sin( evalExpr(e, env))\n",
    "    \n",
    "    case Cosine(e) => math.cos(evalExpr(e, env))\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mf1\u001b[39m: \u001b[32mDouble\u001b[39m = \u001b[32m0.6816069937797158\u001b[39m"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val f1 = evalExpr(expr1, myEnvironment)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mf2\u001b[39m: \u001b[32mDouble\u001b[39m = \u001b[32m6.913043478260868\u001b[39m"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val f2 = evalExpr(expr2, myEnvironment)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\left(1.00 - \\left(\\sin\\left(x\\right)\\ \\sin\\left(x\\right)\\right) - \\left(\\cos\\left(x\\right)\\ \\cos\\left(x\\right)\\right)\\right)$"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36mexpr3\u001b[39m: \u001b[32mMinus\u001b[39m = Minus(Const(1.0),List(Mult(List(Sine(Ident(x)), Sine(Ident(x)))), Mult(List(Cosine(Ident(x)), Cosine(Ident(x))))))"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val expr3 = Minus(Const(1.0), List(\n",
    "    Mult(List(Sine(x), Sine(x))),\n",
    "    Mult(List(Cosine(x), Cosine(x)))\n",
    "))\n",
    "\n",
    "publish.latex(\"$\"+toLatex(expr3)+\"$\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mf3\u001b[39m: \u001b[32mDouble\u001b[39m = \u001b[32m0.0\u001b[39m"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val f3 = evalExpr(expr3, myEnvironment) // Should be 0.0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mf4\u001b[39m: \u001b[32mLog\u001b[39m = Log(Plus(List(Const(1.0), Mult(List(Const(2.0), Ident(y))))))\n",
       "\u001b[36menv\u001b[39m: \u001b[32mMap\u001b[39m[\u001b[32mString\u001b[39m, \u001b[32mDouble\u001b[39m] = \u001b[33mMap\u001b[39m(\u001b[32m\"y\"\u001b[39m -> \u001b[32m1.2\u001b[39m)"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val f4 = Log(Plus(List(Const(1.0), Mult(List(Const(2.0), Ident(\"y\"))))))\n",
    "val env = Map(\"y\" -> 1.2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mf5\u001b[39m: \u001b[32mDouble\u001b[39m = \u001b[32m1.2237754316221157\u001b[39m"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val f5 = evalExpr(f4,env )"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We learned how to implement some operations on our inductive data structures.\n",
    "Now we are ready in the next step to learn about how to write an interpreter and start adding features to the interpreter. But you may have already sensed something important: we have developed the bad habit of writing\n",
    "lots of code to carry out various operations and using the code as the definition. This works for simple operations which are easy for us to understand. For a more complex beast like a program, we will need a disciplined approach to understanding and writing down the workings of the program outside of code and in a way that can be analyzed by people. We will learn these as operational semantics in the coming lectures."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Scala",
   "language": "scala",
   "name": "scala"
  },
  "language_info": {
   "codemirror_mode": "text/x-scala",
   "file_extension": ".scala",
   "mimetype": "text/x-scala",
   "name": "scala",
   "nbconvert_exporter": "script",
   "version": "2.12.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}