\documentclass[10pt]{beamer}
\usetheme[progressbar=frametitle]{metropolis}

% example compile line: xelatex -shell-escape slides.tex

\usepackage{booktabs}
\usepackage{csquotes}
\usepackage{graphicx}
\usepackage[scale=2]{ccicons}
\usepackage{pgfplots}
\usepackage{minted}
\usepgfplotslibrary{dateplot}

\usepackage{xspace}
\newcommand{\themename}{\textbf{\textsc{metropolis}}\xspace}

\title{Functional functions in python}
\subtitle{map, zip, fold, apply, filter, \dots}
\date{1st of March 2016}
\author{Lukas Prokop}
\institute{A 10-minutes presentation}
\titlegraphic{\hfill\includegraphics[height=1.5cm]{logo.png}}

\begin{document}

\maketitle

\begin{frame}{Table of contents}
  \setbeamertemplate{section in toc}[sections numbered]
  \tableofcontents[hideallsubsections]
\end{frame}

\section{Background}
\begin{frame}[fragile]{Background}
  The functions we will discuss follow directly from the \emph{Lambda calculus}.

  What's that? You know \emph{Turing machines} as computational models?
  The Church-Turing thesis claims that anything computable by a Turing machine
  can be computed using Lambda Calculus.

  In most simple words: Lambda Calculus is \enquote{model everything as function}.

  Functional programming languages implement the Lambda Calculus.
  This is why Lambda Calculus is popular among Haskellers, Clojurers, \dots
\end{frame}

\begin{frame}[fragile]{Python}
  Python is multi-paradigmatic (you can program object-oriented, imperative, functional, etc)\footnote{If you really want to\dots}

  So we can use tools of functional programming in python, right?
  Yes, but in a limited way (missing lazy evaluation, tail-call optimization, monads, immutable data structures, etc).

  Advantages:
  \begin{enumerate}
    \item Easy testable (follows from referential transparency)
    \item Mathematically reasonable (useful for formal verification)
  \end{enumerate}
  Disadvantages:
  \begin{enumerate}
    \item Less popular, therefore high bus factor
    \item Purely functional is impossible
  \end{enumerate}
\end{frame}

\begin{frame}[fragile]{First-class citizens}
  Python has functions with first-class citizenship. So we can use functions taking functions as arguments (\emph{higher-order functions}).
  Example:
  \begin{minted}[linenos]{python}
>>> a = [2, -3, 5, 4]
>>> a.sort(key=lambda v: abs(v))
>>> a
[2, -3, 4, 5]
  \end{minted}
  Wait? Did I say \verb=lambda=? Yes, as in Lambda Calculus.
\end{frame}


\section{List comprehensions}

\begin{frame}{Why lists?}
  Lambda Calculus likes lists. Why?

  We \emph{don't} use mutable data structures where we iterate over all values
  and manipulate one after another. Or pass them as pointer to a function.

  We \emph{do} create a list of values. We pop the top element and apply
  a function to it. The remaining values constitute a new list. No pointers.

  So essentially, this results directly from recursion over iteration a.
\end{frame}

\begin{frame}[fragile]{List comprehensions in python}
  A very convenient tool to create new lists.

  In mathematics, we have
  \[ \left\{\left\{a,b\right\}: a \neq b, a, b \in V\right\} \]

  In python, we have:
  \begin{minted}[linenos]{python}
V = {1, 3, 5, 6}
E = [{a, b} for a in V for b in V if a != b]
  \end{minted}
\end{frame}

\begin{frame}[fragile]{List comprehensions in python}
  Simple expressions:

  \begin{minted}[linenos]{python}
ints = [x for x in range(1, 20)]
  \end{minted}

  We can do what we will come to know as \verb=map()=:
  \begin{minted}[linenos]{python}
f = lambda v: v**2
mapped = [f(x) for x in range(1, 20)]
  \end{minted}

  We can do what we will come to know as \verb=filter()=:
  \begin{minted}[linenos]{python}
import re
# abigail's regex
pred = lambda v: not re.match(r'1?$|^(11+?)\1+$', '1' * v)
filtered = [x for x in range(20) if pred(x)]
  \end{minted}
\end{frame}

\begin{frame}[fragile]{List comprehensions in python}
  What about generators?

  \begin{minted}[linenos]{python}
f = lambda x: x * 2
gen = (f(x) for x in range(1, 20))
  \end{minted}

  What about dictionary comprehensions?
  \begin{minted}[linenos]{python}
compr1 = dict((x, f(x)) for x in range(1, 20))

# How thinks this works?
compr2 = {x: f(x) for x in range(1, 20)}
  \end{minted}
\end{frame}

\begin{frame}[fragile]{List comprehensions in python}
  It does.

  PEP~274, Barry Warsaw, 2001~\footnote{Withdrawn for Python~2.3 but included in Python~2.7 and Python~3.0}
  \begin{minted}[linenos]{python}
>>> {i : chr(65+i) for i in range(4)}
{0: 'A', 1: 'B', 2: 'C', 3: 'D'}
>>> {(k, v): k+v for k in range(4) for v in range(4)}
{(3, 3): 6, (3, 2): 5, (3, 1): 4, (0, 1): 1, ...}
  \end{minted}
\end{frame}

\begin{frame}[fragile]{List comprehensions in python}
  And finally set comprehensions:
  \begin{minted}[linenos]{python}
a = {x*2 for x in range(20)}
  \end{minted}
\end{frame}

\section{Functions}

\begin{frame}[fragile]{all (conjunction)}
  \verb=all()= returns true, if -- and only if -- all values are true.
  \begin{minted}[linenos]{python}
ints = {2, 3, 7, 23}
is_prime = lambda v: not re.match(r'1?$|^(11+?)\1+$', '1' * v)
print(all([is_prime(v) for v in ints]))
  \end{minted}

  What about an empty sequence?
  \begin{minted}[linenos]{python}
>>> print(all([]))
True
  \end{minted}
\end{frame}

\begin{frame}[fragile]{any (disjunction)}
  \verb=any()= returns true, if -- and only if -- some value is true.
  \begin{minted}[linenos]{python}
ints = {2, 4, 6, 8}
print(any([is_prime(v) for v in ints]))
  \end{minted}

  What about an empty sequence?
  \begin{minted}[linenos]{python}
>>> print(any([]))
False
  \end{minted}
\end{frame}

\begin{frame}[fragile]{zip (convolution)}
  \begin{minted}[linenos]{python}
    """
    class zip(object)
    |  zip(iter1 [,iter2 [...]]) --> zip object
    |
    |  Return a zip object whose .__next__()
    |  method returns a tuple where the i-th
    |  element comes from the i-th iterable
    |  argument.  The .__next__() method
    |  continues until the shortest iterable in
    |  the argument sequence is exhausted and
    |  then it raises StopIteration.
    """
 \end{minted}
\end{frame}

\begin{frame}[fragile]{zip (convolution)}
  \begin{minted}[linenos]{python}
>>> zip("hello", "world")
<zip object at 0x7fb624099dc8>
>>> list(zip("hello", "world"))
[('h', 'w'), ('e', 'o'), ('l', 'r'), ('l', 'l'), ('o', 'd')]
  \end{minted}

  \begin{center}
    \includegraphics[width=3cm]{zip.png} \\[10pt]
    It really reminds of a zipper \\
    \enquote{A device for temporarily joining two edges of fabric together}
  \end{center}
\end{frame}

\begin{frame}[fragile]{zip (convolution)}
  It also works for arbitrary many iterables:
  \begin{minted}[linenos]{python}
>>> list(zip({0,3,6}, {1,4,7}, {2,5,8}))
[(0, 1, 8), (3, 4, 2), (6, 7, 5)]
  \end{minted}
\end{frame}

\begin{frame}[fragile]{min/max/sum}
  Pretty straightforward: Returns the minimum or maximum value or the sum.
  \begin{minted}[linenos]{python}
>>> min([2, 56, 3])
2
>>> max([2, 56, 3])
56
>>> sum([2, 56, 3])
61
  \end{minted}
\end{frame}

\begin{frame}[fragile]{min/max/sum}
  You can also define a key to select an criterion.
  \begin{minted}[linenos]{python}
>>> min([('lukas', 1), ('horst', 9), ('thomas', 3)],
...     key=lambda v: v[1])
('lukas', 1)
>>> max([('lukas', 1), ('horst', 9), ('thomas', 3)],
...     key=lambda v: v[1])
('horst', 9)
  \end{minted}
  \verb=sum()= does not, but can take an initial value.
  \begin{minted}[linenos]{python}
>>> sum([1, 4, 6], 100)
111
  \end{minted}
\end{frame}

\begin{frame}[fragile]{map}
  \begin{minted}[linenos]{python}
    """
    class map(object)
     |  map(func, *iterables) --> map object
     |
     |  Make an iterator that computes the
     |  function using arguments from each
     |  of the iterables.  Stops when the
     |  shortest iterable is exhausted.
    """
 \end{minted}
\end{frame}

\begin{frame}[fragile]{map}
  Apply a function to every value of an iterable:
  \begin{minted}[linenos]{python}
>>> map(lambda v: v + 1, [1, 3, 5, 10])
<map object at 0x7f5939cbef98>
>>> list(map(lambda v: v + 1, [1, 3, 5, 10]))
[2, 4, 6, 11]
  \end{minted}
  Corresponds to Visitor pattern in OOP.
\end{frame}

\begin{frame}[fragile]{filter}
  \begin{minted}[linenos]{python}
    """
    class filter(object)
     |  filter(function or None, iterable)
     |  --> filter object
     |
     |  Return an iterator yielding those items
     |  of iterable for which function(item)
     |  is true. If function is None,
     |  return the items that are true.
    """
 \end{minted}
\end{frame}

\begin{frame}[fragile]{filter}
  \begin{minted}[linenos]{python}
    >>> import re
    >>> is_prime = lambda v: not \
    ...    re.match(r'1?$|^(11+?)\1+$', '1' * v)
    >>> filter(is_prime, range(1, 20))
    <filter object at 0x7fc3b0750ac8>
    >>> list(filter(is_prime, range(1, 20)))
    [2, 3, 5, 7, 11, 13, 17, 19]
  \end{minted}
\end{frame}

\begin{frame}[fragile]{apply}
  \begin{minted}[linenos]{python}
>>> apply(lambda v: v + 1, [3])
4
  \end{minted}
  Deprecated since version 2.3:
  Use \verb=function(*args, **keywords)= instead of
  \verb=apply(function, args, keywords)= (\enquote{unpacking}).

  In Python~3.0 \verb=apply= is undefined.
\end{frame}

\begin{frame}[fragile]{fold/reduce}
  Left-folding is called \verb=reduce= in python
  \begin{minted}[linenos]{python}
>>> # computes ((((1+2)+3)+4)+5)
>>> reduce(lambda x, y: x+y, [1, 2, 3, 4, 5])
15
  \end{minted}

  Python~3.0:
  Removed \verb=reduce()=. Use \verb=functools.reduce()= if you really need it; however, 99~percent of the time an explicit for loop is more readable.
\end{frame}

\begin{frame}[fragile]{Guido on those functions}
  \begin{quote}
    \enquote{About 12 years ago, Python aquired lambda, reduce(), filter() and map(), courtesy of (I believe) a Lisp hacker who missed them and submitted working patches. But, despite of the PR value, I think these features should be cut from Python 3000.

Update: lambda, filter and map will stay (the latter two with small changes, returning iterators instead of lists). Only reduce will be removed from the 3.0 standard library. You can import it from functools.}
    ---Guido van Rossum, \href{http://www.artima.com/weblogs/viewpost.jsp?thread=98196}{10th of March 2005}
  \end{quote}
\end{frame}

\section{Conclusions}
\begin{frame}[fragile]{Conclusions}
  Python fundamentally provides some simple primitives which can make your code more concise.
  \begin{itemize}
    \item The \verb=operator= package provides operator methods as functions (unbounded)
    \item The \verb=functools= package specifically provides features of functional programming
    \item The \verb=itertools= package provides primitives for generators and combinatorics
  \end{itemize}
  The Python documentation call them \href{https://docs.python.org/3/library/functional.html}{functional packages}.

  Curring is provided as \verb=functools.partial=, but I didn't cover that.
\end{frame}

\begin{frame}[fragile]{Conclusions}
  Shall I use them?
  \begin{itemize}
    \item If it fits your intuition kindly.
    \item Don't overdo functional programming in Python!
    \item Decide yourself whether a function call or list comprehension is more convenient.
  \end{itemize}
\end{frame}

\begin{frame}[fragile]{Thanks}
  \begin{center}
    \Huge{Thanks for your attention!}
  \end{center}
\end{frame}

\end{document}
