{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Assignment on Programming Techniques for Big Data\n",
    "\n",
    "## Yoshi van den Akker and Georgios Gousios\n",
    "\n",
    "Functional programming is the basis of most modern Big Data processing systems.\n",
    "Before going forward to the course, it is important to master data processing\n",
    "techniques using a functional programming style. In this assignment, your task \n",
    "is to train yourselves in thinking in a functional way when processing data. \n",
    "\n",
    "Many of the the tasks below are easy, but some are not and require many\n",
    "iterations (and extensive testing!) to get right. For some of them, you\n",
    "can find ready-made solutions on the internet. Even though it may be tempting,\n",
    "we advise you against copying and pasting them here, as you will regret it\n",
    "later on in the course.\n",
    "[Wax on, wax off!](https://www.youtube.com/watch?v=fULNUr0rvEc)\n",
    "\n",
    "\n",
    "This assignment has a total of *115* points. Your grade is calculated with `min(points/11, 10)`, i.e. you need 110 points for a 10.\n",
    "\n",
    "A few notes:\n",
    "* For each function you define, you also need to define at least one working example.\n",
    "* Do not change the given function signatures, otherwise automated tests will fail.\n",
    "* The tests will run every cell. Make sure no errors occur by testing this via Cell -> Run All.\n",
    "* The tests will call every function we ask you to implement. If you are skipping a question, make sure it still compiles. The way we provided this notebook works.\n",
    "* Use functional programming for every question (besides the first section)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Foundation of functional programming\n",
    "\n",
    "In this part you will implement core functions that are vital to functional programming."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**T** (5pts): Implement `map` using iteration for lists/arrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def map[A,B](func: (A => B), xs: List[A]): List[B] = {\n",
    "    return null\n",
    "}\n",
    "\n",
    "map((x:Int) => x*2, List.range(0,10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**T** (5pts): Implement `filter` using iteration for lists/arrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def filter[A](func: (A => Boolean), xs: List[A]): List[A] = {\n",
    "    return null\n",
    "}\n",
    "\n",
    "filter((x: Int) => (x % 2 == 0), List.range(0, 10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**T** (5pts): Implement `reduceR` using iteration for lists/arrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reduceR[A, B]( f : (A,B) => B, list: List[A], init: B) : B = {\n",
    "    return init\n",
    "}\n",
    "\n",
    "reduceR((x: Int, y: Int) => x-y, List.range(0, 7), 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**T** (5pts): Implement a function `flatten(xs: [[A]]): [A]` that converts a list of \n",
    "lists into a list formed by the elements of these lists. For example:\n",
    "\n",
    "```scala\n",
    ">>> a = List(List(1,2,3),List(4,5), List(6), List(7,List(8,9)))\n",
    ">>> flatten(a)\n",
    "List(1, 2, 3, 4, 5, 6, 7, List(8, 9))\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def flatten[A](xs: List[List[A]]): List[A] = {\n",
    "    return null\n",
    "}\n",
    "\n",
    "\n",
    "flatten(List(List(1,2,3),List(4,5), List(6), List(7,List(8,9))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## More basic functions\n",
    "\n",
    "In every implementation from now (also in next steps)on you should reuse at least one of your answers to an earlier question."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**T** (5pts): Implement `reduceL` by reusing `reduceR`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reduceL[A, B](func: (B, A) => B, xs: List[A], init: B): B = {\n",
    "    return init\n",
    "}\n",
    "\n",
    "reduceL((x: Int, y: Int) => x-y, List.range(0,7), 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**T** (10pts): Implement `group_by` by reusing `reduceL`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def group_by[A,B](theKeyFunction : (A) => B, xs: List[A]) : Map[B, List[A]] = {\n",
    "    return null\n",
    "}\n",
    "\n",
    "group_by((x: Int) => if (x % 2 == 0) \"even\" else \"odd\", List.range(0,10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Simple data processing\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**T** (5pts): Implement `distinct` using `reduceL`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def distinct[A](xs: List[A]): List[A] = {\n",
    "    return null\n",
    "}\n",
    "\n",
    "val a = List(1,2,3,1,2,3,4,5,6,5,4,3,2,1)\n",
    "distinct(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**T** (5pts): Implement `flatmap`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def flatmap[A,B](func: A => List[B], xs: List[A]): List[B] = {\n",
    "    return null\n",
    "}\n",
    "\n",
    "flatmap((x: Int) => List.range(0,x), List.range(0,5))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**T** (5pts): Implement `max(xs: [Integer]): Integer` that finds the largest value in `xs`. You can assume the list is non-empty."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def max(xs: List[Int]): Int = {\n",
    "    return 0\n",
    "}\n",
    "\n",
    "max(List(1,59,42,27,38))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Higher-order functions\n",
    "\n",
    "\n",
    "**T** (10pts): Implement a function called `drop_while(f: A -> Boolean, xs: [A]) : [A]` \n",
    "that drops the longest prefix of elements from `xs` that satisfy `f`.\n",
    "\n",
    "```scala\n",
    ">>> a = List(1,2,3,4,3,2,1)\n",
    ">>> dropWhile((x: Int) => x <= 3, a)\n",
    "List(4,3,2,1)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def drop_while[A](func: A => Boolean, xs: List[A]): List[A] = {\n",
    "    return null\n",
    "}\n",
    "\n",
    "drop_while((x: Int) => x <= 3, List(1,2,1,3,5,3,1,4,1,5,6))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**T** (10pts): Implement a function `zip(xs: [A], ys: [B]): List[(A,B)]` that returns a list formed from this list and another list by combining the corresponding elements in pairs. If one of the two lists is longer \n",
    "than the other, its remaining elements are ignored. \n",
    "\n",
    "```scala\n",
    ">>> a = List(1,2,3,4)\n",
    ">>> b = List(a,b,c,d,e)\n",
    ">>> zip(a,b)\n",
    "List((1,a),(2,b),(3,c), (4, d)]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def zip[A,B](list1: List[A], list2: List[B]) : List[(A, B)] = {\n",
    "    return null\n",
    "}\n",
    "\n",
    "val list1 = List(1, 2, 3, 4, 5, 6, 7)\n",
    "val list2 = List('a', 'b', 'c', 'd')\n",
    "zip(list1, list2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**T** (10pts): Implement a function \n",
    "`scanL(f: (acc: B, x: A) -> B, xs: [A], init: B) -> [B]`\n",
    "that works like `reduceL` but instead of producing one final result, it also\n",
    "returns all the intermediate results.\n",
    "\n",
    "```scala\n",
    ">>> a = List(2,3,4)\n",
    ">>> scanL((x: Int, y: Int) => x + y, a, 0)\n",
    "List(0, 2, 5, 9)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def scanL[A,B](f: (B, A) => B, xs : List[A], init: B) : List[B] = {\n",
    "    return null\n",
    "}\n",
    "    \n",
    "scanL((x: Int, y: Int) => x + y, List(2,3,4), 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Real life application\n",
    "\n",
    "In the following questions you will solve realistic problems with the techniques you learned in this assignment. You will be working with data of San Francisco Library patrons. You can find the data file [here](https://drive.google.com/open?id=1sYTB_gR4Ig0Aww9QBN9wRdaLWVdBVD62). Below you can find what each field means.\n",
    "\n",
    "* Id: Id of patron\n",
    "* Patron Type Definition: Description of patron (adult, teen, child, senior, etc.).\n",
    "* Total Checkouts: Total number of items the patron has checked out from the library since the record was created.\n",
    "* Total Renewals: Total number of times the patron has renewed checked-out items.\n",
    "* Age Range: Age ranges: 0 to 9 years, 10 to 19 years, 20 to 24 years, 25 to 34 years, 35 to 44 years, 45 to 54 years, 55 to 59 years, 60 to 64 years 65 to 74 years, 75 years and over. Some blank.\n",
    "* Home Library Definition: Description of the branch library where the patron was originally registered.\n",
    "* Circulation Active Month: Month the patron last checked out library materials, or last logged into the library’s subscription databases from a computer outside the library.\n",
    "* Circulation Active Year: Year the patron last checked out library materials, or last logged into the library’s subscription databases from a computer outside the library.\n",
    "* Notice Preference Definition: Description of the patron’s preferred method of receiving library notices.\n",
    "* Provided Email Address: Indicates whether the patron provided an email address.\n",
    "* Year Patron Registered: Year patron registered with library system. No dates prior to 2003 due to system migration.\n",
    "* Outside of County: If a patron's home address is not in San Francisco, then flagged as true, otherwise false.\n",
    "* Supervisor District: Based on patron address: San Francisco Supervisor District. Note: This is an automated field, please note that if \"Outside of County\" is true, then there will be no supervisor district. Also, if the input address was not well-formed, the supervisor district will be blank.\n",
    "\n",
    "Solve the following questions using functions you implemented earlier. The code for reading the file is already given. Hint: for testing purposes it could be beneficial to only use a small part of the dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "// This snippet imports the csv file to a List[Array[String]]\n",
    "\n",
    "var patrons: List[Array[String]] = Nil\n",
    "try {\n",
    "    patrons = scala.io.Source.fromFile(\"library.csv\").getLines().drop(1).map(_.split(\",\")).toList\n",
    "} catch {\n",
    "    case e : Throwable => println(\"Library data file not found\")\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**T** (10pts) Some patrons have indicated that they want to receive notices via email, but have not provided their email address. Implement a function that outputs a list of the IDs of these patrons."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def missing_email(xs: List[Array[String]]): List[String] = {\n",
    "    return null\n",
    "}\n",
    "\n",
    "missing_email(patrons)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**T** (10pts) Implement a function that outputs the total amount of checkouts from members originally registered at a given location.\n",
    "\n",
    "```scala\n",
    ">>> checkouts(patrons, \"Noe Valley/Sally Brunn\")\n",
    "1355624\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def checkouts(xs: List[Array[String]], location: String): Int = {\n",
    "    return 0\n",
    "}\n",
    "\n",
    "checkouts(patrons, \"Mission\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**T** (15pts) Implement a function that lists the number of renewals per location in a map. Example output for part of the dataset:\n",
    "\n",
    "```scala\n",
    ">>> number_renewals(patrons)\n",
    "\n",
    "Map(Presidio -> 431988),\n",
    " (Mission -> 1218976))\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def number_renewals(xs: List[Array[String]]): Map[String, Int] = {\n",
    "    return null\n",
    "}\n",
    "    \n",
    "number_renewals(patrons)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Apache Toree - Scala",
   "language": "scala",
   "name": "apache_toree_scala"
  },
  "language_info": {
   "name": "scala",
   "version": "2.10.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}