{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Itérations et collections\n",
    "\n",
    "Il nous reste à voir comment itérer en Scala.\n",
    "Nous avons volontairement attendu la fin du cours pour parler des boucles, afin de décourager leur usage.\n",
    "Comme nous allons le voir, l'approche fonctionnelle et orientée objet de Scala encourage l'utilisation de la récursivité ou de l'itération de collections plutôt que des boucles.\n",
    "\n",
    "## Boucles\n",
    "\n",
    "Scala dispose de deux types de boucles, que vous connaissez bien : les boucles `for` et les boucles `while`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "1\n",
      "2\n",
      "10\n",
      "7\n",
      "4\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "// iterate including upper bound\n",
    "for (i <- 1 to 3) {\n",
    "    println(i)\n",
    "}\n",
    "// iterate excluding upper bound\n",
    "for (i <- 1 until 3) {\n",
    "    println(i)\n",
    "}\n",
    "for (i <- 10 to 1 by -3) {\n",
    "    println(i)\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "4\n",
      "6\n",
      "8\n",
      "6\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "for { i <- 1 to 8 \n",
    "      if i%2 == 0} {\n",
    "    println(i)\n",
    "}\n",
    "for { i <- 1 to 8\n",
    "      if i%2 == 0\n",
    "      if i > 5} {\n",
    "    println(i)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`for` loops are more often used to iterate over a collection (such as a `List`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "4\n",
      "5\n",
      "6\n",
      "6\n",
      "6\n",
      "9\n",
      "13\n"
     ]
    }
   ],
   "source": [
    "val l = List(1,2,4,5,6,6,6,9,13)\n",
    "for (i <- l) {\n",
    "    println(i)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Even more useful, `for` loops can be used to create collections."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Vector(2, 4, 6, 8)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val l1 = for (i <- 1 to 8 if i%2 == 0) yield i\n",
    "l1 // l1 is a collection of the values yielded by the loop"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Vector(3, 6, 11, 18, 27, 38, 51, 66)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "val l2 = for (i <- 1 to 8) yield i*i+2\n",
    "l2 // l2 is a collection of the values yielded by the loop"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une boucle `for` peut aussi être utilisée pour itérer sur plusieurs collections, ce qui est très pratique pour produire des produits cartésiens d'ensembles par exemple."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "8\n",
      "13\n",
      "20\n",
      "29\n",
      "40\n",
      "53\n",
      "68\n",
      "7\n",
      "10\n",
      "15\n",
      "22\n",
      "31\n",
      "42\n",
      "55\n",
      "70\n",
      "9\n",
      "12\n",
      "17\n",
      "24\n",
      "33\n",
      "44\n",
      "57\n",
      "72\n",
      "11\n",
      "14\n",
      "19\n",
      "26\n",
      "35\n",
      "46\n",
      "59\n",
      "74\n"
     ]
    }
   ],
   "source": [
    "// x ranges over l1, y ranges over l2\n",
    "// the loop has l1.length()*l2.length() iterations\n",
    "for (x <- l1; y <- l2) {\n",
    "    println(x+y)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les boucles `while` ont, sans surprise, deux versions : une où la condition est testée en début de boucle, l'autre où la condition est testée en fin de boucle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "2\n",
      "1\n",
      "3\n",
      "2\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "var x = 3\n",
    "while (x > 0) {\n",
    "    println(x)\n",
    "    x -= 1\n",
    "}\n",
    "var y = 3\n",
    "do {\n",
    "    println(y)\n",
    "    y -= 1\n",
    "} while (y > 0)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Interruptions de boucles\n",
    "\n",
    "Les boucles en Scala n'ont pas été pensées pour être interrompues.\n",
    "Pour interrompre une boucle en Scala, il faut l'avoir explicitement déclaré comme étant interruptible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "105"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// the import is mandatory...\n",
    "import scala.util.control.Breaks._\n",
    "\n",
    "var sum = 0\n",
    "breakable { for (i <- 0 to 100) {\n",
    "    sum += i\n",
    "    if (sum > 100) break\n",
    "    }\n",
    "}\n",
    "sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La raison de cette lourdeur est que ce type de raisonnement n'est pas très fonctionnel.\n",
    "Le langage, en imposant ces restrictions sur les boucles, cherche à forcer le programmeur à utiliser des choses plus idiomatiques, comme la récursivité ou des formes de Bird-Meertens (cf. infra).  \n",
    "Noter que la boucle `for` peut facilement être transformée en boucle `while`, sans interruption (la condition d'interruption est intégrée à la condition de la boucle)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "105"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "var sum = 0\n",
    "var i = 1\n",
    "while (i <= 100 && sum <= 100) {\n",
    "    sum += i\n",
    "    i += 1\n",
    "}\n",
    "sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Forme de Bird-Meertens\n",
    "\n",
    "Considérons le problème suivant : étant donnée une liste d'entiers, on souhaite savoir si tous ses éléments sont pairs.\n",
    "On peut décomposer le problème de la façon suivante : on associe à chaque élément de la liste une valeur Booléenne qui indique s'il est pair, puis l'on agrège les résultats obtenus dans un `and` Booléen.  \n",
    "Définissons deux opérations : `is_even`, de type `Int => Boolean`, et `&&`, de type `Boolean => Boolean => Boolean`.\n",
    "Plus formellement, à partir de la liste d'entiers, on produit une liste de Booléens grâce à `is_even`, puis on agrège le résultat en répétant l'opération binaire `&&` à la liste obtenue.  \n",
    "Il nous faut donc une opération qui applique une fonction unaire à tous les éléments d'une liste pour produire une nouvelle liste, et une opération qui applique agrège une liste avec une fonction binaire."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "false\n",
      "true\n"
     ]
    }
   ],
   "source": [
    "// functions provided by the list API, that we define here only to illustrate their behavior\n",
    "def map[U,V](f: U => V, l: List[U]): List[V] = l match {\n",
    "    case Nil => Nil\n",
    "    case h::t => f(h)::map(f, t)\n",
    "}\n",
    "def reduce[U,V](f: U => V => V, l: List[U], i: V): V = l match {\n",
    "    case Nil => i\n",
    "    case h::t => f(h)(reduce(f,t,i))\n",
    "}\n",
    "\n",
    "// functions implemented by the developper\n",
    "def is_even(i: Int) = i%2 == 0\n",
    "def and(x: Boolean)(y: Boolean) = x && y\n",
    "def all_even(l: List[Int]) = {\n",
    "    val tmp = map[Int, Boolean](is_even, l)\n",
    "    reduce[Boolean, Boolean](and, tmp, true)\n",
    "}\n",
    "\n",
    "println(all_even(List(1,2,3))) // false\n",
    "println(all_even(List(2,4,6))) // true"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cette forme, qui utilise les primitives `map` et `reduce`, est appelée une forme de Bird-Meertens, ou plus couramment un idiome `map/reduce`.\n",
    "\n",
    "Comparons cette méthode à une approche plus directe.\n",
    "On aurait envie d'utiliser une boucle `for` qu'on interrompt sitôt qu'un élément impair est trouvé, mais une approche récursive est plus idiomatique."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "false\n",
      "true\n"
     ]
    }
   ],
   "source": [
    "// function implemented by the developper\n",
    "def all_even_rec(l: List[Int]): Boolean = l match {\n",
    "    case Nil => true\n",
    "    case h::t => if (h%2 == 0) all_even_rec(t) else false\n",
    "}\n",
    "\n",
    "println(all_even_rec(List(1,2,3))) // false\n",
    "println(all_even_rec(List(2,4,6))) // true"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On pourrait paramétrer la fonction `all_even_rec` pour lui passer `is_even` et `and` en arguments, mais la récursion force un ordre d'exploration de la collection `l`, qui n'est pas nécessairement optimal.\n",
    "\n",
    "La différence entre les deux tient au fait qu'on utilise les fonctions `map` et `reduce` fournie par la bibliothèque de collections pour itérer convenablement la collection `l`.\n",
    "La bibliothèque a donc toute latitude pour implémenter ces fonctions au mieux en fonction des structures de données sous-jacentes.\n",
    "\n",
    "Imaginons que la collection `l` soit très grande, et stockée de manière distribuée sur plusieurs machines.\n",
    "Les fonctions `map` et `reduce` correspondantes vont ainsi pouvoir évaluer leurs arguments sur chaque sous-collection de manière distribuée.  \n",
    "Ceci n'est pas possible avec notre approche récursive, qui revient à faire faire tout le calcul par la machine locale."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Plus généralement, la forme de Bird-Meertens indique que les opérations sur les données sont en fait des _flux_ : les données passent au travers de différentes fonctions qui sont chaînées, les modifications ne sont pas faites en place (d'où l'importance des variables immuables).  \n",
    "Ceci facilite grandement la tâche des bibliothèques pour paralléliser et distribuer au mieux le calcul, en fonction des implémentations des collections manipulées.  \n",
    "Plusieurs opérations chaînées peuvent être réparties sur des machines différentes, sans que les résultats intermédiaires aient besoin d'être stockés : ils sont redirigés sous forme de flux vers les machines correspondantes.  \n",
    "On peut également envisager des collections qui agrègent des implémentations hétérogènes et les présentent de manière unifiée à l'utilisateur, qui peut utiliser `map` et `reduce` sans avoir besoin de connaître les détails d'implémentation sous-jacents.\n",
    "\n",
    "La forme de Bird-Meertens permet donc à l'environnement d'exécution d'exploiter au mieux les ressources à sa disposition, tant en \"largeur\" (taille des collections manipulées) qu'en \"profondeur\" (nombre de traitements en chaîne).\n",
    "Cet idiome prend tout son sens dans le domaine du big data, où les masses de données sont distribuées sur un réseau, l'environnement d'exécution présentant une interface unifiée à l'utilisateur.\n",
    "Les environnements dédiés l'utilisent massivement (notamment en Scala) : il est donc primordial de se familiariser avec cet idiome afin de pouvoir profiter de toute la puissance de ces environnements.\n",
    "\n",
    "## Exercice\n",
    "\n",
    "Implémentez une bibliothèque de listes doublement chaînées génériques.\n",
    "Elle doit comporter les opérations suivantes :\n",
    "1. constructeur d'une liste vide\n",
    "2. longueur d'une liste\n",
    "3. insertion à une position donnée de la liste\n",
    "4. insertion en tête de liste, insertion en queue de liste\n",
    "5. suppression d'un élément de la liste\n",
    "6. une opération `map` : si `l` est la liste composée des éléments `x1`, `x2`... `xn`, `map f l` retourne la liste composée des éléments `f(x1)`, `f(x2)`... `f(xn)`\n",
    "7. une opération `fold_left` : si `l` est la liste composée des éléments `x1`, `x2`... `xn`, alors `fold_left f l x0` retourne `f(f(...f(x0, x1), x2) ... xn)`.\n",
    "8. une opération `fold_right` : si `l` est la liste composée des éléments `x1`, `x2`... `xn`, alors `fold_right f l x0` retourne `f(x1, f(x2, f(...f(xn x0)...)`.\n",
    "9. `for_all p l` retourne `True` si et seulement si tous les éléments de la liste `l` vérifient le prédicat `p` (un prédicat est une fonction à un argument dont le type de retour est `Boolean`).\n",
    "10. `exists p l` retourne `True` si et seulement si un élément au moins de `l` vérifie le prédicat `p`.\n",
    "11. `partition p l` qui retourne deux listes : la liste des éléments de `l` qui vérifient `p` et la liste des éléments de `l` qui ne vérifient pas `p`.\n",
    "\n",
    "Vous pouvez aussi :\n",
    "12. réimplémenter la fonction qui retourne la longueur d'une liste en vous basant sur `fold_left`, puis en vous basant sur `fold_right`.\n",
    "13. implémenter des fonctions statistiques : somme, moyenne, écart-type, médiane, mode des éléments d'une liste. Ces opérations seront bien sûres restreintes aux listes contenant des valeurs numériques."
   ]
  }
 ],
 "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
}