Permalink
Switch branches/tags
Nothing to show
Find file
Fetching contributors…
Cannot retrieve contributors at this time
313 lines (277 sloc) 9.8 KB
\documentclass[18pt]{beamer}
\usepackage[T1]{fontenc}
\usepackage[protrusion=true,expansion=true]{microtype}
%usepackage[minionint,mathlf]{MinionPro}
%\usepackage[sc,osf]{mathpazo}
\usepackage{listings}
\usepackage{diagrams}
%\renewcommand{\sfdefault}{Myriad-LF}
\newcommand{\fto}{\;\Rightarrow\;}
\definecolor{gray_ulisses}{gray}{0.55}
\definecolor{castanho_ulisses}{rgb}{0.71,0.33,0.14}
\definecolor{preto_ulisses}{rgb}{0.41,0.20,0.04}
\definecolor{green_ulises}{rgb}{0.2,0.75,0}
\lstdefinelanguage{HaskellUlisses} {
basicstyle=\ttfamily,
sensitive=true,
morecomment=[l][\color{gray_ulisses}\ttfamily]{--},
morecomment=[s][\color{gray_ulisses}\ttfamily]{\{-}{-\}},
morestring=[b]",
stringstyle=\color{red},
showstringspaces=false,
%numberstyle=,
numberblanklines=true,
showspaces=false,
breaklines=true,
showtabs=false,
emph=
{[1]
FilePath,IOError,abs,acos,acosh,all,and,any,appendFile,approxRational,asTypeOn,
asinh,atan,atan2,atanh,basicIORun,break,catch,ceiling,chr,compare,concat,concatMap,
const,cos,cosh,curry,cycle,decodeFloat,denominator,digitToInt,div,divMod,drop,
dropWhile,either,elem,encodeFloat,enumFrom,enumFromThen,enumFromThenTo,enumFromTo,
error,even,exp,exponent,fail,filter,flip,floatDigits,floatRadix,floatRange,floor,
fmap,foldl,foldl1,foldr,foldr1,fromDouble,fromEnum,fromInt,fromInteger,fromIntegral,
fromRational,fst,gcd,getChar,getContents,getLine,head,id,inRange,index,init,intToDigit,
interact,ioError,isAlpha,isAlphaNum,isAscii,isControl,isDenormalized,isDigit,isHexDigit,
isIEEE,isInfinite,isLower,isNaN,isNegativeZero,isOctDigit,isPrint,isSpace,isUpper,iterate,
last,lcm,length,lex,lexDigits,lexLitChar,lines,log,logBase,lookup,map,mapM,mapM_,max,
maxBound,maximum,maybe,min,minBound,minimum,mod,negate,not,notElem,null,numerator,odd,
or,ord,otherwise,pi,pred,primExitWith,print,product,properFraction,putChar,putStr,putStrLn,quot,
quotRem,range,rangeSize,read,readDec,readFile,readFloat,readHex,readIO,readInt,readList,readLitChar,
readLn,readOct,readParen,readSigned,reads,readsPrec,realToFrac,recip,rem,repeat,replicate,return,
reverse,round,scaleFloat,scanl,scanl1,scanr,scanr1,seq,sequence,sequence_,show,showChar,showInt,
showList,showLitChar,showParen,showSigned,showString,shows,showsPrec,significand,signum,sin,
sinh,snd,span,splitAt,sqrt,subtract,succ,sum,tail,take,takeWhile,tan,tanh,threadToIOResult,toEnum,
toInt,toInteger,toLower,toRational,toUpper,truncate,uncurry,undefined,unlines,until,unwords,unzip,
unzip3,userError,words,writeFile,zip,zip3,zipWith,zipWith3,listArray,doParse
},
emphstyle={[1]\color{blue}},
emph=
{[2]
Bool,Char,Double,Either,Float,IO,Integer,Int,Maybe,Ordering,Rational,Ratio,ReadS,ShowS,String,
Word8,InPacket
},
emphstyle={[2]\color{castanho_ulisses}},
emph=
{[3]
case,class,data,deriving,do,else,if,import,in,infixl,infixr,instance,let,
module,of,primitive,then,type,where
},
emphstyle={[3]\color{preto_ulisses}\textbf},
emph=
{[4]
quot,rem,div,mod,elem,notElem,seq
},
emphstyle={[4]\color{castanho_ulisses}\textbf},
emph=
{[5]
EQ,False,GT,Just,LT,Left,Nothing,Right,True,Show,Eq,Ord,Num
},
emphstyle={[5]\color{preto_ulisses}\textbf}
}
\lstnewenvironment{code}
{\hrulefill \lstset{language=HaskellUlisses}}{}
\usepackage{textcomp}
\usepackage{graphicx}
\usepackage{semantic}
\usetheme{default}
\usefonttheme{professionalfonts}
%\usefonttheme[]{structuresmallcapsserif}
\begin{document}
\frame{
\begin{center}
Applicative programming\\
with effects\\
\end{center}
}
\begin{frame}[fragile]
The Functor definition\\
\begin{code}
class Functor f where
fmap :: (a -> b) -> f a -> f b
\end{code}
\end{frame}
\begin{frame}[fragile] \frametitle{Category}
A Category is:\\
\begin{gather*}
\text{A collection of objects:} \quad A, B, C, \dotsc\\
\text{A collection of morphisms:} \quad f, g, h, \dotsc\\
\end{gather*}
Morphisms lies between objects: $f \colon A \to B$,\\
For any object $A$, a morphism $Id_A \colon A \to A$,\\
For any two morphisms, $f \colon A \to B, \; g \colon B \to C$ a
composition $g \circ f \colon A \to C$\\
The composition follows the assiociative and unit laws.
\end{frame}
\begin{frame}[fragile] \frametitle{Example}
A Directed graph is a category:\\
Objects are the vertices $x, y, z \in V$\\
If there is a edge $e \in E$ with $s(e) = x$ and $t(e) = y$ then $e
\colon x \to y$ is a morphism.\\
The identity morphism is vacuously true.\\
Paths play the role of compositions.\\--\\
\emph{Other Examples:} vector spaces, monoids, groups, topological
spaces, etc.
\end{frame}
\begin{frame}[fragile] \frametitle{Functor}
If $\mathcal{C}$ and $\mathcal{D}$ are categories, then $F \colon
\mathcal{C} => \mathcal{D}$ iff:
\begin{itemize}
\item $F$ maps an object $A$ to $F A$
\item $F$ maps a morphism $f \colon A \to B$ to $F f \colon F A \to
F B$
\item For any object $A$, $F \; Id_A = Id_{F A}$
\item For all morphisms $f, g$: \quad $F (g \circ f) = F g \circ F f$
\end{itemize}
$F$ is then called a \emph{functor}.
\end{frame}
\begin{frame}[fragile] \frametitle{Example}
The (standard) instance of a functor\\
\begin{code}
class Functor [] where
fmap f [] = []
fmap f (x : xs) = f x : (fmap f xs)
\end{code}
\end{frame}
\begin{frame}[fragile] \frametitle{Leading example}
What we have without Applicative Functors:\\
\begin{code}
data Exp v = Var v
| Val Int
| Add (Exp v) (Exp v)
eval :: Exp v -> Env v -> Int
eval (Var x) env = fetch x env
eval (Val i) env = i
eval (Add p q) env = eval p env + eval q env
\end{code}
Not very pretty - nor general
\end{frame}
\begin{frame}[fragile] \frametitle{S, K combinators}
We can do better:\\
\begin{code}
eval :: Exp v -> Env v -> Int
eval (Var x) = fetch x
eval (Val i) = K i
eval (Add p q) = K (+) 'S' eval p 'S'eval q
\end{code}
where\\
\begin{code}
K :: a -> env -> a
K x env = x
S :: (env -> a -> b)
-> (env -> a) -> (env -> b)
S ef es env = (ef env) (es env)
\end{code}
\end{frame}
\begin{frame}[fragile] \frametitle{Applicative Functor}
\begin{align*}
\mathbf{infixl} & \; 4 \; \circledast\\
\mathbf{class} & \; \mathrm{Applicative} \; f \; \mathbf{where}\\
\quad & \mathrm{pure} \; :: \; a -> f a\\
\quad & (\circledast) \; :: \; f (a -> b) -> f a -> f b
\end{align*}
Rules:
\begin{align*}
\mathbf{Identity:} \quad & \mathrm{pure} \; \mathrm{id} \;
\circledast u = u\\
\mathbf{Composition:} \quad & \mathrm{pure} \; (\cdot) \circledast u
\circledast v \circledast w = u \circledast (v \circledast w)\\
\mathbf{Homomorphism:} \quad & \mathrm{pure} \; f \circledast x =
\mathrm{pure} \; (\lambda f \rightarrow f x) \circledast f\\
\mathbf{Interchange:} \quad & u \circledast \mathrm{pure} \; x = \mathrm{pure} \;
(\lambda f \rightarrow f x) \circledast u\\
\end{align*}
%Dollar sign
\end{frame}
\begin{frame}[fragile] \frametitle{Recapturing the Functor}
\begin{code}
(<$>) :: Applicative f =>
(a -> b) -> f a -> f b
f <$> u = pure f <*> u
\end{code}
Note this is the functor type.
\end{frame}
\begin{frame}[fragile]\frametitle{Canonical form:}
\centering{
pure $f \circledast u_1 \circledast \ldots \circledast u_n \equiv |[f u_1 \ldots u_n|]$\\
and in practice\\
\begin{code}
pure f <*> u1 <*> ... <*> un
\end{code}}
\end{frame}
\begin{frame}[fragile] \frametitle{Leading example revisited:}
\begin{code}
instance Applicative ((->) env) where
pure x = \env -> x --K
ef <*> ex = \env -> (ef env)(ex env) -- S
\end{code}
So now:\\
\begin{code}
eval :: Exp v -> Env v -> Int
eval (Var x) = fetch x
eval (Val i) = pure i
eval (Add p q) =
pure (+) <*> (eval p) <*> (eval q)
\end{code}
\end{frame}
\begin{frame}[fragile] \frametitle{Applicative distributor for lists:}
\begin{align*}
&\mathrm{dist} :: \mathrm{Applicative} \; f &=>& [f a] -> f [a]\\
&\mathrm{dist} [] &=& |[ [] |]\\
&\mathrm{dist} (v : vs) &=& |[ (:) v (\mathrm{dist} \; vs) |]
\end{align*}
Example:\\
\begin{code}
flakeyMap :: (a -> Maybe b)
-> [a] -> Maybe [b]
flakeyMap f ss = dist (fmap f ss)
\end{code}
\end{frame}
\begin{frame}[fragile] \frametitle{Traverse and traversable - a better choice:}
\begin{align*}
&\mathrm{traverse} \; :: \; \mathrm{Applicative} \; f &=> (a -> f b) -> [a] -> f [b]\\
&\mathrm{traverse} \; f \; [] &= |[ [] |]\\
&\mathrm{traverse} \; f \; (x :xs) &= |[(:)\; (f \; x)(\mathrm{traverse} \; f \; xs)|]
\end{align*}
\begin{code}
class Traversable t where
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
dist :: Applicative f => t (f a) -> r (t a)
dist = traverse id
\end{code}
Through this and the type system we can now create traversable functions
\end{frame}
\begin{frame}[fragile]\frametitle{Monoids and applicative functors}
\begin{align*}
&\mathbf{class} \; \mathrm{Monoid} \; o \; \mathbf{where}\\
\emptyset &:: o\\
(\oplus) &:: o -> o -> o
\end{align*} \\
These induce an applicative functor:\\
$\mathbf{newtype} \; \mathrm{Accy} \; o\; a = \mathrm{Acc} \{\mathrm{acc} \; :: \;o \}$
\begin{align*}
&\mathbf{instance} \; \mathrm{Monoid} \; o &=>& \mathrm{Applicative} (\mathrm{Accy}\; o) \; \mathbf{where}\\
&\mathrm{pure} \_ &=& \mathrm{Acc} \; \emptyset\\
&\mathrm{Acc} \; o_1 \circledast \mathrm{Acc} \; o_2 &=& \mathrm{Acc}(o_1 \oplus o_2)
\end{align*}
\end{frame}
\begin{frame}[fragile] \frametitle{The result}
accumulate :: (Traversable t, Monoid o) $=>$ (a $->$ o) $->$ t a $->$ o
accumulate f = acc $\cdot$ traverse (Acc $\cdot$ f)
\end{frame}
\begin{frame} \frametitle{Mighty}
newtype Mighty = Might\{might :: Bool \}
\begin{align*}
\mathbf{instance} \; &\mathrm{Monoid \; Mighty} \; \mathbf{where}\\
&\emptyset &=& \mathrm{Might} \; \mathrm{False}\\
&\mathrm{Might}\; x \oplus \mathrm{Might}\; y &=& \mathrm{Might} (x \lor y)
\end{align*}
any :: Traversable t $=>$ (a $->$ Bool) $->$ t a $->$ Bool\\
any p = might $\cdot$ accumulate (Might $\cdot$ p)
\end{frame}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: