Lab 2 - Cenni di Programmazione Funzionale - Parte prima.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Cenni di Programmazione Funzionale\n",
    "Questo notebook è da intendersi come supporto alle slides usate in aule, di cui si richiamano alcuni punte. Le slides sono disponibili sul sito del corso.\n",
    "\n",
    "## 1. High Order Functions\n",
    "**ESERCIZIO:** Si consideri un polinomio di ordine $n$:\n",
    "\n",
    "$$p(x) = a_0 x^0 + a_1 x^1 + ... + a_n x^n = \\sum_{i=0,..,n} a_i x^i$$\n",
    "\n",
    "Scrivere una funzione che data la lista dei coefficienti del polinomio $[a_0, a_1, ..., a_n]$\n",
    "restituisca due funzioni che, dato un punto $x$, la prima funzione calcoli il valore del polinomio $p(x)$, la seconda funzione calcoli la derivata prima del polinomio:\n",
    "\n",
    "$$p'(x) = q(x) = a_1 x^0 + 2 a_2 x^1 + ... + n a_n x^{n-1} = \\sum_{i=1,..,n} a_i x^{i-1}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def MakePolyAndDerivate(As):\n",
    "    def Poly(x):\n",
    "        return sum(a*x**n for n,a in enumerate(As))\n",
    "    def PolyDerivate(x):\n",
    "        return sum((n+1)*a*x**n for n,a in enumerate(As[1:]))\n",
    "    return Poly, PolyDerivate\n",
    "\n",
    "p,q = MakePolyAndDerivate([1, 0, 24])\n",
    "print(p(0), q(0))\n",
    "print(p(1), q(1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Funzioni ricorsive\n",
    "\n",
    "**ESERCIZIO:** Si scrivano le seguenti funzioni usando delle definizioni ricorsive.\n",
    "\n",
    "1. Fattoriale(n)\n",
    "2. Fibonacci(n)\n",
    "3. IsPalindrome(stringa)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Fattoriale\n",
    "def Fattoriale(n):\n",
    "    if n == 0:\n",
    "        return 1\n",
    "    else:\n",
    "        return n*Fattoriale(n-1)\n",
    "    \n",
    "print(Fattoriale(4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Fibonacci\n",
    "def Fib(n):\n",
    "    if n == 0 or n == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        return Fib(n-1) + Fib(n-2) \n",
    "    \n",
    "print(Fib(6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Test if a list (e.g. string) is a palindrome\n",
    "def IsPalindrome(Ls):\n",
    "    if len(Ls) <= 1:\n",
    "        return True\n",
    "    else:\n",
    "        return (Ls[0] == Ls[-1]) and IsPalindrome(Ls[1:-1])\n",
    "    \n",
    "print(IsPalindrome(\"abcdedcba\"))\n",
    "print(IsPalindrome(\"abcdeecba\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3. List processing\n",
    "\n",
    "Esempi da fare:\n",
    "\n",
    "1. Sommatoria degli elementi di una lista: \n",
    "$$\\mbox{sum}(Ls) = \\sum_{e \\in Ls} e$$\n",
    "2. Produttoria degli elementi di una lista: \n",
    "$$\\mbox{prod}(Ls) = \\prod_{e \\in Ls} e$$\n",
    "3. Generalizzare le due funzioni precedenti in una singola funzione **`Fold`**:\n",
    "$$\\mbox{fold}(f,v_0,[v_1,v_2,v_3,...,v_n]) = f(v_1, f(v_2, f(v_3, ... f(v_n,v_0))))$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def Sum(Ls):\n",
    "    if Ls == []:\n",
    "        return 0\n",
    "    else:\n",
    "        return Ls[0] + Sum(Ls[1:]) # Notazione postfix per l'addizione\n",
    "\n",
    "# Meglio se si usa operator.add dalla libreria operator\n",
    "# https://docs.python.org/3.6/library/operator.html\n",
    "def Add(x,y):\n",
    "    return x+y\n",
    "\n",
    "def Sum2(Ls):\n",
    "    if Ls == []:\n",
    "        return 0\n",
    "    else:\n",
    "        return Add(Ls[0], Sum(Ls[1:])) # Notazione prefix per l'addizione"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def Mul(x,y):\n",
    "    return x*y\n",
    "\n",
    "def Prod(Ls):\n",
    "    if Ls == []:\n",
    "        return 1\n",
    "    else:\n",
    "        return Mul(Ls[0], Prod(Ls[1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def Fold(F, v, Ls):\n",
    "    if Ls == []:\n",
    "        return v\n",
    "    else:\n",
    "        return F(Ls[0], Fold(F, v, Ls[1:]))\n",
    "\n",
    "def FoldSum(Ls):\n",
    "    return Fold(Add, 0, Ls)\n",
    "\n",
    "def FoldProd(Ls):\n",
    "    return Fold(Mul, 1, Ls)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Espressività della funzione **`fold`**\n",
    "Con la funzione `fold` appena vista, si possono scrivere diverse funzioni classiche che operano su delle liste. Si chiede di sviluppare come esercizio, le seguenti funzioni in termini di `fold`:\n",
    "\n",
    "1. `And(Ls)`: viene valutata a True se tutti gli elementi della lista sono True\n",
    "2. `Or(Ls)`: viene valutata a True se almeno uno degli elementi della lista è True\n",
    "3. `Length(Ls)`: determina la lughezza di una lista\n",
    "4. `Reverse(Ls)`: inverte il contenuto di una lista (esempio: [1,2,3,4] diventa [4,3,2,1])\n",
    "5. `FoldFactorial(n)`: una funzione che calcola il fattoriale di `n`\n",
    "6. `SumLength(Ls)`: restituisce una coppia di valori, data dalla somma degli elementi nella lista, e la lunghezza della stringa (esempio: `SumLength([1,2,3,4]) = (10,4)`)\n",
    "7. `Map(F, Ls)`: una funzione `map` equivalente alla builtin di python\n",
    "8. `Filter(P, Ls)`: una funzione `filter` equivalente alla builtin di python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# DA SCRIVERE LE 8 FUNZIONI RICHIESTE SOPRA"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### FoldRight e FoldLeft\n",
    "La funzione `fold` scritta sopra, viene generalmente chiamata `foldRight` in quando applica la funzione data agli elementi della lista utilizzando la convenzione che la funzione data sia associativa a destra. Per esempio, la funzione `FoldSum` come implementa sopra, se applicata alla lista $[1,2,3,4,5]$, calcola $(1+(2+(3+(4+(5+0)))))$.\n",
    "\n",
    "**ESERCIZIO:** Si scriva una funzione `fold` che assuma che per la regola data valga regola associativa a sinistra, ovvero che data la lista $[1,2,3,4,5]$, calcoli $(((((0+1)+2)+3)+4)+5)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def FoldLeft(F, v, Ls):\n",
    "    # DA COMPLETARE\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**ESERCIZIO:** Si scriva la funzione `reverse(Ls)` utilizzando la `FolfLeft` invece della `Fold` (se non altrimenti specificato, per `fold` si intende la `FolfRight`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def ReverseFoldL(Ls):\n",
    "    # DA COMPLETARE\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**TODO:** Commenti sulle differenze tra `FoldRight` e `FoldLeft`."
   ]
  }
 ],
 "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": 2
}