wtfunctional/tex/wtfunctional.tex

\documentclass[english,aspectratio=43]{beamer}

\usepackage{babel}
\usepackage{csquotes}
\usepackage{tabularx}
\usepackage{shellesc}
\usepackage[backend=biber,]{biblatex}
\bibliography{wtf}
\renewcommand{\bibfont}{\small}

\usepackage{fontspec}
\setsansfont{Fira Sans}
\setmonofont{Inconsolata-g}

\usetheme{Antibes}
\setbeamercovered{transparent}

\newcommand{\cpp}{\texttt{C++}}

\title{WTFunctional}
\author{Oliver Rümpelein}
\subtitle{Functional paradigms and non-functional languages}
\date{2016-06-11}

\input{headers/listings}

\begin{document}
\frame{\titlepage}

\begin{frame}[plain]{What?}
    \begin{enumerate}[<+->]
    \item Dafunc? Introduction to functional paradigms using Haskell
    \item PhuncY! Functional programming in Python
    \item Fun\cpp{}tional: STL-hacks and usage in \cpp
    \end{enumerate}
    \begin{uncoverenv}<4-| invisible@1-3>
        \emph{With preview to \cpp{}17/20/22!}
    \end{uncoverenv}
\end{frame}

\section{Dafunc?}
\subsection{Functional programming}
\begin{frame}{Understanding functional paradigms}
    Here: so called \enquote{purely/strict functional} paradigm.
    \begin{itemize}
    \item<+-> Programming without \enquote{side-effects}
        \begin{itemize}
        \item<+-> No mutability
        \item<+-> Functions work only in local context
        \end{itemize}
    \item<+-> Extensive use of lists and so called maps/reduces (later)
    \item<+-> Do not mix up with \enquote{procedural} programming (using only functions)!
    \end{itemize}
\end{frame}

\begin{frame}[fragile]{Example}
    % ToDo: C-code call by value, call by reference.
\begin{cppcode}
int f(int  x) { return ++x;}
int g(int& x) { return ++x;}
int main() {
  int x = 2;
  f(x);
  assert(x==2); // f is “functional”
  g(x);
  assert(x!=2); // g is not!
}
\end{cppcode}
\end{frame}

\begin{frame}{Pros and Cons}
    \uncover<+->{Pros:}
    \begin{itemize}[<+->]
    \item Maintainability
    \item Testing
    \item (often) shorter code
    \end{itemize}
    \uncover<+->{Cons:}
    \begin{itemize}[<+->]
    \item harder to learn
    \item harder to understand
    \item slower due to abstraction
    \end{itemize}
\end{frame}

\begin{frame}{Languages}
    \begin{itemize}[<+->]
    \item Haskell(*)
    \item Clojure(*) (runs in JVM)
    \item F\#, OCaml
    \item Ada, Lua, Scala
    \item Lisp/Scheme and dialects (some (*))
    \item JS, Python, Swift
    \item Swift
    \end{itemize}
\end{frame}

\subsection{Case study: Haskell}
\begin{frame}{Overview}
    \begin{itemize}[<+->]
    \item \emph{Haskell} is a purely functional, compiled programming language
        developed since 1990.
    \item It is typed and has a strong meta-type system (comparable to
        interfaces in OOP)
    \item The most important implementation is \emph{GHC} (Glasgow Haskell
        Compiler)
    \item Haskell is lazy. Statements get evaluated only when needed, if ever.
    \end{itemize}
\end{frame}

\begin{frame}[fragile]{Syntax – Functions}
    Function definition and calls:
\begin{haskell}
mysum :: Num a => a -> a -> a -> a
mysum x y z = x + y + z
-- b == 6
b = mysum 1 2 3
\end{haskell}
    \pause
    Functions always get evaluated left to right, thus the following works (\emph{\enquote{Currying}}):
\begin{haskell}
mysum2 = mysum 2
-- c == 12
c = mysum2 4 6
\end{haskell}
\end{frame}

\begin{frame}[fragile]{Syntax – Lists (1)}
    \begin{itemize}[<+->]
    \item Lists in Haskell can only hold data of one type. They are defined using
        \haskellcmd{a = [1,2,3,4]} or similar.
    \item An automatic range can be obtained by using \haskellcmd{b = [1..4]},
        where the last number is inclusive.
    \item If possible, Haskell will try to inhibit the step
        automatically. \haskellcmd{c = [1,3..7]} yields
        \haskellcmd{[1,3,5,7]}.
    \item When leaving out the end specifier, a range can be infinite. In this case,
        it's up to the programmer to constrain things.
    \end{itemize}
\end{frame}

\begin{frame}[fragile]{Syntax – Lists (2)}
    \begin{itemize}[<+->]
    \item Two lists can be concatenated using the \haskellcmd{++} operator:
        \haskellcmd{[1,2,3] ++ [4..7]}
    \item Single objects get pushed to the front using
        \enquote{\haskellcmd{:}}: \haskellcmd{1:[2..7]}.
    \item This can also be used vice versa to extract single values from lists:
\begin{haskell}
extract (x:xs) = x
-- a = 1
a = extract [1..5]
\end{haskell}
    \end{itemize}
\end{frame}

\begin{frame}[fragile]{Syntax – Recursion}
    Example: Add a value to every entry in an array
\begin{haskell}
addto :: (Num a) => [a] -> a -> [a]
addto [] _ = [] -- edge case (list empty)
addto (x:xs) y = (x+y) : addto xs y
b = [1..4]
-- c == [5,6,7,8]
c = addto b 4
\end{haskell}
\end{frame}

\begin{frame}[fragile]{Lambdas}
    \begin{itemize}[<+->]
    \item By now: lambda-functions well known from other programming languages
    \item Represent \enquote{anonymous} functions, i.e. locally defined functions
        without associated name
    \item Can simply be passed to algorithms, i.e. sort.
    \item Syntax: \haskellcmd{\var1 var2 -> retval} (The \haskellcmd{\} is for λ)
    \end{itemize}
\end{frame}

\begin{frame}[fragile]{Maps, Filters}
    \begin{itemize}[<+->]
    \item A \emph{Map} applies a function to all elements of a list:
        \haskellcmd{map (^2) c}\quad (square the elements of c)
    \item A \emph{Filter} does exactly that to a list:
        \haskellcmd{filter (\x -> (mod x 2) == 0) c} \quad (even numbers in c,
        filtering done using a lambda function)
    \end{itemize}
\end{frame}

\begin{frame}[fragile]{Folds (1)}
    \begin{itemize}[<+->]
    \item \emph{Folds} (or sometimes \emph{reductions}) create single values
        using whole lists, i.e. sums over all elements
    \item Often implemented using recursion
    \item Need a function, an initialisation value and a list
    \end{itemize}
\end{frame}

\begin{frame}[fragile]{Folds (2)}
    \uncover<+-> Example: Self written right fold and sum:
\begin{haskell}
mfold f z [] = z
mfold f z (x:xs) = f x (mfold f z xs)
msum = mfold (+) 0
-- g == 5050
g = msum [1..100]
\end{haskell}
    \uncover<+->{Note that this gets pretty resource hungry with large
      lists, better use left-folds for this (see~\cite{whichfold}, not shown
      here as they are more complicated)}
\end{frame}

\begin{frame}[fragile]{Example: Pythagorean triangles}
    Get all Pythagorean triangles with a hypotenuse of length at most 15:
\begin{haskell}
> [(a,b,c) | a <- [1..15],
             b <- [1..a],
             c <- [1..b],
             a^2 == b^2 + c^2]
[(5,4,3),(10,8,6),(13,12,5),(15,12,9)]
\end{haskell}
\end{frame}

\begin{frame}[fragile]{Example: Bubble-sort}
    Recursive, functional bubble-sort algorithm:
\begin{haskell}
bsort f [] = []
bsort f (x:xs) = (bsort f a) ++ [x] ++ (bsort f b)
  where a = [ y | y <- xs, not (f x y) ]
        b = [ y | y <- xs, (f x y) ]
mbsort = bsort (\x y -> (x > y))
\end{haskell}
    \pause Result:
\begin{haskell}
λ> h = [1, 20, -10, 5]
λ> mbsort h
[-10,1,5,29]
\end{haskell}
\end{frame}

\section{PhuncY!}
\subsection{Overview}
\begin{frame}{Functional programming in Python}
    \begin{itemize}[<+->]
    \item Obviously, python is not strictly functional…
    \item …but has functions as first class objects!
    \item Some other stuff is widely used, but with another syntax,…
    \item … although there usually are ways to get the \enquote{real} functional
        style.
    \item I use python3 here, python2 differs in some points.
    \end{itemize}
\end{frame}

\subsection{Elements}
\begin{frame}[fragile]{Lambdas, Maps}
    \begin{itemize}[<+->]
    \item Lambda-syntax: \pycmd{lambda a,b: a+b}
    \item Maps are done by \pycmd{map}
    \item \emph{Note:} Most functional list-functions return iterators in
        python, not lists!
    \item Use \pycmd{list()} to cast Iterators, but this is usually not
        necessary (you use them as iterators either way).
    \end{itemize}
\end{frame}

\begin{frame}[fragile]{Filters}
    \begin{itemize}[<+->]
    \item Can be done using \pycmd{filter(func, iter)}:
\begin{pycode}
a = range(1,7)
b = filter(lambda x: x%2, a)
print(list(b))
# [1,3,5]
\end{pycode}
    \item Alternatively, use List Comprehension:
\begin{pycode}
a = range(1,7)
b = [x for x in a if x%2]
print(b)
\end{pycode}
    \item Pro: Maybe easier readable, returns list
    \item Con: Returns list (slower when iterating afterwards)
    \end{itemize}
\end{frame}

\begin{frame}[fragile]{Fold}
    \begin{itemize}[<+->]
    \item From the python2 to python3 changelog:
        \begin{quote}
            Removed `reduce()`. Use `functools.reduce()` if you really need it;
            however, 99 percent of the time an explicit `for` loop is more
            readable.
        \end{quote}
    \item I disagree – Old-style is more explicit and  still available from
        \pycmd{functools}, plus reduce is faster with build-in functions.
    \item Example – sum of squares
\begin{pycode}
from functools import reduce
a = range(10)
mapped = map(lambda x: x**2, a)
reduced = reduce(lambda x,y: x+y, mapped)
\end{pycode}
    \end{itemize}
\end{frame}

\begin{frame}[fragile]{Currying}
    \begin{itemize}[<+->]
    \item No real currying, but several workarounds
    \item Lambdas: \pycmd{g=lambda x: foo(2,x)}
    \item \pycmd{functools.partial}:
\begin{pycode}
def foo(x,y):
  return x+y
bar=partial(foo, 2)
bar(3) # 5
\end{pycode}
    \end{itemize}
\end{frame}

\begin{frame}{Decorators (1)}
    \begin{itemize}[<+->]
    \item Often used to modify functions in Frameworks
    \item Basic pattern: Decorator is a function that itself takes a function,
        and returns a wrapper
    \item Step-by-step introduction to decorators at~\cite{decorators}
    \end{itemize}
\end{frame}

\begin{frame}[fragile]{Decorators (2)}
\begin{pycode}
def debug(func):
  def inner(*args, **kwargs):
    print("F: {}, args: {}, kwargs: {}\n"
          .format(func.__name__, args, kwargs))
    return func(*args, **kwargs)
  return inner

@debug
def foo(x):
  pass

foo(2) # => F: foo, args: (2), kwargs: {}
\end{pycode}
\end{frame}

\subsection{Conclusion}
\begin{frame}{Quite enough…}
    \begin{itemize}[<+->]
    \item Python is not really functional…
    \item …but is strongly influenced by functional paradigms.
    \item Its functional parts are heavily used, i.e in Genomics
    \end{itemize}
\end{frame}

\begin{frame}[fragile]{Example}
\begin{pycode}
def mybubblesort(array,
      func=lambda x, y: True if x > y else False):
  if (len(array) == 0):
    return []
  else:
    x, *xs = array
    return mybubblesort([y for y in xs
                         if func(x,y)], func) \
        + [x] \
        + mybubblesort([y for y in xs \
                         if not func(x,y)], func)
\end{pycode}
\end{frame}

\section{Fun\cpp{}ional}
\subsection{Overview}

\begin{frame}{Functional programming in \cpp{}}
    \begin{itemize}[<+->]
    \item \enquote{Classical} \cpp{} has a few functional elements…
    \item …but lacks lambdas, for instance.
    \item This changed significantly with the modern standards, starting from \cpp{}11.
    \end{itemize}
\end{frame}


\subsection{Elements}
\begin{frame}[fragile]{Lists}
    \begin{itemize}[<+->]
    \item In \cpp{}, \emph{Iterators} are equivalent to lists in functional languages.
    \item Examples of iterators include \cppcmd{vector} and \cppcmd{array}.
    \item See~\cite{cppiter} for more information about the specific iterator
        types and the necessary prerequisites.
    \end{itemize}
\end{frame}

\begin{frame}[fragile]{lambdas}
    \begin{itemize}[<+->]
    \item \emph{Lambdas} have been introduced with \cpp{}11
    \item Syntax:
\begin{cppcode}
[v1,&v2](int v1, int v2)
    {return v1 < v2}
\end{cppcode}
    \item The \cppcmd{[]} denotes the capture-list and specifies, whether
        variables are used by value or by reference. If this is empty,
        anything is used by value.
    \item Lambdas are fully-featured \emph{functionals}, such are functions
        wrapped with \cppcmd{std::function}, and objects implementing
        \cppcmd{operator()}.
    \end{itemize}
\end{frame}

\begin{frame}[fragile]{Maps (1)}
    \uncover<+->{\begin{alertblock}{map ≠ map}
          \cppcmd{std::map} is a data-type similar to pythons \pycmd{dict} and has no
          relation to the functional concept of maps!
      \end{alertblock}}
    \uncover<+->{The following can be used instead (both from \cppcmd{<algorithm>}):}
    \begin{itemize}[<+->]
    \item \cppcmd{std::for_each}
    \item \cppcmd{std::transform}
    \end{itemize}
\uncover<+->{But they are quite different.}
\end{frame}

\begin{frame}[fragile]{Maps (2)}
    \uncover<+->{\cppcmd{std::for_each} applies a function \cppcmd{void fun(T &a)} to elements
      of an iterator containing values of type \cppcmd{T} in place:}
    
    \begin{uncoverenv}<+->
\begin{cppcode}
vector<int> a{1,2,3};
for_each(a.begin(), a.end(), 
         [](int &n){ n*=2; });
\end{cppcode}
    \end{uncoverenv}
    
    \uncover<+->{This multiplies each element in \cppcmd{a} by 2.}
\end{frame}

\begin{frame}[fragile]{Maps (3)}
    \uncover<+->{In contrast, \cppcmd{std::transform} returns a new iterator containing type
\cppcmd{U}. Thus, the function has to be \cppcmd{U func(T val)}:}

\begin{uncoverenv}<+->
\begin{cppcode}
vector<int> b{1,2,3,4};
vector<double> c(b.size(), 0.0);
transform(b.begin(), b.end(), c.begin(),
          [](int i){ return 1.0/i; });
\end{cppcode}
\end{uncoverenv}

\uncover<+->{This gives a vector c filled with the inverse elements of b.}
\uncover<+->{There are also forms of \cppcmd{transform} that merge two
  iterators (see examples in git-repo).}
\end{frame}

\begin{frame}[fragile]{Filters}
    \begin{itemize}[<+->]
    \item This is ugly
    \item No syntactic sugar as with python's list comprehensions
    \item Use \cppcmd{std::remove_if} or \cppcmd{std::remove_copy_if} from \cppcmd{<algorithm>},
    \item afterwards \cppcmd{transform}.
    \item Or make use of the \cppcmd{boost::filter_iterator} library.
    \end{itemize}
\end{frame}

\begin{frame}[fragile]{Folds}
    \begin{itemize}[<+->]
    \item \cppcmd{std::accumulate} is defined in \cppcmd{<numeric>}
    \item Takes bounds of an Iterator, and a \cppcmd{BinaryOperation}
    \item Example:
\begin{cppcode}
vector<int> a{1,2,3,4}
int b = accumulate(a.begin(), a.end(), 0); // sum
int c = accumulate(a.begin(), a.end(), 15, minus<int>());
\end{cppcode}
        \cppcmd{std::minus<int>} is defined in \cppcmd{<numeric>} as well.
    \end{itemize}
\end{frame}

\begin{frame}[fragile]{Generics and \texttt{D}}
\begin{itemize}[<+->]
    \item These are only procedural examples of functional programming.
    \item Much can be done using \emph{generic} techniques
        (\enquote{templates}).
    \item Many examples: \cite{generics}
    \item Much more to come in \cpp{}20/22 (\cite[What will Not make it into
        C+17,…]{cpp17})
        \begin{itemize}[<+->]
        \item \emph{Concepts} are kind of constraints on template parameters.
        \item \emph{Ranges} will replace iterators
        \item All of the above and more are available in the \texttt{D}
            programming language! (\url{dlang.org})
        \end{itemize}
    \end{itemize}
\end{frame}

\begin{frame}[fragile]{Generics example: Folds}
    \begin{uncoverenv}<+->
        Using \cpp{}11/14 with variadic templates, one has
\begin{cppcode}
auto sum() { return 0; }

template<typename T>
auto sum(T t) { return t; }

template<typename T, typename... Ts>
auto sum(T t, Ts... ts) { return t + sum(ts...); }
\end{cppcode}
    \end{uncoverenv}
    \begin{uncoverenv}<+->
        With new folding expression (\cite{cppfolds}):
\begin{cppcode}
template<typename T>
auto sum(const auto&... args)
   { return (args + ...); }
\end{cppcode}
    \end{uncoverenv}
\end{frame}

\begin{frame}[plain]{References}
    \printbibliography
\end{frame}

\section{The}
\subsection{end}

\begin{frame}[plain]{Thanks for listening!}{Any questions?}
    \href{https://git.f3l.de/pheerai/wtfunctional/}{Git-Repo with examples and
      slides}: \url{https://git.f3l.de/pheerai/wtfunctional/}
    
    \begin{description}
    \item[Mail:] \url{oli_r@fg4f.de}
    \item[XMPP:] \url{pheerai@im.f3l.de}
    \item[Github:] \href{https://github.com/pheerai/}{pheerai}
    \item[Misc:] Signal, Telegram,…
    \item[…or] later having some drink
    \end{description}
    \vfill
    \tiny \raggedleft Proudly typed using Lua\LaTeX{}. Slides-theme: \emph{Antibes}\\
    Fonts used are \href{github.com/mozilla/Fira}{\emph{Fira Sans}} and
    \href{leonardo-m.livejournal.com/77079.html}{\emph{Inconsolata G}}.\\
    Syntax and code highlighting with
    \href{https://github.com/gpoore/minted}{\emph{minted}} and
    \href{http://pygments.org}{\emph{pygments}}.
\end{frame}

\end{document}

%%% Local Variables:
%%% mode: latex
%%% ispell-local-dictionary: "en_GB"
%%% End: