lectures/05-folds-collections.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "import annotation.tailrec"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Scala- Folds\n",
    "=========\n",
    "\n",
    "##### Vassil Dichev\n",
    "\n",
    "23.03.2022"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Type parameters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "@tailrec\n",
    "def map(l: List[Int], f: Int => Int, acc: List[Int] = Nil): List[Int] =\n",
    "  if (l.isEmpty) acc.reverse\n",
    "  else map(l.tail, f, l.head :: acc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "cmd36.sc:4: type mismatch;\n",
      " found   : rassoc$1.type (with underlying type A)\n",
      " required: B\n",
      "  else map(l.tail, f, l.head :: acc)\n",
      "                        ^Compilation Failed"
     ]
    },
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "Compilation Failed"
     ]
    }
   ],
   "source": [
    "@tailrec\n",
    "def map[A,B](l: List[A], f: A => B, acc: List[B] = Nil): List[B] =\n",
    "  if (l.isEmpty) acc.reverse\n",
    "  else map(l.tail, f, l.head :: acc)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# reduce\n",
    "![image](images/reduce.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Folding right or left\n",
    "![image](images/Right-fold-transformation.png)\n",
    "\n",
    "![image](images/Left-fold-transformation.png)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mmap\u001b[39m\n",
       "\u001b[36mres37_1\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m2\u001b[39m, \u001b[32m4\u001b[39m, \u001b[32m6\u001b[39m)"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def map[A,B](l: List[A])(f: A => B): List[B] = l.foldRight(List.empty[B]){(x, acc) => f(x) :: acc}\n",
    "map(List(1, 2, 3))(_ * 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def map[A,B](l: List[A])(f: A => B): List[B] =\n",
    "  l.foldRight(List.empty[B]) {\n",
    "    (x, l) => f(x) :: l\n",
    "  }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mfilter\u001b[39m\n",
       "\u001b[36mres40_1\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m2\u001b[39m, \u001b[32m4\u001b[39m)\n",
       "\u001b[36mres40_2\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m()"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def filter[A](l: List[A])(f: A => Boolean): List[A] = l.foldRight(List.empty[A]){(x, acc) => if (f(x)) x :: acc else acc}\n",
    "filter(List(2, 3, 4))(_ % 2 == 0)\n",
    "filter(List.empty[Int])(_ % 2 == 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def filter[A](l: List[A])(f: A => Boolean): List[A] =\n",
    "  l.foldRight(List.empty[A]) {\n",
    "    (x, l) => if (f(x)) x :: l else l\n",
    "  }"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Exercise: implementing in terms of foldXXX\n",
    "1. We'll guess the function from the signature\n",
    "2. We'll let the signature guide the implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "\n",
    "def f1[A](l: List[A]): Int = ???"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36msize\u001b[39m\n",
       "\u001b[36mres44_1\u001b[39m: \u001b[32mInt\u001b[39m = \u001b[32m3\u001b[39m"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def size[A](l: List[A]): Int = l.foldLeft(0) {(acc, _) => acc + 1 }\n",
    "size(List(1, 2, 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def size[A](l: List[A]) = l.foldLeft(0)((acc, _) => 1 + acc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def f2(l: List[Int]): Int = ???"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "ename": "",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[31mjava.lang.UnsupportedOperationException: empty.reduceLeft\u001b[39m\n  scala.collection.IterableOnceOps.reduceLeft(\u001b[32mIterableOnce.scala\u001b[39m:\u001b[32m721\u001b[39m)\n  scala.collection.IterableOnceOps.reduceLeft$(\u001b[32mIterableOnce.scala\u001b[39m:\u001b[32m718\u001b[39m)\n  scala.collection.AbstractIterable.reduceLeft(\u001b[32mIterable.scala\u001b[39m:\u001b[32m921\u001b[39m)\n  ammonite.$sess.cmd48$Helper.max(\u001b[32mcmd48.sc\u001b[39m:\u001b[32m1\u001b[39m)\n  ammonite.$sess.cmd48$Helper.<init>(\u001b[32mcmd48.sc\u001b[39m:\u001b[32m2\u001b[39m)\n  ammonite.$sess.cmd48$.<clinit>(\u001b[32mcmd48.sc\u001b[39m:\u001b[32m7\u001b[39m)"
     ]
    }
   ],
   "source": [
    "def max(l: List[Int]): Int = l.reduceLeft(math.max)\n",
    "max(Nil)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def max(l: List[Int]) = l reduce math.max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def f3[A](l: List[A]): List[A] = ???"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mreverse\u001b[39m\n",
       "\u001b[36mres51_1\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m3\u001b[39m, \u001b[32m2\u001b[39m, \u001b[32m1\u001b[39m)"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def reverse[A](l: List[A]): List[A] = l.foldLeft(List.empty[A])((acc, x) => x :: acc)\n",
    "reverse(List(1, 2, 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def reverse[A](l: List[A]) = l.foldLeft(List.empty[A])((acc, x) => x :: acc)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# reverse\n",
    "![image](images/animation-reverse.gif)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def f4[A](l1: List[A], l2: List[A]): List[A] = ???"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "defined \u001b[32mfunction\u001b[39m \u001b[36mconcat\u001b[39m\n",
       "\u001b[36mres55_1\u001b[39m: \u001b[32mList\u001b[39m[\u001b[32mInt\u001b[39m] = \u001b[33mList\u001b[39m(\u001b[32m1\u001b[39m, \u001b[32m5\u001b[39m, \u001b[32m3\u001b[39m, \u001b[32m4\u001b[39m, \u001b[32m2\u001b[39m, \u001b[32m6\u001b[39m)"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def concat[A](l1: List[A], l2: List[A]): List[A] = l1.foldRight(l2){ _ :: _ }\n",
    "concat(List(1, 5, 3), List(4, 2, 6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def concat[A](l1: List[A], l2: List[A]) = l1.foldRight(l2) { _ :: _ }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def f5[A](l: List[A], x: A): Boolean = ???"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def contains[A](l: List[A], el: A): Boolean = ???"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def contains[A](l: List[A], el: A) = l.foldLeft(false)((acc, x) => x == el || acc)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Lazy\n",
    "![image](images/work.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#  Fold and laziness\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def forall[A](l: List[A])(f: A => Boolean): Boolean = ???"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#  Fold and laziness\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def forall[A](l: List[A])(f: A => Boolean): Boolean =\n",
    "  l.foldLeft(true) { (acc, x) => f(x) && acc }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def forall[A](l: List[A])(f: A => Boolean): Boolean = {\n",
    "  l.foldLeft(true) { (acc, x) =>\n",
    "    println(\"Executing for \" + x)\n",
    "    f(x) && acc\n",
    "  }\n",
    "}\n",
    "\n",
    "forall(List.range(1, 5))(_ % 2 == 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#  forall/exists\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def exists[A](l: List[A])(f: A => Boolean): Boolean = ???"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#  forall/exists\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def exists[A](l: List[A])(f: A => Boolean): Boolean =\n",
    "  !forall(l)(!f(_))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Case study: side effects\n",
    "\n",
    "## Migration of Scalaz to Cats"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Scalaz' implementation:\n",
    "```\n",
    "l.reverse.foldLeft(...) {...}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "### Cats' implementation:\n",
    "```\n",
    "l.foldRight(...) {...}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Scala- Collections\n",
    "=========\n",
    "\n",
    "##### Vassil Dichev\n",
    "\n",
    "31.03.2021"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Recap\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "## What is the type of a function?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "## How do partially applied and curried functions compare?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "## How are multiple parameter lists and currying related?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "## What is the difference between a function and its tupled version?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Collections\n",
    "![image](images/collections-diagram-213.svg)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#  Design tips\n",
    "\n",
    "* Prefer `var` of immutable to `val` of mutable\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "var map = Map.empty[Int,String]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "val map = collection.mutable.Map.empty[Int,String]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Collections are functions\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "val dict = Map(1 -> \"one\", 2 -> \"two\")\n",
    "List(1, 2) map dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "val arr = Array(5, 3, 4)\n",
    "List(2, 1) map arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "val set = Set(1, 3, 5, 8)\n",
    "(1 to 10) map set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Uniform return type principle\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "arr map (_ + 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "dict map (t => t._1.toString -> t._2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "import Function.tupled\n",
    "dict map tupled(_.toString -> _)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "dict.mapValues(\"<\" + _ + \">\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "set map (_ / 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Partial functions\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "val reciprocal = new PartialFunction[Int,Double] {\n",
    "  override def isDefinedAt(x: Int) = x != 0\n",
    "  override def apply(x: Int) =\n",
    "    if (isDefinedAt(x)) 1.toDouble / x\n",
    "    else throw new MatchError(\"Division by zero\")\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "val reciprocal: PartialFunction[Int,Double] = {\n",
    "  case x if x != 0 => 1.toDouble / x\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Tuples\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "val t1: (Int, String) = (1, \"hi\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "val t2: Tuple2[Int,String] = Tuple2(1, \"hi\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "val t3 = 1 -> \"hi\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "val a = t1._1\n",
    "val b = t3._2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Tuple2\n",
    "\n",
    "-   `partition`- combines `filter`/`filterNot`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "-   `span`- combines `takeWhile`/`dropWhile`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "-   `splitAt`- combines `take`/`drop`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Functions\n",
    "\n",
    "-   `flatten`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "-   `flatMap`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "-   `groupBy`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "-   `zip`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# flatten/flatMap\n",
    "\n",
    "Generate all combinations of numbers\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "val s = \"abcd\"\n",
    "val prefixes = s.inits.toList\n",
    "val suffixes = s.tails.toList"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "val lol = prefixes.map(_.tails.toList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lol.flatten"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "prefixes.flatMap(_.tails)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "lol.flatMap(identity) == lol.flatten"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "val list = List(1, 2, 3)\n",
    "for {\n",
    "  i <- list\n",
    "  if i % 2 == 0\n",
    "  c <- 'a' to 'c'\n",
    "} yield s\"$i$c\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "val list = List(1, 2, 3)\n",
    "\n",
    "list.filter(i => i % 2 != 0).flatMap(i => ('a' to 'c').map(c => s\"$i$c\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Syntax sugar\n",
    "![image](images/godji-opakovka2.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Merging maps\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "val eng = Map(1 -> \"one\", 2 -> \"two\")\n",
    "val ger = Map(1 -> \"eins\", 3 -> \"drei\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "List(eng, ger).flatten.groupBy(_._1).mapValues(_.map(_._2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Zip\n",
    "![image](images/zipper.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Exercise\n",
    "\n",
    "Find the differences between consecutive numbers\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "val l = List(1, 3, 8, 11, 15, 17, 24, 27, 32)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "(l zip l.tail)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 0,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "(l.tail zip l) map tupled(_ - _)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Laziness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "> I'm not lazy, I'm just on energy-saving mode.\n",
    ">\n",
    "> **Anonymous**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* non-strict: arguments are evaluated on demand\n",
    "* lazy: evaluation is memoized"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def doubleView(s: Seq[Int]) =\n",
    "  s.view.map{ x => println(\"Calculating \" + x); x * 2 }\n",
    "{{\n",
    "  val longRange = 1 to 10000\n",
    "  val view = doubleView(longRange).take(10)\n",
    "  println(view.toList)\n",
    "  println(view.toList)\n",
    "}}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def doubleLazyList(s: Seq[Int]) =\n",
    "  s.to(LazyList).map{ x => println(\"Calculating \" + x); x * 2 }\n",
    "{{\n",
    "  val longRange = 1 to 10000\n",
    "  val stream = doubleLazyList(longRange).take(10)\n",
    "  println(stream.toList)\n",
    "  println(stream.toList)\n",
    "}}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "{{\n",
    "  lazy val fibs: LazyList[Int] = 0 #:: 1 #:: fibs.zip(fibs.tail).map(n => n._1 + n._2 )\n",
    "  fibs.take(5)\n",
    "}}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Let's implement a Lazy List!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "trait LazyIntList {\n",
    "  def head: Int\n",
    "  def tail: LazyIntList\n",
    "}\n",
    "case object Nil extends LazyIntList {\n",
    "  def head = throw new NoSuchElementException\n",
    "  def tail = throw new UnsupportedOperationException\n",
    "}\n",
    "case class LazyCons(head: Int, tail: LazyIntList) extends LazyIntList\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "trait LazyIntList {\n",
    "  def head: Int\n",
    "  def tail: LazyIntList\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "object LazyNil extends LazyIntList {\n",
    "  def head = throw new NoSuchElementException\n",
    "  def tail = throw new UnsupportedOperationException\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "class LazyCons(h: => Int, t: => LazyIntList) extends LazyIntList {\n",
    "  lazy val head = h\n",
    "  lazy val tail = t\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def from(start: Int, step: Int = 1): LazyIntList = new LazyCons(start, from(start + step, step))\n",
    "val naturalNumbers = from(0)"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "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.13.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}