recitation7.ipynb

{
 "metadata": {
  "name": "recitation7"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# CS1001.py\n",
      "\n",
      "## Extended Introduction to Computer Science with Python, Tel-Aviv University, Spring 2013\n",
      "\n",
      "# Recitation 7 - 25-29.4.2013\n",
      "\n",
      "## Last update: 29.4.2013"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Lambda expressions and high-order functions\n",
      "\n",
      "Lambda expressions are a way to define a function *inline* in runtime without a `def` statement.\n",
      "\n",
      "For example, lets use a lambda expression to define a simple function:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "(lambda x: x + 2)(6)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 1,
       "text": [
        "8"
       ]
      }
     ],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "type(lambda x: x + 2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 2,
       "text": [
        "builtins.function"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "f = lambda x: x + 2\n",
      "print(f(6))\n",
      "print(type(f))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "8\n",
        "<class 'function'>\n"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## `make_pow` - a function that creates and returns a function\n",
      "\n",
      "Without `lambda`:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def make_pow(n):\n",
      "    def pow_n(x):\n",
      "        return x ** n\n",
      "    return pow_n\n",
      "\n",
      "square = make_pow(2)\n",
      "print(square(10))\n",
      "cube = make_pow(3)\n",
      "print(cube(10))\n",
      "print(make_pow(0.5)(100))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "100\n",
        "1000\n",
        "10.0\n"
       ]
      }
     ],
     "prompt_number": 9
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "With `lambda`:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def make_pow(n):\n",
      "    return lambda x: x ** n\n",
      "\n",
      "square = make_pow(2)\n",
      "print(square(10))\n",
      "cube = make_pow(3)\n",
      "print(cube(10))\n",
      "print(make_pow(0.5)(100))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "100\n",
        "1000\n",
        "10.0\n"
       ]
      }
     ],
     "prompt_number": 10
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print(type(square))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "<class 'function'>\n"
       ]
      }
     ],
     "prompt_number": 11
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## `sorted` - a function that recieves and uses a function\n",
      "The sorting buiktin function `sorted` can recieve a function as an argument and use it to sort a collection.\n",
      "\n",
      "Regular `str` sorting - lexicographical orer:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "sorted([\"Yoav\", \"Amir\", \"Amiram\", \"Haim\"])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 12,
       "text": [
        "['Amir', 'Amiram', 'Haim', 'Yoav']"
       ]
      }
     ],
     "prompt_number": 12
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Sort by length - give `len` as the `key` argument to `sorted`:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "sorted([\"Yoav\", \"Amir\", \"Amiram\", \"Haim\"], key=len)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 13,
       "text": [
        "['Yoav', 'Amir', 'Haim', 'Amiram']"
       ]
      }
     ],
     "prompt_number": 13
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Sort by reverse lexicographical order - note this does not change the list elements, only the order of the elements:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "sorted([\"Yoav\", \"Amir\", \"Amiram\", \"Haim\"], key=lambda x: x[::-1])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 15,
       "text": [
        "['Amiram', 'Haim', 'Amir', 'Yoav']"
       ]
      }
     ],
     "prompt_number": 15
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "\"Yoav\"[::-1]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 16,
       "text": [
        "'vaoY'"
       ]
      }
     ],
     "prompt_number": 16
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "For a complex sorting function we can define a function instead of using `lambda`:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def comparator(x):\n",
      "    return x[::-1]\n",
      "sorted([\"Yoav\", \"Amir\", \"Amiram\", \"Haim\"], key=comparator)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 18,
       "text": [
        "['Amiram', 'Haim', 'Amir', 'Yoav']"
       ]
      }
     ],
     "prompt_number": 18
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## `compose` - a function that recieves two function and creates a third\n",
      "\n",
      "`compose` does function composition."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def compose(f1,f2):\n",
      "    def composed(x):\n",
      "        return f2(f1(x))\n",
      "    return composed"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 23
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "absolute = compose(lambda x: x ** 2, sqrt)\n",
      "print(absolute(5))\n",
      "print(absolute(-5))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "5.0\n",
        "5.0\n"
       ]
      }
     ],
     "prompt_number": 33
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "A different example:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def compose(f1,f2):\n",
      "    return lambda x: f2(f1(x))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 31
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "vector_product = lambda x,y: [x[i] * y[i] for i in range(len(x))]\n",
      "vector_product([1,2,3],[3,2,1])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 24,
       "text": [
        "[3, 4, 3]"
       ]
      }
     ],
     "prompt_number": 24
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "norm = compose(compose(lambda x: vector_product(x,x), sum), sqrt)\n",
      "norm([1,2,3])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 30,
       "text": [
        "3.7416573867739413"
       ]
      }
     ],
     "prompt_number": 30
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# `Matrix` class\n",
      "\n",
      "We will now write a class for matrices.\n",
      "\n",
      "We will try to include several methods that will make working with matrices easy."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "class Matrix:\n",
      "    \n",
      "    def __init__(self, n_rows, m_cols, default_value=0):\n",
      "        assert n_rows > 0\n",
      "        assert m_cols > 0\n",
      "        assert isinstance(default_value, (int, float, complex))\n",
      "        self.rows = [[default_value ] * m_cols for i in range(n_rows)]      \n",
      "    \n",
      "    def dim(self):\n",
      "        '''return tuple -> num of rows, num of cols'''\n",
      "        return (len(self.rows), len(self.rows[0]))\n",
      "    \n",
      "    def __repr__(self):\n",
      "        return 'Matrix: %d rows, %d cols\\n' % self.dim() + str(self.rows[0])\n",
      "   \n",
      "    def __getitem__(self, ij): \n",
      "        '''ij is a tuple (i,j). Allows m[i,j] instead m[i][j]'''\n",
      "        i,j = ij\n",
      "        if isinstance(i, int) and isinstance(j, int):\n",
      "            return self.rows[i][j]\n",
      "        elif isinstance(i, slice) and isinstance(j, slice):\n",
      "            M = Matrix(1,1) # to be overwritten\n",
      "            M.rows = [row[j] for row in self.rows[i]]\n",
      "            return M\n",
      "        else:\n",
      "            return NotImplemented\n",
      "    \n",
      "    def __setitem__(self, ij, val): \n",
      "        '''ij is a tuple (i,j). Allows m[i,j] instead m[i][j]'''\n",
      "        i,j = ij\n",
      "        if isinstance(i,int) and isinstance(j,int):\n",
      "            assert isinstance(val, (int, float, complex))\n",
      "            self.rows[i][j] = val\n",
      "        elif isinstance(i,slice) and isinstance(j,slice):\n",
      "            assert isinstance(val, Matrix)\n",
      "            n,m = val.dim()\n",
      "            s_rows = self.rows[i]\n",
      "            assert len(s_rows) == n and len(s_rows[0][j]) == m\n",
      "            for s_row, v_row in zip(s_rows,val.rows):\n",
      "                s_row[j] = v_row\n",
      "        else:\n",
      "            return NotImplemented\n",
      "\n",
      "    def __eq__(self, other):\n",
      "        assert isinstance(other, Matrix)\n",
      "        if self.dim() != other.dim():\n",
      "            return False\n",
      "        n,m = self.dim()\n",
      "        for i in range(n):\n",
      "            for j in range(m):\n",
      "                if self[i,j] != other[i,j]:\n",
      "                    return False\n",
      "        return True\n",
      "    \n",
      "    def __add__(self, other):\n",
      "        return self._entrywise_op(other, lambda x,y: x + y)\n",
      "    \n",
      "    def __sub__(self, other):\n",
      "        return self._entrywise_op(other, lambda x,y: x - y)\n",
      "    \n",
      "    def __neg__(self):\n",
      "        n,m = self.dim()\n",
      "        return Matrix(n, m, 0) - self\n",
      "    \n",
      "    def _entrywise_op(self, other, op):\n",
      "        assert isinstance(other, Matrix)\n",
      "        assert self.dim() == other.dim()\n",
      "        n,m = self.dim()\n",
      "        M = Matrix(n, m)\n",
      "        for i in range(n):\n",
      "            for j in range(m):\n",
      "                M[i,j] = op(self[i,j], other[i,j])\n",
      "        return M\n",
      "    \n",
      "    def __mul__(self, other):\n",
      "        '''multilpy by scalar or another matrix'''\n",
      "        if isinstance(other, (int,float,complex)):\n",
      "            n,m = self.dim()\n",
      "            M = Matrix(n, m, other)\n",
      "            return self._entrywise_op(M, lambda x,y: x * y)\n",
      "        elif isinstance(other, Matrix):\n",
      "            n1,m1 = self.dim()\n",
      "            n2,m2 = other.dim()\n",
      "            assert m1 == n2\n",
      "            M = Matrix(n1,m2)\n",
      "            for i in range(n1):\n",
      "                for j in range(m2):\n",
      "                    M[i,j] = sum([self[i,k] * other[k,j] for k in range(m1)])\n",
      "            return M\n",
      "        else:\n",
      "            return NotImplemented\n",
      "    \n",
      "    __rmul__ = __mul__\n",
      "    \n",
      "    def prettyprint(self):\n",
      "        return str.join('\\n',[str(row) for row in self.rows])\n",
      "    \n",
      "    def save(self, filename):\n",
      "        '''save to file'''\n",
      "        with open(filename, \"w\") as fout:\n",
      "            fout.write(self.prettyprint())\n",
      "    \n",
      "    @staticmethod\n",
      "    def load(filename):\n",
      "        '''load from file'''\n",
      "        rows = []\n",
      "        with open(filename, 'r') as fin:\n",
      "            for line in fin:\n",
      "                line = line.strip()\n",
      "                row = eval(line)\n",
      "                rows.append(row)\n",
      "        M = Matrix(1,1)\n",
      "        M.rows = rows\n",
      "        return M"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "A = Matrix(3,3,1)\n",
      "B = Matrix(3,3,1) * 2.5\n",
      "C = A - B\n",
      "D = A + B\n",
      "print(C.prettyprint())\n",
      "D.save(\"tmp\")\n",
      "print(D == Matrix.load(\"tmp\"))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "[-1.5, -1.5, -1.5]\n",
        "[-1.5, -1.5, -1.5]\n",
        "[-1.5, -1.5, -1.5]\n",
        "True\n"
       ]
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Fin\n",
      "This notebook is part of the [Extended introduction to computer science](http://tau-cs1001-py.wikidot.com/) course at Tel-Aviv University.\n",
      "\n",
      "The notebook was written using Python 3.2 and IPython 0.13.1.\n",
      "\n",
      "The code is available at <https://raw.github.com/yoavram/CS1001.py/master/recitation7.ipynb>.\n",
      "\n",
      "The notebook can be viewed online at <http://nbviewer.ipython.org/urls/raw.github.com/yoavram/CS1001.py/master/recitation7.ipynb>.\n",
      "\n",
      "This work is licensed under a [Creative Commons Attribution-ShareAlike 3.0 Unported License](http://creativecommons.org/licenses/by-sa/3.0/)."
     ]
    }
   ],
   "metadata": {}
  }
 ]
}