{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Programmation fonctionnelle\n",
    "\n",
    "## Fonctions de haut-niveau\n",
    "\n",
    "Dans un langage fonctionnel, les fonctions sont des citoyens de premier niveau.\n",
    "La manipulation de fonctions et leur typage sont ainsi facilités.\n",
    "On peut définir des valeurs et des variables contenant des fonctions.\n",
    "\n",
    "Le type d'une fonction est `A => B`, où `A` est le type de l'argument et `B` le type de retour de la fonction."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "/* /!\\ DO NOT FORGET '=', otherwise the return type is 'Unit' */\n",
    "def incr1(x: Int) = x+1           // argument type is mandatory\n",
    "def incr2(x: Int): Int = x+1      // return type can be explicited\n",
    "def incr4 = (x: Int) => x+1       // alternative syntax, the return type is implicit\n",
    "def incr3: Int => Int = x => x+1  // alternative syntax, note how the argument type is explicited"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Rappelons que les fonctions sont des entités comme les autres : une fonction peut prendre une fonction en argument et retourner une fonction."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def add_cste(c: Int) = (x: Int) => x+c\n",
    "def apply(f: Int => Int, x: Int) = f(x)\n",
    "def compose(f: Int => Int, g: Int => Int) = (x: Int) => f(g(x))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fonctions curryfiées\n",
    "\n",
    "Considérons la fonction `add_cste` ci-dessus.\n",
    "Elle prend un entier en argument, et retourne une fonction de type `Int => Int`.\n",
    "Le type de `add_cste` est donc `Int => (Int => Int)`.\n",
    "Soient `a` et `b` deux valeurs (ou variables, peu importe) de type `Int`.\n",
    "`add_cste(a)` est de type `Int => Int`, donc on peut l'appliquer à `b`, ce qui donne un entier `add_cste(a)(b)`.\n",
    "Remarquez que cet entier n'est autre que `a+b`.\n",
    "On pourrait implémenter la même opération avec la fonction `def add(x: Int, y: Int) = a+b`, de type `(Int, Int) => Int`.\n",
    "\n",
    "On appelle `add_cste` une fonction _curryfiée_ : plutôt que d'avoir plusieurs arguments, elle a un seul argument et renvoie une fonction des autres arguments.\n",
    "Le passage d'une fonction non-curryfiée (comme `add`) à une fonction curryfiée (comme `add_cste`) s'appelle la _curryfication_ (\"_currying_\" en anglais).\n",
    "L'opération inverse s'appelle la _décurryfication_.  \n",
    "La curryfication permet d'appliquer _partiellement_ des fonctions.\n",
    "Par exemple, on peut définir une fonction qui incrémente un entier comme `def incr = add_cste(1)`.\n",
    "Similairement, une fonction de décrémentation est obtenue comme `def decr = add_cste(-1)`.  \n",
    "Remarquez comme la curryfication permet de partager le code de `incr` et `decr` (même si cela paraît futile pour cet exemple).\n",
    "\n",
    "**NB :** comme la curryfication permet d'appliquer aux différents arguments un par un, l'opération `=>` sur les types est _associative_ à droite, ce qui permet d'éliminer des parenthèses.\n",
    "Le type `Int => (Int => Int)` peut se noter `Int => Int => Int`.\n",
    "Attention, il est différent du type `(Int => Int) => Int`, dont l'argument est une fonction et le type de retour est `Int`.\n",
    "\n",
    "# Exercice : Entiers de Church\n",
    "\n",
    "Les entiers de Church sont un encodage des entiers naturels dans le lambda-calcul, qui est un modèle théorique des langages de programmation fonctionnels.  \n",
    "L'entier `n` est codée comme une fonction qui prend deux arguments `f` et `x` et renvoie `f^n(x)`, c'est-à-dire `f` composée `n` fois à elle-même appliquée à `x`.  \n",
    "On rappelle que `f^0(x) = x` et `f^1(x) = f`.\n",
    "Pour simplifier, on considère que `x` est de type `Int` : `f` est donc de type `Int => Int`.\n",
    "Un entier de Church est donc de type `(Int => Int) => Int => Int`, type que l'on notera `ChurchNumber` pour raccourcir.\n",
    "\n",
    "On cherche à implémenter une fonction `church` de type `Int => (Int => Int) => Int => Int` qui à un entier naturel `n` associe son entier de Church.\n",
    "1. Implémentez l'entier de Church représentant 0.\n",
    "2. Implémentez la fonction `succ`, de type `ChurchNumber => ChurchNumber`, qui à un entier de Church `n` associe l'entier de Church correspondant à `n+1`.\n",
    "3. Implémentez la fonction `church`, qui à un `Int` associe le `ChurchNumber` correspondant. Cette fonction peut être définie récursivement à partir de `zero` et de `succ`.\n",
    "4. Implémentez l'opération `add` sur les entiers de Church.\n",
    "5. Implémentez l'opération `multiply` sur les entiers de Church."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "5\n",
      "7\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "// a useful typedef\n",
    "type ChurchNumber = (Int=>Int) => Int => Int\n",
    "\n",
    "def zero(f: Int=>Int)(x: Int) = /* TODO */\n",
    "def succ(n: ChurchNumber): ChurchNumber = /* TODO */\n",
    "def church: Int => ChurchNumber = /* TODO */\n",
    "\n",
    "def add(n: ChurchNumber)(p: ChurchNumber): ChurchNumber = /* TODO */\n",
    "    \n",
    "def multiply(n: ChurchNumber)(p: ChurchNumber): ChurchNumber = /* TODO */\n",
    "    \n",
    "// tests\n",
    "val incr = (x:Int) => x+1\n",
    "def test(n: ChurchNumber) = n(incr)(0)\n",
    "println(test(church(0))) // 0\n",
    "println(test(church(5))) // 5\n",
    "println(test(add(church(2))(church(5)))) // 7\n",
    "println(test(multiply(church(2))(church(5)))) // 10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercice : Implémenter des ensembles avec des fonctions\n",
    "\n",
    "On rappelle qu'un ensemble `E` peut être vu comme une fonction booléenne, sa _fonction caractéristique_.\n",
    "On identifie ici un ensemble avec sa fonction caractéristique.\n",
    "`E(x)` renvoie `true` si et seulement si `x` appartient à `E`.\n",
    "Implémentez les opérations `union`, `intersection`, `complement`, `difference`, `symmetric_difference` sur les fonctions charactéristiques.\n",
    "Implémentez aussi une fonction qui associe à une liste d'entiers la fonction caractéristique correspondante."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Name: Compile Error\n",
       "Message: <console>:3: error: illegal start of simple pattern\n",
       "           for (var i = 0; i <= 10; ++i) {\n",
       "                ^\n",
       "<console>:3: error: '<-' expected but ';' found.\n",
       "           for (var i = 0; i <= 10; ++i) {\n",
       "                         ^\n",
       "<console>:3: error: '<-' expected but ';' found.\n",
       "           for (var i = 0; i <= 10; ++i) {\n",
       "                                  ^\n",
       "<console>:3: error: illegal start of simple pattern\n",
       "           for (var i = 0; i <= 10; ++i) {\n",
       "                                       ^\n",
       "StackTrace: "
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type IntSet = Int => Boolean\n",
    "\n",
    "// printSet(S) actually prints the set (S inter [0..9])\n",
    "def printSet(S: IntSet) = \n",
    "    for (var i = 0; i < 10; ++i) {\n",
    "        if (S(i)) {\n",
    "            print(i, \",\");\n",
    "        }\n",
    "    }\n",
    "    println(\"\")\n",
    "\n",
    "def insert: IntSet => Int => IntSet = /* TODO */\n",
    "def erase: IntSet => Int => IntSet = /* TODO */\n",
    "def union: IntSet => IntSet => IntSet = /* TODO */\n",
    "def intersection: IntSet => IntSet => IntSet = /* TODO */\n",
    "def complement: IntSet => IntSet = /* TODO */\n",
    "def difference: IntSet => IntSet => IntSet = /* TODO */\n",
    "def symmetric_difference: IntSet => IntSet => IntSet = /* TODO */\n",
    "\n",
    "def fromSet: Set[Int] => IntSet = /* TODO */\n",
    "\n",
    "val S1 = List(1, 2, 3)\n",
    "val S2 = List(2, 4, 6)\n",
    "\n",
    "printSet(union(S1)(S2))                 // 1,2,3,4,6\n",
    "printSet(intersection(S1)(S2))          // 2\n",
    "printSet(complement(S1))                // 0,4,5,6,7,8,9\n",
    "printSet(difference(S2)(S1))            // 4,6\n",
    "printSet(symmetric_difference(S1)(S2))  // 1,3,4,6"
   ]
  }
 ],
 "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
}