123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506 |
- % Copyright (C) 2017 Koz Ross <koz.ross@retro-freedom.nz>
- % This work is licensed under the Creative Commons Attribution-ShareAlike 4.0
- % International License. To view a copy of this license, visit
- % http://creativecommons.org/licenses/by-sa/4.0/ or send a letter to Creative
- % Commons, PO Box 1866, Mountain View, CA 94042, USA.
- \documentclass{beamer}
- \usepackage[utf8]{inputenc}
- \usecolortheme{seahorse}
- \usefonttheme{professionalfonts}
- \usepackage{fontspec}
- \setmainfont{DejaVu Sans}
- \setbeamertemplate{navigation symbols}{}
- \usepackage{caption}
- \usepackage[font=itshape, begintext=``, endtext='']{quoting}
- \usepackage{fancyvrb}
- \usepackage{color}
- \usepackage[noend]{algpseudocode}
- \title{Hylomorphisms}
- \subtitle{Or: intermediate structures in a non-awful way}
- \titlegraphic{\includegraphics[scale=0.8]{img/logo.pdf}}
- \author{Koz Ross}
- \date{14th September, 2017}
- \begin{document}
- \begin{frame}[c]
- \titlepage{}
- \end{frame}
- \begin{frame}[c]
- \frametitle{Outline}
- \tableofcontents
- \end{frame}
- \section{Introduction}
- \begin{frame}[c]
- \frametitle{Intermediate structures}
- \pause{}
- \begin{definition}
- We say that a data structure is {\em intermediate\/} if it is used in an
- algorithm, but not given as an input or returned as an output.
- \end{definition}
- \pause{}
- \bigskip{}
- Essentially, it's a data structure which we {\em use}, but never {\em see}.
- \end{frame}
- \begin{frame}[c, fragile]
- \frametitle{An example}
- \begin{definition}
- The {\em Fibonacci numbers\/} $(F_0, F_1, \ldots)$ are a sequence of natural
- numbers, such that:\pause{}
- \begin{itemize}
- \item $F_0 = F_1 = 1$\pause{}
- \item For any $n > 1$, $F_n = F_{n - 1} + F_{n - 2}$
- \end{itemize}
- \end{definition}\pause{}
- If we wanted to write an algorithm for computing $F_n$ given an input $n$, we
- can convert this definition directly:\pause{}
-
- \bigskip{}
- \begin{algorithmic}
- \Function{$\mathrm{fib}$}{$n$}
- \If{$n = 0$ or $n = 1$}
- \State{}\Return{}$1$
- \Else{}
- \State{}\Return{}\Call{$\mathrm{fib}$}{$n - 1$} $+$ \Call{$\mathrm{fib}$}{$n - 2$}
- \EndIf{}
- \EndFunction{}
- \end{algorithmic}
- \end{frame}
- \begin{frame}[c]
- \frametitle{Why this is awful}
- Let's see what happens if we call $\mathrm{fib}(4)$:\pause{}
- \begin{enumerate}
- \item $\mathrm{fib}(3) + \mathrm{fib}(2)$\pause{}
- \item $\mathrm{fib}(2) + \mathrm{fib}(1) + \mathrm{fib}(2)$\pause{}
- \item $\mathrm{fib}(1) + \mathrm{fib}(0) + \mathrm{fib}(1) +
- \mathrm{fib}(2)$\pause{}
- \item $1 + \mathrm{fib}(0) + \mathrm{fib}(1) + \mathrm{fib}(2)$\pause{}
- \item $1 + 1 + \mathrm{fib}(1) + \mathrm{fib}(2)$\pause{}
- \item $1 + 1 + 1 + \mathrm{fib}(2)$\pause{}
- \item $1 + 1 + 1 + \mathrm{fib}(1) + \mathrm{fib}(0)$\pause{}
- \item $1 + 1 + 1 + 1 + \mathrm{fib}(0)$\pause{}
- \item $1 + 1 + 1 + 1 + 1$\pause{}
- \item $5$\pause{}
- \end{enumerate}
- That's a {\em lot\/} of wasted effort --- for example, we have to compute
- $\mathrm{fib}(2)$ twice.\pause{} Only gets worse for higher $n$!
- \end{frame}
- \begin{frame}[c]
- \frametitle{How awful is it?}
- Every call to $\mathrm{fib}(n)$ produces two recursive calls: one to
- $\mathrm{fib}(n - 1)$ and another to $\mathrm{fib}(n - 2)$. We stop when
- $n = 0, 1$.\pause{} That means that $\mathrm{fib}(n)$ requires $2^{n - 2} +
- 2^{n - 3}$ recursive calls.\pause{} This means our algorithm is
- $O(2^n)$.\pause{} This is \alert{atrocious}.\pause{}
- \bigskip{}
- One reason why it's so bad is because we waste a lot of work --- in order to
- compute $\mathrm{fib}(n - 1)$, we have to compute $\mathrm{fib}(n - 2)$, only
- to throw it away and do it again!\pause{} If only we kept a hold of
- $\mathrm{fib}(n - 2)$, we could reduce the number of recursive calls required
- from $2$ to $1$.\pause{} Let's try using an intermediate data structure for
- that\ldots
- \end{frame}
- \begin{frame}[c, fragile]
- \frametitle{Take 2}
- Let's use an array to hold the intermediate computations:\pause{}
- \bigskip
- \begin{algorithmic}
- \Function{$\mathrm{fib}^{\prime}$}{$n$}
- \State{}$\mathrm{arr} \gets$ an empty array of length $n$
- \State{}$\mathrm{arr}[0] = 1$
- \State{}$\mathrm{arr}[1] = 1$
- \For{$i \in 2,3,\ldots,n - 1$}
- \State{}$\mathrm{arr}[i] \gets \mathrm{arr}[i - 1] + \mathrm{arr}[i -
- 2]$
- \EndFor{}
- \State{}\Return{}$\mathrm{arr}[n - 1]$
- \EndFunction{}
- \end{algorithmic}\pause{}
- \bigskip
- Since we have a (nearly) $n$-length loop in $\mathrm{fib}^{\prime}(n)$, this
- is clearly $O(n)$ --- much better! All thanks to the intermediate array.
- \end{frame}
- \begin{frame}[c]
- \frametitle{Intermediate structures are {\em everywhere\/}}
- \pause{}
- \begin{itemize}
- \item Graph processing algorithms (DFS, BFS, Dijkstra's, Prim's, Kruskal's,
- \ldots)\pause{}
- \item Graphics pipeline (rasterization, translations, shading,
- \ldots)\pause{}
- \item Compilers (of any sort)\pause{}
- \item Every time you do recursion (implicitly)\pause{}
- \item And so many more\ldots
- \end{itemize}
- \pause{}
- However, it's not all brilliant --- intermediate structures have two major
- issues.
- \end{frame}
- \begin{frame}[c]
- \frametitle{Issue One: ad-hoc-ism}
- Every time we employ an intermediate data structure, we have to devise the
- algorithm `from first principles'. This has several downsides:\pause{}
-
- \begin{itemize}
- \item Correctness is harder to determine\pause{}
- \item Structure and content are entangled (no general treatment)\pause{}
- \item Incidental complexity from the structure adds to the complexity of the
- algorithm\pause{}
- \end{itemize}
- This is mostly because we're being forced to consider a specific solution
- every time we want an intermediate structure to be built up, then torn down.
- \end{frame}
- \begin{frame}[c, fragile]
- \frametitle{Issue Two: efficiency}
- Let's look at $\mathrm{fib}^{\prime}$ again:\pause{}
- \bigskip
- \begin{algorithmic}
- \Function{$\mathrm{fib}^{\prime}$}{$n$}
- \State{}$\mathrm{arr} \gets$ an empty array of length $n$
- \State{}$\mathrm{arr}[0] = 1$
- \State{}$\mathrm{arr}[1] = 1$
- \For{$i \in 2,3,\ldots,n - 1$}
- \State{}$\mathrm{arr}[i] \gets \mathrm{arr}[i - 1] + \mathrm{arr}[i -
- 2]$
- \EndFor{}
- \State{}\Return{}$\mathrm{arr}[n - 1]$
- \EndFunction{}
- \end{algorithmic}\pause{}
- \bigskip
-
- At no point in the algorithm are we interested in the whole array --- just the
- last two elements.\pause{} However, we can't get rid of any part of the
- structure until the {\em very\/} end, even though it's useless to us!
- \end{frame}
- \begin{frame}[c]
- \frametitle{Can we do better?}
- What we really want is:\pause{}
- \begin{itemize}
- \item A general way of handling {\em any\/} algorithm which involves
- intermediate structures\pause{}
- \item A guarantee of {\em some\/} correctness properties (from a
- formal/mathematical point of view)\pause{}
- \item Some way of automatically only building up as much structure as we
- need\pause{}
- \end{itemize}
- Sounds impossible, right?\pause{} However: there's a morphism for that!
- \end{frame}
- \section{Hylomorphisms}
- \begin{frame}[fragile, c]
- \frametitle{Where we last left recursion schemes\ldots}\pause{}
- \begin{Verbatim}[fontsize=\small, commandchars=\\\{\}]
- \color{gray}-- our knotting hack
- data Knot f = Tie \{ untie :: f (Knot f) \}
- \color{gray}-- pronounced `then', for easier composition
- >>> :: (a -> b) -> (b -> c) -> (a -> c)
- f >>> g = g \circ f
- type Algebra f a = f a -> a
- \color{gray}-- catamorphism - tears structures down
- cata :: Functor f => Algebra f a -> Knot f -> a
- cata f = untie >>> map (cata f) >>> f
- type Coalgebra f a = a -> f a
- \color{gray}-- anamorphism - builds structures up
- ana :: Functor f => Coalgebra f a -> a -> Knot f
- ana f = f >>> map (ana f) >>> Tie
- \end{Verbatim}
- \end{frame}
- \begin{frame}[fragile, c]
- \frametitle{Trying to use recursion schemes}
- When we use an intermediate structure, we first build it up, then tear it
- down. What would happen if we tried to write this using recursion
- schemes?\pause{}
- \begin{Verbatim}[fontsize=\small, commandchars=\\\{\}]
- \color{gray}-- what's the type of this?
- huh coalg alg = ana coalg >>> cata alg \pause{}
- huh :: Functor f => (a -> f a) -> (f b -> b) -> a -> b
- \color{gray}-- remember, (a -> f a) is Coalgebra f a
- \color{gray}-- and (f b -> b) is Algebra f b
- \end{Verbatim}
- \pause{}
- Now, {\tt huh} is a very silly name. We should really fix our terminology
- again\ldots
- \end{frame}
- \begin{frame}[fragile, c]
- \frametitle{The humble hylomorphism}
- \begin{Verbatim}[fontsize=\small, commandchars=\\\{\}]
- hylo :: Functor f => Coalgebra f a -> Algebra f b -> a -> b
- hylo f g = ana f >>> cata g
- \end{Verbatim}
- \bigskip
- The term `hylomorphism' comes from the Greek root {\em hylo\/} (meaning
- `tree'), as its behaviour can be seen as tree-like (building up is like the
- tree growing, and tearing down is like the tree being turned into
- matches).\pause{}
-
- \bigskip{}
- Note: The intermediate structure being operated on by the
- algebra and coalgebra must be {\em the same}, but the data can be different.
- \end{frame}
- \section{Using hylomorphisms}
- \begin{frame}[fragile, c]
- \frametitle{Example: mergesort}
- \pause{}
- \begin{itemize}
- \item A well-known {\em comparison-sorting\/} algorithm for arrays\pause{}
- \item An example of a {\em divide-and-conquer\/} algorithm\pause{}
- \item Relies on the following two principles:\pause{}
- \begin{enumerate}
- \item An array of length $1$ is always sorted\pause{}
- \item We can merge two sorted arrays into one sorted array\pause{}
- \end{enumerate}
- \item Relies on a three-step {\em merge procedure\/}:\pause{}
- \begin{enumerate}
- \item Create an array big enough to hold the contents of both inputs\pause{}
- \item Walk over the new array, inserting the smallest element from either
- input at each stage\pause{}
- \item When we've finished, return the result\pause{}
- \end{enumerate}
- \item Implicitly builds up a binary tree of deferred sort operations
- \end{itemize}
- \end{frame}
- \begin{frame}[fragile,c]
- \frametitle{The merge procedure, in detail}
- \begin{algorithmic}
- \Function{$\mathrm{merge}$}{$a_1, a_2$}
- \State{}$n \gets$ \Call{$\mathrm{len}$}{$a_1$} $+$ \Call{$\mathrm{len}$}{$a_2$}
- \State{}$a \gets$ a new array of length $n$
- \State{}$f_1, f_2 \gets 0$
- \For{$i \in 0,1,\ldots,n - 1$}
- \If{$f_1 =$ \Call{$\mathrm{len}$}{$a_1$}}
- \State{}$a[i] = a_2[f_2]$
- \State{}$f_2 \gets f_2 + 1$
- \ElsIf{$f_2 =$ \Call{$\mathrm{len}$}{$a_2$}}
- \State{}$a[i] \gets a_1[f_1]$
- \State{}$f_1 \gets f_1 + 1$
- \Else{}
- \State{}$e \gets \min\{a_1[f_1], a_2[f_2]\}$
- \State{}$a[i] \gets e$
- \State{}Increment corresponding $f$
- \EndIf{}
- \EndFor{}
- \State{}\Return{}$a$
- \EndFunction{}
- \end{algorithmic}
- \end{frame}
- \begin{frame}[fragile,c]
- \frametitle{Viewing mergesort as a hylomorphism}
- \begin{itemize}
- \item When we do the `divide' step of mergesort, we build up a binary
- tree:\pause{}
- \begin{itemize}
- \item The leaves are singleton arrays\pause{}
- \item The internal nodes are deferred merges of the children\pause{}
- \end{itemize}
- \item Once we've built up this tree, we can tear it down bottom-up by
- realizing the deferred computations based on their children\pause{}
- \item At the end, we have a single, sorted array, and the tree is
- gone\pause{}
- \end{itemize}
- \bigskip{}
- Let's see how this works in practice: we will sort the array {\tt [4, 2, 6,
- 1]}.
- \end{frame}
- \begin{frame}[fragile,c]
- \frametitle{Worked example}
- \begin{overprint}
- \onslide<1>\centerline{\includegraphics[scale=1]{img/merge1.pdf}}%
- \onslide<2>\centerline{\includegraphics[scale=1]{img/merge2.pdf}}%
- \onslide<3>\centerline{\includegraphics[scale=1]{img/merge3.pdf}}%
- \onslide<4>\centerline{\includegraphics[scale=1]{img/merge4.pdf}}%
- \onslide<5>\centerline{\includegraphics[scale=1]{img/merge5.pdf}}%
- \onslide<6>\centerline{\includegraphics[scale=1]{img/merge6.pdf}}%
- \onslide<7>\centerline{\includegraphics[scale=1]{img/merge7.pdf}}%
- \onslide<8>\centerline{\includegraphics[scale=1]{img/merge8.pdf}}%
- \end{overprint}
- \end{frame}
- \begin{frame}[fragile,c]
- \frametitle{Putting it into a hylo}
- First, we will need an intermediate tree structure:\pause{}
- \begin{Verbatim}[commandchars=\\\{\}]
- data Tree a = Leaf a | Internal (Tree a) (Tree a)
- \end{Verbatim}
- \pause{}
- It then needs a slight change so we can use it with recursion schemes:\pause{}
- \begin{Verbatim}[commandchars=\\\{\}]
- data ITree a s = Leaf a | Internal s s
- \end{Verbatim}
- \pause{}
- Lastly, we need a {\tt Functor} instance for it. This can be derived
- automatically (both in theory {\em and\/} practice).\pause{}
- \begin{Verbatim}[commandchars=\\\{\}]
- instance Functor (ITree a) where \pause{}
- map :: (s -> t) -> ITree a s -> ITree a t\pause{}
- map _ (Leaf a) = Leaf a \color{gray}-- nothing to do\pause{}
- map f (Internal l r) = Internal (f l) (f r)
- \end{Verbatim}
- \end{frame}
- \begin{frame}[fragile,c]
- \frametitle{A suitable coalgebra}
- Our coalgebra will represent one `step' in the dividing process:\pause{}
- \begin{itemize}
- \item If we get given an array of length $1$, we just make a {\tt Leaf}
- storing it\pause{}
- \item Otherwise, we make an {\tt Internal}, and send half of the array into
- each child\pause{}
- \end{itemize}
- \begin{Verbatim}[commandchars=\\\{\}]
- \color{gray}-- Vector a is an array of a
- breakDown :: Coalgebra (ITree (Vector a)) (Vector a)\pause{}
- \color{gray}-- breakDown :: Vector a -> ITree (Vector a)\pause{}
- breakDown v = case (length v) of \pause{}
- 1 -> Leaf v\pause{}
- x -> let half = x `div` 2 in
- Internal (slice v 0 half) (slice v half (x - half))
- \end{Verbatim}
- \end{frame}
- \begin{frame}[fragile,c]
- \frametitle{A suitable algebra}
- Our algebra will represent one `step' in the conquering process:\pause{}
- \begin{itemize}
- \item If we have a {\tt Leaf}, we just return the array as-is\pause{}
- \item If we have an {\tt Internal}, merge the arrays in its left and right
- children\pause{}
- \end{itemize}
- We will assume we have {\tt merge} defined appropriately --- its details don't
- matter for this.\pause{}
- \begin{Verbatim}[commandchars=\\\{\}]
- mergeAlg :: Ord a => Algebra (ITree (Vector a)) (Vector a)\pause{}
- \color{gray}-- mergeAlg :: Ord a => ITree (Vector a) -> Vector a\pause{}
- mergeAlg (Leaf v) = v\pause{}
- mergeAlg (Internal v1 v2) = merge v1 v2
- \end{Verbatim}
- \end{frame}
- \begin{frame}[fragile,c]
- \frametitle{Putting it all together}
- \begin{Verbatim}[commandchars=\\\{\}]
- mergeSort :: Ord a => Vector a -> Vector a
- mergeSort v\pause{}
- | length v == 0 = v \color{gray}-- no point sorting an empty array\pause{}
- | otherwise = hylo breakDown mergeAlg v
- \end{Verbatim}
- \pause{}
- \bigskip{}
- \alert{Yay!}
- \end{frame}
- \begin{frame}[fragile, c]
- \frametitle{Reviewing our goals}
- \pause{}
- \begin{itemize}
- \item Generalization of all divide-and-conquer algorithms (and almost all
- intermediate structure work!)\pause{}
- \item Strong correctness guarantees:\pause{}
- \begin{itemize}
- \item Won't miss any items in the teardown\pause{}
- \item No edge-cases for `lop-sided' structures\pause{}
- \item No `funny stuff' --- no side effects, no structural wrecking we
- didn't ask for\pause{}
- \end{itemize}
- \item Efficiency still a problem --- until we finish {\tt ana f} we can't
- start on {\tt cata g}!\pause{}
- \end{itemize}
- Luckily for us, Meijer and Hutton solved that last one in their `Bananas in
- Space' paper in 1995:\pause{}
- \begin{Verbatim}[fontsize=\small,commandchars=\\\{\}]
- hylo' :: Functor f => Coalgebra f a -> Algebra f b -> a -> b
- hylo' f g = f >>> map (hylo' f g) >>> g
- \end{Verbatim}
- \pause{}
- \alert{Result:} We have everything we wanted, and recursion schemes still rule!
- \end{frame}
- \section{Questions}
- \begin{frame}[fragile, c]
- \frametitle{Questions?}
- \begin{center}
- \includegraphics[scale=0.27]{img/questions.pdf}
- \end{center}
- \end{frame}
- \end{document}
|