map-reduce-filter.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Map, Filter and Fold (Reduce) Operations\n",
    "\n",
    "In many languages, the use of for-loops/while loops to iterate is replaced by operations on data structures such as `map`, `filter` and `fold`. In this lecture, we provide a brief overview with some examples. We show how many varieties of loops or equivalently recursion, can be systematically replaced by these operations.\n",
    "\n",
    "## Functions as First Class Objects in Scala\n",
    "\n",
    "The main idea behind functional programming is that `functions are first class objects`. What this means is that just like integers, strings, lists and other data, functions can be passed around. \n",
    "1. They can be used as arguments to other functions.\n",
    "2. Functions can be created from inside a function and returned as a value.\n",
    "3. You can have variables (vars) that can be assigned to functions.\n",
    "4. and many more ideas that we will revisit later...\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Idea 1: You can pass functions as arguments to other functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mcallTwice\u001b[39m"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def callTwice(f: Int => Int, arg: Int) = f(f(arg))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function `callTwice` takes in two arguments, `f` a function of type `Int => Int` and `arg` an argument of type `Int` \n",
    "\n",
    "- What does `Int => Int` mean? It annotates a function type in scala. I.e, a function that takes in an Int argument and returns an Int argument."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "27\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36maddOne\u001b[39m\n",
       "\u001b[36my\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m27\u001b[39m"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def addOne(x: Int) = x + 1\n",
    "val y = callTwice(addOne, 25)\n",
    "println(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mfactorialHelper\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36mfactorial\u001b[39m\n",
       "\u001b[36my\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m720\u001b[39m\n",
       "\u001b[36mz\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m-775946240\u001b[39m"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def factorialHelper(x: Int, acc:Int= 1): Int = \n",
    "    if (x <= 0) acc\n",
    "    else factorialHelper(x-1, acc*x)\n",
    "\n",
    "def factorial(x: Int): Int = factorialHelper(x, 1)\n",
    "\n",
    "val y = callTwice(factorial, 3)\n",
    "val z = callTwice(factorial, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mfilterList\u001b[39m\n",
       "defined \u001b[32mfunction\u001b[39m \u001b[36misOdd\u001b[39m\n",
       "\u001b[36mres12_2\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m1\u001b[39m, \u001b[32m3\u001b[39m, \u001b[32m15\u001b[39m, \u001b[32m19\u001b[39m, \u001b[32m13\u001b[39m, \u001b[32m19\u001b[39m)"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def filterList(l: List[Int], f: Int => Boolean): List[Int] = {\n",
    "    // f is a function from Int to Boolean\n",
    "    // l is a list\n",
    "    // make a new list of only those elements for which f returns true\n",
    "    var newList: List[Int] = List()\n",
    "    for (x <- l){\n",
    "        if (f(x)) \n",
    "            newList = newList ++ List(x) // Append x to the end\n",
    "    }\n",
    "    return newList\n",
    "}\n",
    "\n",
    "def isOdd(x: Int): Boolean = x %2 == 1\n",
    "filterList(List(1, 3, 12, 12, 15, 18, 19, 13, 20, 22, 19, 14), isOdd)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Idea 2: You can create and return a function from inside another function.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mbindSecondArgument\u001b[39m"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def bindSecondArgument(f: (Int, Int) => Int, arg2: Int ): (Int=> Int) = {\n",
    "    def g(x: Int): Int = f(x, arg2)\n",
    "    return g\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Function `bindSecondArgument` is quite interesting. It inputs two arguments: \n",
    "- f is a function from two integers to an integer and \n",
    "- arg2 is an integer\n",
    "We define a function `g` with argument `x` that calls `f(x, arg2)`\n",
    "The function `g` is returned by `bindSecondArgument`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mfoo\u001b[39m\n",
       "\u001b[36mtimesThree\u001b[39m: \u001b[32mInt\u001b[39m => \u001b[32mInt\u001b[39m = ammonite.$sess.cmd13$Helper$$Lambda$2615/1454492182@388feb9a\n",
       "\u001b[36mres18_2\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m12\u001b[39m"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def foo(x: Int, y: Int) = x * y\n",
    "\n",
    "val timesThree = bindSecondArgument(foo, 3) // You can use def here but val is also fine\n",
    "\n",
    "timesThree(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mconsecuteArguments\u001b[39m"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def consecuteArguments(f: (Int, Int, Int) => Int) : Int => Int = {\n",
    "    def g(x: Int) = f(x, x+1, x+2)\n",
    "    return g\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "210\n",
      "9240\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mtimes3\u001b[39m\n",
       "\u001b[36mg\u001b[39m: \u001b[32mInt\u001b[39m => \u001b[32mInt\u001b[39m = ammonite.$sess.cmd20$Helper$$Lambda$2662/1302964374@6e8b9af8"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def times3(x:Int, y: Int, z: Int) = x*y*z\n",
    "val g = consecuteArguments(times3)\n",
    "println(g(5))\n",
    "println(g(20))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Anonymous functions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mfoo\u001b[39m"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def foo(x: Int) = x + 10"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mfoo_anon\u001b[39m: \u001b[32mInt\u001b[39m => \u001b[32mInt\u001b[39m = ammonite.$sess.cmd28$Helper$$Lambda$2991/664546194@7729f897"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val foo_anon: Int => Int = ( x => x + 10 ) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mbar\u001b[39m"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def bar(x: Int, y: String) = x match {\n",
    "    case 0 => \"zero\"\n",
    "    case 1 => \"one\"\n",
    "    case _ => y + \"~~> \" + x\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mbar_anon\u001b[39m: (\u001b[32mInt\u001b[39m, \u001b[32mString\u001b[39m) => \u001b[32mString\u001b[39m = ammonite.$sess.cmd30$Helper$$Lambda$3028/1964167843@5b4156d8"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val bar_anon: (Int, String) => String = \n",
    "(x, y) => {\n",
    "    x match {\n",
    "        case 0 => \"zero\"\n",
    "        case 1 => \"one\"\n",
    "        case _ => y + \"~~> \" + x\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres31\u001b[39m: \u001b[32mString\u001b[39m = \u001b[32m\"hello~~> 10\"\u001b[39m"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bar(10, \"hello\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres32\u001b[39m: \u001b[32mString\u001b[39m = \u001b[32m\"hello~~> 10\"\u001b[39m"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bar_anon(10, \"hello\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres33_0\u001b[39m: \u001b[32mString\u001b[39m = \u001b[32m\"one\"\u001b[39m\n",
       "\u001b[36mres33_1\u001b[39m: \u001b[32mString\u001b[39m = \u001b[32m\"one\"\u001b[39m"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bar(1, \"hi\")\n",
    "bar_anon(1, \"hi\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Anonymous functions are useful inside code where they allow us to succinctly create new functions and pass them.\n",
    "Do not worry if the strange factorial function below seems somewhat less intuitive. We will learn all about this within a couple of weeks. It is written in a style called the \"Continuation Passing Style\".\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mstrange_factorial_fun\u001b[39m"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def strange_factorial_fun(x: Int, k: Int => Int): Int = {\n",
    "    if (x <= 0) k(1)\n",
    "    else\n",
    "        factorial_fun(x-1, v => { k(x*v) })\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "120"
     ]
    },
    {
     "data": {
      "text/plain": [
       "\u001b[36mres37_1\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m720\u001b[39m"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "println(factorial_fun(5, x => x))\n",
    "println(factorial_fun(6, x => x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One useful feature of an anonymous function is you can directly pattern match on the input argument."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mf\u001b[39m: \u001b[32mInt\u001b[39m => \u001b[32mString\u001b[39m = ammonite.$sess.cmd39$Helper$$Lambda$3078/161432483@47a7b026"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val f: Int => String = {\n",
    "    case 0 => \"zero\"\n",
    "    case 1 => \"one\"\n",
    "    case x if x >= 2 => x.toString\n",
    "    case x if x < 0 => \"minus: \" + x.toString\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres41_0\u001b[39m: \u001b[32mString\u001b[39m = \u001b[32m\"10\"\u001b[39m\n",
       "\u001b[36mres41_1\u001b[39m: \u001b[32mString\u001b[39m = \u001b[32m\"one\"\u001b[39m\n",
       "\u001b[36mres41_2\u001b[39m: \u001b[32mString\u001b[39m = \u001b[32m\"minus: -1\"\u001b[39m"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f(10)\n",
    "f(1)\n",
    "f(-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mtrait\u001b[39m \u001b[36mList\u001b[39m\n",
       "defined \u001b[32mobject\u001b[39m \u001b[36mNil\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mConsNum\u001b[39m\n",
       "defined \u001b[32mclass\u001b[39m \u001b[36mConsList\u001b[39m"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sealed trait List\n",
    "case object Nil extends List\n",
    "case class ConsNum(j: Int, l: List) extends List\n",
    "case class ConsList(l1: List, l2: List) extends List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mnestingDepthAnon\u001b[39m: \u001b[32mList\u001b[39m => \u001b[32mInt\u001b[39m = ammonite.$sess.cmd45$Helper$$Lambda$3342/746381704@65930c05"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val nestingDepthAnon: List => Int = {\n",
    "    case Nil => 0\n",
    "    case ConsNum(_, l) => nestingDepth(l)\n",
    "    case ConsList(l1, l2) => math.max(1+nestingDepth(l1), nestingDepth(l2))\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mnestingDepth\u001b[39m"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def nestingDepth(lst: List): Int= lst match {\n",
    "    case Nil => 0\n",
    "    case ConsNum(_, l) => nestingDepth(l)\n",
    "    case ConsList(l1, l2) => math.max(1+nestingDepth(l1), nestingDepth(l2))\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mnestingDepthAnonAlternative\u001b[39m: \u001b[32mList\u001b[39m => \u001b[32mInt\u001b[39m = ammonite.$sess.cmd48$Helper$$Lambda$3346/722366535@50b94457"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val nestingDepthAnonAlternative: List => Int = lst => {\n",
    "    lst match {\n",
    "    case Nil => 0\n",
    "    case ConsNum(_, l) => nestingDepth(l)\n",
    "    case ConsList(l1, l2) => math.max(1+nestingDepth(l1), nestingDepth(l2))\n",
    "}\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Map operation\n",
    "\n",
    "The idea of a map operation is to apply a function $f$ to every member of a container (eg., list, array, map, etc.) and return a new container.\n",
    "\n",
    "### Example 1\n",
    "\n",
    "We have a list `List(1, 3, 4, 5, 6, 110, 12, 2)`. We wish to compute the square of each element in the list and make a new list with the result."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mrecursivelySquareEachElt\u001b[39m"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def recursivelySquareEachElt(l: List[Int], acc: List[Int] ): List[Int] = {\n",
    "    if (l.length == 0)\n",
    "        acc.reverse\n",
    "    else\n",
    "        recursivelySquareEachElt(l.tail, (l.head*l.head)::acc)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres5\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m100\u001b[39m)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "recursivelySquareEachElt(List(10), List())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres6\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m1\u001b[39m, \u001b[32m9\u001b[39m, \u001b[32m16\u001b[39m, \u001b[32m25\u001b[39m, \u001b[32m36\u001b[39m, \u001b[32m12100\u001b[39m, \u001b[32m144\u001b[39m, \u001b[32m4\u001b[39m)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "recursivelySquareEachElt(List(1, 3, 4, 5, 6, 110, 12, 2), List())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using the map operator over lists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36msquareEachElt\u001b[39m"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def squareEachElt(l: List[Int]): List[Int] =  l.map( x => x*x ) \n",
    "// x => x * x is an anonymous function that squares its arguments."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres8\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m1\u001b[39m, \u001b[32m9\u001b[39m, \u001b[32m16\u001b[39m, \u001b[32m25\u001b[39m, \u001b[32m36\u001b[39m, \u001b[32m12100\u001b[39m, \u001b[32m144\u001b[39m, \u001b[32m4\u001b[39m)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "squareEachElt(List(1, 3, 4, 5, 6, 110, 12, 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`l.map(f)` says that apply the function `f` on each element of the list `f`.\n",
    "\n",
    "First of all, the elements of the lists must be some type `A`, let's say. \n",
    "Next, the function `f` must be of type `A => B`.\n",
    "\n",
    "Last but not least, `l.map(f)` applies `f` to every element in the list and returns a new list\n",
    "of type `B`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36msayHelloTo\u001b[39m"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def sayHelloTo(l: List[String]): List[String] = l.map( x => (\"Hello \"+ x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres11\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mString\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m\"Hello Cat\"\u001b[39m, \u001b[32m\"Hello Dog\"\u001b[39m, \u001b[32m\"Hello World\"\u001b[39m)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sayHelloTo(List(\"Cat\", \"Dog\", \"World\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sum up all squares of numbers from 1 to n \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36msumUpto\u001b[39m"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def sumUpto(n: Int)= ((1 to n).map(x => x * x)).sum\n",
    "// (1 to n) creates a range or squence (not a list) from 1 to n.\n",
    "// I can apply map on this to square each element.\n",
    "// Calling sum on the result sums it up.\n",
    "// Anonymous function x=> .x * x does the squaring."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres14_0\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m14\u001b[39m\n",
       "\u001b[36mres14_1\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m385\u001b[39m\n",
       "\u001b[36mres14_2\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m5525\u001b[39m"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sumUpto(3)\n",
    "sumUpto(10)\n",
    "sumUpto(25)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Filter Operation.\n",
    "\n",
    "Just like we have used map to apply a function to each element and make a new container, we use `filter` to remove all elements that do not satisfy a predicate.\n",
    "\n",
    "__Predicate__ A preducate is a funciton that takes in a value and returns true/false.\n",
    "\n",
    "`l.filter(c)` filters all those elements that do not satisfy the condition `c` from the list `l`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mremoveAllMultiplesOfThree\u001b[39m"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def retainAllMultiplesOfThree(l: List[Int]): List[Int] = {\n",
    "    l.filter( x => x%3 == 0 )\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres18\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m15\u001b[39m, \u001b[32m18\u001b[39m, \u001b[32m12\u001b[39m, \u001b[32m3\u001b[39m)"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "removeAllMultiplesOfThree(List(10, 15, 18, 12, 3, 1, 5, 7, 8, 14))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36msumOddSquares\u001b[39m"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// Sum up all odd squares from 1 to n\n",
    "def sumOddSquares(n : Int): Int = {\n",
    "    (1 to n).filter(x => x%2 == 1).map(x => x * x).sum\n",
    "    // (1 to n) Range of all numbers frmo 1 to n, not a List\n",
    "    // filter -- take away odd numbers. \n",
    "    // Map from x to x* x\n",
    "    // sum up the answer\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres21\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m165\u001b[39m"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sumOddSquares(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fold Operations\n",
    "\n",
    "Fold/reduce operations are useful to gather all data thus far during a computation. Take a list\n",
    "\n",
    "$$[l_1, l_2, \\ldots, l_n] $$.\n",
    "\n",
    "We wish to sum up the numbers in the list.\n",
    "This is achieved in a loop with accumulator.\n",
    "~~~\n",
    "acc = 0\n",
    "for each item in List\n",
    "   acc = acc + item\n",
    "return acc\n",
    "~~~\n",
    "\n",
    "We can also do it with fold left operator.\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36msumList\u001b[39m"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def sumList(l: List[Int]): Int = l.foldLeft (0) ((acc, x) => acc + x )\n",
    "// Fold left with initial value of accumulator = 0\n",
    "// Every time we have a new list element x and accumulator value acc, update acc by acc + x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\u001b[36mres25\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m55\u001b[39m"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sumList(List(1, 2, 3,4, 5, 6, 7, 8, 9, 10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The expression\n",
    "\n",
    "~~~\n",
    "l.foldLeft (initialValue) (function)\n",
    "~~~\n",
    "\n",
    "replaces the loop\n",
    "\n",
    "~~~\n",
    "var acc = initialValue // Start acc with initial value \n",
    "for elt in l \n",
    "    acc = function(acc, elt) // call function on acc as first arg and the list elt as second.\n",
    "return acc\n",
    "~~~"
   ]
  }
 ],
 "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
}