scala-chap-2-3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Functional Programming is the Best\n",
    "\n",
    "## Why are we here?\n",
    "\n",
    "Functional programming rocks! Everyone is doing it, and it gets cooler every year. \n",
    "\n",
    "## Anti-hype\n",
    "\n",
    "FP is not the be all, end all of it's certainly possible to write a terrible, ugly mess using FP. Your crappy app that no one uses is not going to be better if you rewrite it in Haskell. There's a lot more to programming than some cool ADT tricks and pattern matching. \n",
    "\n",
    "Also, this:\n",
    "\n",
    "![Lisp Comic](http://imgs.xkcd.com/comics/lisp.jpg)\n",
    "\n",
    "## Anti-anti hype\n",
    "\n",
    "Learning FP well will make you a better programmer! We have lots of cool stuff happening these days in FP. \n",
    "\n",
    "Some examples \n",
    "\n",
    "### Ramda \n",
    "* 10 times cooler than underscore\n",
    "* `R.reduce((x,y) => x + y, 0, [1,2,3])`\n",
    "* Note the pointfree style! Everything in Ramda is autocurrying, too\n",
    "* `var sum = R.reduce((x,y) => x + y, 0) // [x] => x`\n",
    "\n",
    "### React\n",
    "* Ideally, your entire UI is just a function of your original state, and the \"virtual DOM\" is a purely functional data type that is returned by your component functions and then diff'ed against the last iteration\n",
    "\n",
    "### Event Sourcing\n",
    "* Data structures (except for events) theoretically become purely functional\n",
    "* i.e., `BankAccount(List(AccountOpens(10), Withdrawal(5), Deposit(30), Withdrawal(20))).balance`\n",
    "\n",
    "### Scala\n",
    "* We're using a lot of Scala here!\n",
    "* But is it functional?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Getting some stuff going here to see if it all works"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mobject \u001b[36mHelloWorld\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "object HelloWorld {\n",
    "  def main(args: Array[String]): Unit = {\n",
    "    println(\"Hello, world!\")\n",
    "  }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hello, world!\n"
     ]
    },
    {
     "data": {
      "text/plain": []
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "HelloWorld.main(Array())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mobject \u001b[36mMyModule\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "object MyModule {\n",
    "  def abs(n: Int): Int = \n",
    "    if (n < 0) -n\n",
    "    else n\n",
    "\n",
    "  private def formatAbs(x: Int) = {\n",
    "    val msg = \"The absolute value of %d is %d\" \n",
    "    msg.format(x, abs(x))\n",
    "  }\n",
    "\n",
    "  def main(args: Array[String]): Unit = \n",
    "    println(formatAbs(-42))\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The absolute value of -42 is 42\n"
     ]
    },
    {
     "data": {
      "text/plain": []
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "MyModule.main(Array())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What does this annotation do?\n",
    "We can see an example of how the `@annotation.tailrec` works here -- the following more naïve implementation won't compile."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mfactorial\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def factorial(n: Int): Int = {\n",
    "    //@annotation.tailrec\n",
    "    def go(n : Int): Int = \n",
    "        if (n == 1) 1\n",
    "        else n * go(n -1)\n",
    "    go(n)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres18\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m120\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "factorial(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Fibonacci w/ Tail Recursion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mfib\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def fib(n: Int): Int = {\n",
    "    @annotation.tailrec\n",
    "    def go(nMinus2 : Int, nMinus1 : Int, n: Int, index: Int) : Int = \n",
    "        if (n == 0) 1\n",
    "        else if (n == 1) 1\n",
    "        else if (index > n) nMinus2 + nMinus1\n",
    "        else go(nMinus1, nMinus2 + nMinus1, n, index + 1)\n",
    "    go(1, 1, n, 3)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres20_0\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m1\u001b[0m\n",
       "\u001b[36mres20_1\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m1\u001b[0m\n",
       "\u001b[36mres20_2\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m2\u001b[0m\n",
       "\u001b[36mres20_3\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m3\u001b[0m\n",
       "\u001b[36mres20_4\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m5\u001b[0m\n",
       "\u001b[36mres20_5\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m8\u001b[0m\n",
       "\u001b[36mres20_6\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m13\u001b[0m\n",
       "\u001b[36mres20_7\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m377\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fib(0)\n",
    "fib(1)\n",
    "fib(2)\n",
    "fib(3)\n",
    "fib(4)\n",
    "fib(5)\n",
    "fib(6)\n",
    "fib(13)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36misSorted\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def isSorted[A](as: Array[A])(ordered: (A,A) => Boolean): Boolean ={\n",
    "    @annotation.tailrec\n",
    "    def loop(n: Int): Boolean =\n",
    "        if (n >= as.length - 1) true \n",
    "        else if (!ordered(as(n),as(n+1))) false \n",
    "        else loop(n + 1)\n",
    "    loop(0)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mtStrings1\u001b[0m: \u001b[32mArray\u001b[0m[\u001b[32mString\u001b[0m] = \u001b[33mArray\u001b[0m(\u001b[32m\"Bob\"\u001b[0m, \u001b[32m\"Jim\"\u001b[0m, \u001b[32m\"Carol\"\u001b[0m)\n",
       "\u001b[36mtStrings2\u001b[0m: \u001b[32mArray\u001b[0m[\u001b[32mString\u001b[0m] = \u001b[33mArray\u001b[0m(\u001b[32m\"Bob\"\u001b[0m, \u001b[32m\"Dole\"\u001b[0m, \u001b[32m\"Gore\"\u001b[0m)\n",
       "\u001b[36mtNums1\u001b[0m: \u001b[32mArray\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mArray\u001b[0m(\u001b[32m3\u001b[0m, \u001b[32m2\u001b[0m, \u001b[32m1\u001b[0m)\n",
       "\u001b[36mtNums2\u001b[0m: \u001b[32mArray\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mArray\u001b[0m(\u001b[32m1\u001b[0m, \u001b[32m2\u001b[0m, \u001b[32m3\u001b[0m)\n",
       "\u001b[36mres22_4\u001b[0m: \u001b[32mBoolean\u001b[0m = \u001b[32mfalse\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val tStrings1 = Array(\"Bob\",\"Jim\",\"Carol\")\n",
    "val tStrings2 = Array(\"Bob\",\"Dole\",\"Gore\")\n",
    "val tNums1 = Array(3, 2, 1)\n",
    "val tNums2 = Array(1, 2, 3)\n",
    "isSorted(tStrings1)(_ < _) // False\n",
    "/*\n",
    "isSorted(tStrings2, (x: String, y: String) => x < y) // True\n",
    "isSorted(tNums1, (x: Int, y: Int) => x < y) // False\n",
    "isSorted(tNums2, (x: Int, y: Int) => x < y) // True\n",
    "// Try with a different function\n",
    "isSorted(tNums2, (x: Int, y: Int) => x > y) // False\n",
    "// Sanity check some obvious ones\n",
    "isSorted(Array(), (x: Int, y: Int) => true) // True\n",
    "isSorted(Array(1), (x: Int, y: Int) => true) // True\n",
    "*/"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Curry, Uncurry, Compose"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mcurry\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def curry[A,B,C](f: (A, B) => C): A => (B => C) = \n",
    "    a => b => f(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mmyAdder\u001b[0m: (\u001b[32mInt\u001b[0m, \u001b[32mInt\u001b[0m) => \u001b[32mInt\u001b[0m = <function2>\n",
       "\u001b[36mres24_1\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m5\u001b[0m\n",
       "\u001b[36mcurriedAdder\u001b[0m: \u001b[32mInt\u001b[0m => \u001b[32mInt\u001b[0m => \u001b[32mInt\u001b[0m = <function1>\n",
       "\u001b[36mtwoAdder\u001b[0m: \u001b[32mInt\u001b[0m => \u001b[32mInt\u001b[0m = <function1>\n",
       "\u001b[36mres24_4\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m5\u001b[0m\n",
       "\u001b[36mres24_5\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m6\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val myAdder = (x: Int, y: Int) => x + y\n",
    "myAdder(2, 3) // 5\n",
    "val curriedAdder = curry(myAdder)\n",
    "val twoAdder = curriedAdder(2)\n",
    "twoAdder(3) // 5\n",
    "twoAdder(4) // 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36muncurry\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def uncurry[A,B,C](f: A => B => C): (A, B) => C = \n",
    "    (a, b) => f(a)(b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36muncurriedAdder\u001b[0m: (\u001b[32mInt\u001b[0m, \u001b[32mInt\u001b[0m) => \u001b[32mInt\u001b[0m = <function2>\n",
       "\u001b[36mres26_1\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m5\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val uncurriedAdder = uncurry(curriedAdder)\n",
    "uncurriedAdder(2, 3) // 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mcompose\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def compose[A,B,C](f: B => C, g: A => B) : A => C = \n",
    "    a => f(g(a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mfiveAdder\u001b[0m: \u001b[32mInt\u001b[0m => \u001b[32mInt\u001b[0m = <function1>\n",
       "\u001b[36mres28_1\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m8\u001b[0m\n",
       "\u001b[36mres28_2\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m20\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val fiveAdder = compose(twoAdder, curriedAdder(3))\n",
    "fiveAdder(3) // 8\n",
    "fiveAdder(15) // 20"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Functional Data Structures"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36msum\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mInt\u001b[0m] => \u001b[32mInt\u001b[0m = <function1>\n",
       "\u001b[36mx\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m3\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val sum = (x : List[Int]) => 0\n",
    "val x = List(1,2,3,4,5) match {\n",
    "    case x :: 2 :: 4 :: _ => x\n",
    "    case Nil => 42\n",
    "    case x :: y :: 3 :: 4 :: _ => x + y \n",
    "    case h :: t => h + sum(t)\n",
    "    case _ => 101\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mtail\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def tail[A](as : List[A]) : List[A] = as match {\n",
    "    case Nil => Nil\n",
    "    case a :: as => as\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres31_0\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m4\u001b[0m, \u001b[32m5\u001b[0m)\n",
       "\u001b[36mres31_1\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mNothing\u001b[0m] = \u001b[33mList\u001b[0m()"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "tail(List(3, 4, 5))\n",
    "tail(List())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36msetHead\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def setHead[A](newHead : A, as: List[A]) = as match {\n",
    "    case Nil => List(newHead)\n",
    "    case a :: as => newHead :: as\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres33\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m7\u001b[0m, \u001b[32m4\u001b[0m, \u001b[32m5\u001b[0m)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "setHead(7, List(3, 4, 5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mdrop\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def drop[A](l: List[A], n: Int): List[A] = l match {\n",
    "    case a :: as if n > 0 => drop(as, n - 1)\n",
    "    case _ => l\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres35_0\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m5\u001b[0m)\n",
       "\u001b[36mres35_1\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mNothing\u001b[0m] = \u001b[33mList\u001b[0m()\n",
       "\u001b[36mres35_2\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mList\u001b[0m()"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "drop(List(3, 4, 5), 2)\n",
    "drop(List(), 4)\n",
    "drop(List(3, 4, 5), 83)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mdropWhile\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def dropWhile[A](l: List[A], f: A => Boolean): List[A] = l match {\n",
    "    case a :: as if (f(a)) => dropWhile(as, f)\n",
    "    case _ => l\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres37\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m6\u001b[0m, \u001b[32m7\u001b[0m, \u001b[32m8\u001b[0m, \u001b[32m9\u001b[0m, \u001b[32m10\u001b[0m)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "dropWhile(List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10),(x : Int) => x <= 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36minit\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def init[A](l: List[A]): List[A] = l match {\n",
    "    case _ :: Nil => Nil\n",
    "    case a :: as => a :: init(as)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres39_0\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m1\u001b[0m, \u001b[32m2\u001b[0m, \u001b[32m3\u001b[0m)\n",
       "\u001b[36mres39_1\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m1\u001b[0m)\n",
       "\u001b[36mres39_2\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mList\u001b[0m()"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "init(List(1, 2, 3, 4))\n",
    "init(List(1, 2))\n",
    "init(List(1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Folding"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mfoldRight\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def foldRight[A,B](as: List[A], z: B)(f: (A, B) => B): B =\n",
    " as match {\n",
    "    case Nil => z\n",
    "    case x :: xs => f(x, foldRight(xs, z)(f))\n",
    " }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres41\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m1\u001b[0m, \u001b[32m2\u001b[0m, \u001b[32m3\u001b[0m)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "foldRight(List(1, 2, 3), Nil:List[Int])(_::_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mproduct\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def product(ns: List[Double]) =\n",
    "    foldRight(ns, 1.0)(_*_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres43\u001b[0m: \u001b[32mDouble\u001b[0m = \u001b[32m6.0\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "product(List(1, 2, 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mlength\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def length[A](as: List[A]): Int = \n",
    "    foldRight(as, 0)((_, y) => y + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres45\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m4\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "length(List(1, 2, 3, 3932))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mfoldLeft\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def foldLeft[A,B](as: List[A], z: B)(f: (B, A) => B): B = as match {\n",
    "    case Nil => z\n",
    "    case a :: as => foldLeft(as, f(z, a))(f)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres47\u001b[0m: \u001b[32mDouble\u001b[0m = \u001b[32m6.0\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "foldLeft(List(1, 2, 3), 1.0)(_*_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mreverse\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def reverse[A](as: List[A]) : List[A] = {\n",
    "    val switch = (as : List[A], el : A) => el :: as\n",
    "    foldLeft(as, List[A]())(switch)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres49\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m3\u001b[0m, \u001b[32m2\u001b[0m, \u001b[32m1\u001b[0m)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "reverse(List(1,2,3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mcoolFoldRight\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def coolFoldRight[A,B](as: List[A], z: B)(f: (A, B) => B): B = {\n",
    "    foldLeft(reverse(as), z)((a, b) => f(b,a))\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mappend\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def append[A](as: List[A], bs: List[A]) : List[A] = {\n",
    "    coolFoldRight(as, bs)(_::_)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres52\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m1\u001b[0m, \u001b[32m2\u001b[0m, \u001b[32m3\u001b[0m, \u001b[32m4\u001b[0m, \u001b[32m5\u001b[0m, \u001b[32m6\u001b[0m)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "append(List(1,2,3),List(4, 5, 6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mconcatenate\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def concatenate[A](l : List[List[A]]) : List[A] = {\n",
    "    foldLeft(l, List[A]())(append)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres54\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m1\u001b[0m, \u001b[32m2\u001b[0m, \u001b[32m3\u001b[0m, \u001b[32m4\u001b[0m, \u001b[32m5\u001b[0m, \u001b[32m6\u001b[0m, \u001b[32m7\u001b[0m, \u001b[32m8\u001b[0m, \u001b[32m9\u001b[0m)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "concatenate(List(List(1, 2, 3), List(4,5,6), List(7,8,9)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## More functions for lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36maddOneToAll\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def addOneToAll(xs : List[Int]) : List[Int] = xs match {\n",
    "    case Nil => Nil\n",
    "    case x :: xs => x + 1 :: addOneToAll(xs)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres56\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m2\u001b[0m, \u001b[32m3\u001b[0m, \u001b[32m4\u001b[0m)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "addOneToAll(List(1,2,3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mallDoublesToString\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def allDoublesToString(xs: List[Double]) : List[String] = xs match {\n",
    "    case Nil => Nil\n",
    "    case x :: xs => x.toString() :: allDoublesToString(xs)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres58\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mString\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m\"3.3\"\u001b[0m, \u001b[32m\"3.2\"\u001b[0m, \u001b[32m\"4.2\"\u001b[0m)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "allDoublesToString(List(3.3, 3.2, 4.2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mmap\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def map[A,B](as: List[A])(f: A => B): List[B] = as match {\n",
    "    case Nil => Nil\n",
    "    case x :: xs => f(x) :: map(xs)(f)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres60\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m2\u001b[0m, \u001b[32m3\u001b[0m, \u001b[32m4\u001b[0m)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "map(List(1,2,3))(_+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mfilter\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def filter[A](as: List[A])(f: A => Boolean): List[A] = as match {\n",
    "    case Nil => Nil\n",
    "    case x :: xs if f(x) => x :: filter(xs)(f)\n",
    "    case x :: xs => filter(xs)(f)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres62\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m2\u001b[0m, \u001b[32m4\u001b[0m, \u001b[32m6\u001b[0m, \u001b[32m8\u001b[0m)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "filter(List(1,2,3,4,5,6,7,8,9))(_ % 2 == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mflatMap\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def flatMap[A,B](as: List[A])(f: A => List[B]): List[B] = as match {\n",
    "    case Nil => Nil\n",
    "    case x :: xs => append(f(x), flatMap(xs)(f))\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres64\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m1\u001b[0m, \u001b[32m1\u001b[0m, \u001b[32m2\u001b[0m, \u001b[32m2\u001b[0m, \u001b[32m3\u001b[0m, \u001b[32m3\u001b[0m)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "flatMap(List(1,2,3))(i => List(i,i))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mfilterFlatMap\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def filterFlatMap[A](as: List[A])(f: A => Boolean): List[A] = {\n",
    "    val filterFunc = (x : A) => if (f(x)) List(x) else List[A]()\n",
    "    flatMap(as)(filterFunc)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres66\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m2\u001b[0m, \u001b[32m4\u001b[0m, \u001b[32m6\u001b[0m, \u001b[32m8\u001b[0m)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "filterFlatMap(List(1,2,3,4,5,6,7,8,9))(_ % 2 == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36maddTwoLists\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def addTwoLists(xs : List[Int], ys : List[Int]) : List[Int] = (xs,ys) match {\n",
    "    case (Nil, Nil) => Nil\n",
    "    case (x :: xs, y :: ys) => x + y :: addTwoLists(xs, ys)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres68\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m5\u001b[0m, \u001b[32m7\u001b[0m, \u001b[32m9\u001b[0m)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "addTwoLists(List(1,2,3),List(4,5,6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mzipWith\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def zipWith[A,B,C](xs : List[A], ys : List[B])(f: (A,B) => C) : List[C] = (xs,ys) match {\n",
    "    case (Nil, Nil) => Nil\n",
    "    case (x :: xs, y :: ys) => f(x,y) :: zipWith(xs, ys)(f)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres70\u001b[0m: \u001b[32mList\u001b[0m[\u001b[32mInt\u001b[0m] = \u001b[33mList\u001b[0m(\u001b[32m5\u001b[0m, \u001b[32m7\u001b[0m, \u001b[32m9\u001b[0m)"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "zipWith(List(1,2,3),List(4,5,6))(_+_)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mhasSubsequence\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean = (sup, sub) match {\n",
    "    case (_, Nil) => true\n",
    "    case (Nil, sub) => false\n",
    "    case (x :: sup, y :: sub) if (x == y) => hasSubsequence(sup, sub)\n",
    "    case (x :: sup, y :: sub) => hasSubsequence(sup, y :: sub)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres72_0\u001b[0m: \u001b[32mBoolean\u001b[0m = \u001b[32mtrue\u001b[0m\n",
       "\u001b[36mres72_1\u001b[0m: \u001b[32mBoolean\u001b[0m = \u001b[32mfalse\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "hasSubsequence(List(1,2,3,4), List(3,4))\n",
    "hasSubsequence(List(1,2,3,4), List(4,3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Trees"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mtrait \u001b[36mTree\u001b[0m\n",
       "defined \u001b[32mclass \u001b[36mLeaf\u001b[0m\n",
       "defined \u001b[32mclass \u001b[36mBranch\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "sealed trait Tree[+A]\n",
    "case class Leaf[A](value: A) extends Tree[A]\n",
    "case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mmyTree\u001b[0m: \u001b[32mBranch\u001b[0m[\u001b[32mString\u001b[0m] = Branch(Branch(Leaf(A),Leaf(B)),Branch(Leaf(C),Leaf(D)))"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val myTree = Branch(Branch(Leaf(\"A\"), Leaf(\"B\")), Branch(Leaf(\"C\"), Leaf(\"D\")))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36msize\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def size[A](t : Tree[A]) : Int = t match {\n",
    "   case Leaf(_) => 1\n",
    "   case Branch(left, right) => 1 + size(left) + size(right)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres76\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m7\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "size(myTree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mintTree\u001b[0m: \u001b[32mBranch\u001b[0m[\u001b[32mInt\u001b[0m] = Branch(Branch(Leaf(1),Leaf(2)),Branch(Branch(Leaf(5),Leaf(7)),Leaf(6)))"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "val intTree = Branch(Branch(Leaf(1), Leaf(2)), Branch(Branch(Leaf(5),Leaf(7)), Leaf(6)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mmaximum\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def maximum(t : Tree[Int]) : Int = t match {\n",
    "    case Leaf(x) => x\n",
    "    case Branch(left, right) => maximum(left) max maximum(right)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres79\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m7\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "maximum(intTree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mdepth\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def depth[A](t : Tree[A]) : Int = t match {\n",
    "    case Leaf(_) => 1\n",
    "    case Branch(left, right) => 1 + (depth(left) max depth(right))\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres81\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m4\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "depth(intTree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mtreeMap\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def treeMap[A,B](t : Tree[A])(f: A => B) : Tree[B] = t match {\n",
    "    case Leaf(x) => Leaf(f(x))\n",
    "    case Branch(left, right) => Branch(treeMap(left)(f), treeMap(right)(f))\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres83\u001b[0m: \u001b[32mTree\u001b[0m[\u001b[32mInt\u001b[0m] = Branch(Branch(Leaf(2),Leaf(3)),Branch(Branch(Leaf(6),Leaf(8)),Leaf(7)))"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "treeMap(intTree)(_+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mfold\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def fold[A,B](t : Tree[A])(leafF : A => B)(branchF : (B,B) => B) : B = t match {\n",
    "    case Leaf(x) => leafF(x)\n",
    "    case Branch(left, right) => branchF(fold(left)(leafF)(branchF), fold(right)(leafF)(branchF))\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mfsize\u001b[0m\n",
       "\u001b[36mres85_1\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m7\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def fsize[A](t : Tree[A]) : Int = \n",
    "   fold(t)(x => 1)(_ + _ + 1)\n",
    "fsize(myTree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction \u001b[36mfmaximum\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def fmaximum(t : Tree[Int]) : Int = \n",
    "    fold(t)(x => x)(_ max _)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres87\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m7\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fmaximum(intTree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[31mMain.scala:27: missing parameter type for expanded function ((x$1, x$2) => x$1.max(x$2))",
      "    fold(t)(x => 1)((_ max _) + 1)",
      "                     ^\u001b[0m",
      "\u001b[31mMain.scala:27: missing parameter type for expanded function ((x$1: <error>, x$2) => x$1.max(x$2))",
      "    fold(t)(x => 1)((_ max _) + 1)",
      "                           ^\u001b[0m"
     ]
    }
   ],
   "source": [
    "def fdepth[A](t : Tree[A]) : Int = \n",
    "    fold(t)(x => 1)((_ max _) + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres89\u001b[0m: \u001b[32mInt\u001b[0m = \u001b[32m3\u001b[0m"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fdepth(intTree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Scala 2.11",
   "language": "scala211",
   "name": "scala211"
  },
  "language_info": {
   "codemirror_mode": "text/x-scala",
   "file_extension": ".scala",
   "mimetype": "text/x-scala",
   "name": "scala211",
   "pygments_lexer": "scala",
   "version": "2.11.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}