Lab 3 - Cenni di Programmazione Funzionale - Parte seconda.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Elementi a supporto della *Programmazione funzionale*\n",
    "Vediamo di seguito quelli che sono gli strumenti più usati per programmare con uno stile *elegante*, *preciso* e *conciso*.\n",
    "\n",
    "## Lambda Expressions\n",
    "\n",
    "Il primo elemento sono le **lambda expressions**, chiamate anche **anonymous functions**. La loro forma generale è del tipo:\n",
    "\n",
    "<p><center>`lambda <sequenza di nomi di variabili>: <espressione>`</center></p>\n",
    "\n",
    "Dove **lambda** è una parola riservata (keyword) di Python. Le lambda expressions sono usate soprattutto quando si devono passare delle funzioni come parametri ad altre funzioni.\n",
    "\n",
    "**ESEMPIO:**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Due modi diversi per definire la stessa funzione:\n",
    "# Primo: metodo standard, funzione di nome F1\n",
    "def F1(x):\n",
    "    return x**2\n",
    "\n",
    "# Secondo: lambda expression a cui si assegna un nome\n",
    "F2 = lambda x: x**2\n",
    "\n",
    "F1(3.3) == F2(3.3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(lambda x,y: x+y)(2,3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print(type(lambda x: x**2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Funzione `map`\n",
    "La funzione `map` è la prima di una **triade** di funzioni molto importanti. Le altre due sono `filter` e `reduce`.\n",
    "\n",
    "La funzione `map` è una funzione che prende in input come primo argomento una funzione di $n$ argomenti e viene poi seguita da $n$ collezioni iterabili della stessa lunghezza (come ad esempio $n$ liste); restituisce in output **generator** specifico di tipo **map object**:\n",
    "\n",
    "<p><center>`map(func, *iterables) --> map object`</center></p>\n",
    "\n",
    "Per ottenere il risultato bisogna iterare sugli elementi del *map object*, per esempio costruendo una lista con la funzione `list()`. Di solito la funzione data come prima argomento prende un solo argomento in input e la funzione viene quindi usata con una sola lista di input. La funzione `map` è una delle builtins di Python, ma è relativamente facile scrivere una versione usando gli elementi di Python stesso.\n",
    "\n",
    "**ESEMPIO 1**: Per calcolare il quadrato di una lista di numeri:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "map(lambda x: x**2, [1,2,3,4,5,6,7,8,9,10])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "list(map(lambda x: x**2, [1,2,3,4,5,6,7,8,9,10]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si osservi che la funzione `map` ha passato alla funzione `list` un `map object` con cui ha costruito la lista data visualizzata in output."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**ESEMPIO 2**: Per calcolare il prodotto elemento per elemento di due vettori:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "list(map(lambda x, y: x*y, [1,2,3,4,5,6,7,8,9], [9,8,7,6,5,4,3,2,1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**ESERCIZIO 1**: Scrivere un'espressione che calcoli il quadrato delle differenze elemento per elemento di due \"vettori\" dati, ovvero:\n",
    "$$\\sum_{i = 1,..,n} (x_i-y_i)^2, \\quad x,y \\in \\mathbb{R}^n$$\n",
    "\n",
    "Usare nell'espressione le due liste $[1,2,3,4,5,6,7,8,9]$  e $[9,8,7,6,5,4,3,2,1]$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# SVOLGERE ESERCIZIO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Funzione `filter`\n",
    "La funzione `filter` letteralmente \"filtra\" gli elementi: prende in input un **predicato** (ovvero una funzione booleana, che restituisce `True` o `False`) e una sequenza *iterabile* di elementi, e restituisce in output un `filter object` su cui iterando si ottiene la sequenza di elementi per cui il predicato è verificato (pari a `True`): \n",
    "\n",
    "<p><center>`filter(function or None, iterable) --> filter object`</center></p>\n",
    "\n",
    "La funzione **filter** è una delle builtins di Python.\n",
    "\n",
    "**ESEMPIO 3**: Filtrare i numeri pari di una lista data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "list(filter(lambda x: x%2 == 0, {1,2,3,4,5,6,7,8,9}))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**ESERCIZIO 2**: Calcolare il quadrato dei numeri dispari di una lista data. Suggerimento: utilizzare sia `map` che `filter`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# SVOLGERE ESERCIZIO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "## *List comprehensions*\n",
    "Usare la notazione di *list comprehensions* può rendere talvolta il codice più compatto e può spostare il focus di chi lo legge dal **come** si stan facendo i conti al **cosa** si sta calcolando. Si consideri l'esempio seguente:\n",
    "\n",
    "```\n",
    "collection = list()\n",
    "for datum in data_set:\n",
    "    if condition(datum):\n",
    "        collection.append(datum)\n",
    "    else:\n",
    "        new = modify(datum)\n",
    "        collection.append(new)\n",
    "```\n",
    "\n",
    "che usando la notazione di *list comprehensions* si può riscrivere come:\n",
    "\n",
    "```\n",
    "collection = [d if condition(d) else modify(d) for d in data_set]\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Funzione `reduce`\n",
    "La funzione `reduce` letteralmente \"riduce\" una sequenza di elementi ad uno scalare. In [programmazione funzionale](https://wiki.haskell.org/Fold) viene chiamata anche **`fold`**. La funzione `reduce` prende in input una funzione, chiamata \"combinante\", una sequenza iterabile di elementi e un valore iniziale (facoltativo). In output viene restituito un valore che risulta dall'applicare in sequenza agli elementi della lista la funzione data:\n",
    "\n",
    "<p><center>`reduce(function, sequence[, initial]) -> value`</center></p>\n",
    "\n",
    "Per esempio, se viene passata in input la funzione `f(x,y)`, la lista `[1,2,3,4]` e il valore iniziale 0, la funzione `reduce` calcola il valore:\n",
    "\n",
    "$$v = f(f(f(f(0,1), 2), 3), 4)$$\n",
    "\n",
    "Se la funzione data è la somma, questo risulta equivalente a calcolare: \n",
    "\n",
    "$$((((0+1)+2)+3)+4) = 10$$\n",
    "\n",
    "La funzione `reduce` non è una builtin di Python e deve essere importata con il comando:\n",
    "\n",
    "`from functools import reduce`\n",
    "\n",
    "**ESEMPIO 4**: Scrivere il codice per l'esempio precedente"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from functools import reduce"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "reduce(lambda x,y: x+y, [1,2,3,4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**ESERCIZIO 3**: Scrivere una funzione che calcoli la norma di un vettore $\\sqrt{\\sum_{i=1,..,n} x_i^2}$. Suggerimento: la funzione `sqrt` è una funzione della libreria `math` e deve essere importata con ìl comando `from math import sqrt`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from math import sqrt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# SVOLGERE ESERCIZIO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4. Lazy Evaluation e Liste infinite\n",
    "Negli esempi sopra, le funzioni `map` e `filter` erano funzioni che restituivano delle lista che venivano elaborate in maniera **LAZY**: ovvero, l'elemento i-esimo della lista non sono calcolato sino a quando non è effettivamente necessario per effettuare qualche calcolo. Per questo motivo, si dice che la lista viene valutata in modalità lazy. Questo è un concetto molto generale, che in Python viene implementato attraverso degli oggetti chiamati *generators* e *iterators*. I primi sono gli oggetti che generano le liste, mentre i secondi sono gli oggetti che permettono di valutare tali liste in modalità lazy, valutando un elemento alla volta solo quando viene effettivamente richiesto. Per poter definire una funzione che genera una lista infinita si usa la parola chiave **`yield`** invece del solito **`return`**. Per richiedere un elemento alla volta di un iteratore si utilizza la builtin **`next()`** (vedere l'esempio sotto).\n",
    "\n",
    "Si noti, che sfruttando una valutazione delle liste di tipo `LAZY` è quindi possibile definire delle liste di lunghezza infinita, che però vengono valutate solamente quando uno dei suoi elementi è veramente necessario per effettuare dei conti.\n",
    "\n",
    "**ESEMPI:**\n",
    "1. Funzione `Counter()` che restituisce la lista infinita dei numeri natuali a partire da 1.\n",
    "2. Funzione builtin `Enumerate(Ls)` che restituisce la coppia `(i,l)` dove `l` è l'`i`-esimo elemento della lista Ls."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Primo esempio di lista \"infinita\"\n",
    "def Counter():\n",
    "    c = 1\n",
    "    while True:\n",
    "        yield c\n",
    "        c += 1\n",
    "        \n",
    "cnt = Counter()\n",
    "print(type(cnt))\n",
    "print([next(cnt) for _ in range(10)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Implementazione naive in Python della funzione builtin `enumerate(Ls)`\n",
    "def Enumerate(Ls):\n",
    "    i = 0\n",
    "    for l in Ls:\n",
    "        yield i,l\n",
    "        i += 1\n",
    "\n",
    "print(Enumerate(\"CiaoBella\"))\n",
    "print(list(Enumerate(\"CiaoBella\")))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**ESERCIZIO 4:** Implementare una funzione che restituisce lista infinita dei numeri primi primi."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Terzo esempio di lista infinita\n",
    "def NumeriPrimi():\n",
    "    # DA COMPLETARE\n",
    "\n",
    "crivello = NumeriPrimi()        \n",
    "print([next(crivello) for _ in range(10)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**ESERCIZIO 5 (FACOLTATIVO):** Implementare una funzione che restituisca la lista infinita dei numeri dati dalla successione di Fibonacci."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def Fibonacci():\n",
    "    # DA COMPLETARE\n",
    "    pass"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [default]",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}