\documentclass[]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\else % if luatex or xelatex
\ifxetex
\usepackage{mathspec}
\usepackage{xltxtra,xunicode}
\else
\usepackage{fontspec}
\fi
\defaultfontfeatures{Mapping=tex-text,Scale=MatchLowercase}
\newcommand{\euro}{€}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{\usepackage{microtype}}{}
\usepackage[margin=1in]{geometry}
\usepackage{color}
\usepackage{fancyvrb}
\newcommand{\VerbBar}{|}
\newcommand{\VERB}{\Verb[commandchars=\\\{\}]}
\DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}}
% Add ',fontsize=\small' for more characters per line
\newenvironment{Shaded}{}{}
\newcommand{\AlertTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
\newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.49,0.56,0.16}{#1}}
\newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\BuiltInTok}[1]{#1}
\newcommand{\CharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\CommentTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textit{#1}}}
\newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.53,0.00,0.00}{#1}}
\newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
\newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.56,0.13,0.00}{#1}}
\newcommand{\DecValTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.73,0.13,0.13}{\textit{#1}}}
\newcommand{\ErrorTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
\newcommand{\ExtensionTok}[1]{#1}
\newcommand{\FloatTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.02,0.16,0.49}{#1}}
\newcommand{\ImportTok}[1]{#1}
\newcommand{\InformationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
\newcommand{\NormalTok}[1]{#1}
\newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.40,0.40,0.40}{#1}}
\newcommand{\OtherTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{#1}}
\newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.74,0.48,0.00}{#1}}
\newcommand{\RegionMarkerTok}[1]{#1}
\newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.73,0.40,0.53}{#1}}
\newcommand{\StringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\VariableTok}[1]{\textcolor[rgb]{0.10,0.09,0.49}{#1}}
\newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\WarningTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\ifxetex
\usepackage[setpagesize=false, % page size defined by xetex
unicode=false, % unicode breaks when used with xetex
xetex]{hyperref}
\else
\usepackage[unicode=true]{hyperref}
\fi
\hypersetup{breaklinks=true,
bookmarks=true,
pdfauthor={Justin Le},
pdftitle={The Const Applicative and Monoids},
colorlinks=true,
citecolor=blue,
urlcolor=blue,
linkcolor=magenta,
pdfborder={0 0 0}}
\urlstyle{same} % don't use monospace font for urls
% Make links footnotes instead of hotlinks:
\renewcommand{\href}[2]{#2\footnote{\url{#1}}}
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
\setlength{\emergencystretch}{3em} % prevent overfull lines
\setcounter{secnumdepth}{0}
\title{The Const Applicative and Monoids}
\author{Justin Le}
\date{May 8, 2018}
\begin{document}
\maketitle
\emph{Originally posted on
\textbf{\href{https://blog.jle.im/entry/const-applicative-and-monoids.html}{in
Code}}.}
The Applicative typeclass has a somewhat infamous reputation for having opaque
laws. There are a lot of great
\href{https://wiki.haskell.org/Typeclassopedia\#Alternative_formulation}{alternative}
\href{https://www.reddit.com/r/haskell/comments/2lompe/where_do_the_applicative_laws_come_from/clws90h/}{rephrasing}
of these laws, from many different approaches. For this post, however, I want to
talk about Applicative in terms of one of my favorites: \texttt{Const}.
\hypertarget{const}{%
\section{Const}\label{const}}
The \texttt{Const} data type from the standard libraries is relatively simple as
far as newtypes go:
\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{newtype} \DataTypeTok{Const}\NormalTok{ w a }\FunctionTok{=} \DataTypeTok{Const}\NormalTok{ \{}\OtherTok{ getConst ::}\NormalTok{ w \}}
\end{Highlighting}
\end{Shaded}
However, let's look at a less polymorphic version, \texttt{IntConst}, which is
essentially \texttt{Const\ Int}:\footnote{Note that if you want to play along in
ghci, you should give this a \texttt{Show} instance by typing
\texttt{deriving\ (Show)} after the data declaration}
\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{newtype} \DataTypeTok{IntConst}\NormalTok{ a }\FunctionTok{=} \DataTypeTok{IntConst}\NormalTok{ \{}\OtherTok{ getIntConst ::} \DataTypeTok{Int}\NormalTok{ \}}
\end{Highlighting}
\end{Shaded}
For a \texttt{IntConst\ a}, the \texttt{a} is a \emph{phantom} type parameter.
This means that there are not necessarily any values of type \texttt{a} in a
value of type \texttt{IntConst\ a}. In modern GHC with PolyKinds, this means
that \texttt{a} might not even be a type that can have values --- you might
have, say, a value of type \texttt{IntConst\ Maybe}, or a value of type
\texttt{IntConst\ Monad}, and GHC would be perfectly happy.
\texttt{IntConst} admits a straightforward \texttt{Functor} instance that is a
lot like the \texttt{Functor} instance for \texttt{Proxy} and
\texttt{Either\ e}:
\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{instance} \DataTypeTok{Functor} \DataTypeTok{IntConst} \KeywordTok{where}
\NormalTok{ fmap _ (}\DataTypeTok{IntConst}\NormalTok{ w) }\FunctionTok{=} \DataTypeTok{IntConst}\NormalTok{ w}
\end{Highlighting}
\end{Shaded}
In fact, sometimes I like to refer to \texttt{Const\ w\ a} as ``an
\texttt{Either\ w\ a} with only \texttt{Left}, no \texttt{Right}''. The
\texttt{Functor} instance reflects this pretty well:
\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{instance} \DataTypeTok{Functor}\NormalTok{ (}\DataTypeTok{Either}\NormalTok{ e) }\KeywordTok{where}
\NormalTok{ fmap _ (}\DataTypeTok{Left}\NormalTok{ e) }\FunctionTok{=} \DataTypeTok{Left}\NormalTok{ e }\CommentTok{-- just like 'Const'}
\NormalTok{ fmap f (}\DataTypeTok{Right}\NormalTok{ x) }\FunctionTok{=} \DataTypeTok{Right}\NormalTok{ (f x) }\CommentTok{-- who cares}
\end{Highlighting}
\end{Shaded}
However, the \texttt{Applicative} instance of \texttt{IntConst} is one of my
favorite things about it. Let's try to imagine how we'd write it.
First of all, let's look at the types of the functions we need:
\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{pure}\OtherTok{ ::}\NormalTok{ a }\OtherTok{->} \DataTypeTok{IntConst}\NormalTok{ a}
\OtherTok{(<*>) ::} \DataTypeTok{IntConst}\NormalTok{ (a }\OtherTok{->}\NormalTok{ b) }\OtherTok{->} \DataTypeTok{IntConst}\NormalTok{ a }\OtherTok{->} \DataTypeTok{IntConst}\NormalTok{ b}
\end{Highlighting}
\end{Shaded}
Now, remember that \texttt{IntConst}'s type parameter is phantom, so we don't
have any actual values of type \texttt{a\ -\textgreater{}\ b}, \texttt{a}, or
\texttt{b} involved. An \texttt{IntConst\ a}, for any \texttt{a}, is really just
an \texttt{Int}. Essentially, once we strip out the newtype wrapper shenanigans
(replacing \texttt{IntConst\ a} with its contents, \texttt{Int}), we just get:
\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{pure}\OtherTok{ ::}\NormalTok{ a }\OtherTok{->} \DataTypeTok{Int}
\OtherTok{(<*>) ::} \DataTypeTok{Int} \OtherTok{->} \DataTypeTok{Int} \OtherTok{->} \DataTypeTok{Int}
\end{Highlighting}
\end{Shaded}
We now have a few options on how to implement these. Let's try one and see if it
works:
\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{instance} \DataTypeTok{Applicative} \DataTypeTok{IntConst} \KeywordTok{where}
\NormalTok{ pure _ }\FunctionTok{=} \DataTypeTok{IntConst} \DecValTok{42}
\DataTypeTok{IntConst}\NormalTok{ x }\FunctionTok{<*>} \DataTypeTok{IntConst}\NormalTok{ _ }\FunctionTok{=} \DataTypeTok{IntConst}\NormalTok{ x}
\end{Highlighting}
\end{Shaded}
A perfectly reasonable implementation, right? Our Applicative instance
type-checks. And if it type-checks, ship it! Time to call it a day and go home,
right?
Not quite.
\hypertarget{applicative}{%
\section{Applicative}\label{applicative}}
Let's take a detour through the essense of the \texttt{Applicative} typeclass.
Or, at least, one particular interpretation of it that makes sense for instances
that represent some sort of effectful action.
The essence of Applicative, to me, is a way to combine values representing some
sort of ``effect'' in a sane way. In Haskell, we often talk about data types as
representing/describing some sort of effects. Applicative lets us combine
(``sequence'') them in a way that allows us to write powerful generic
combinators.
One way to look at it is as a generalization of \texttt{fmap} to taking two
parameters:
\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{fmap1 ::}\NormalTok{ (a }\OtherTok{->}\NormalTok{ b ) }\OtherTok{->} \DataTypeTok{F}\NormalTok{ a }\OtherTok{->} \DataTypeTok{F}\NormalTok{ b}
\OtherTok{fmap2 ::}\NormalTok{ (a }\OtherTok{->}\NormalTok{ b }\OtherTok{->}\NormalTok{ c) }\OtherTok{->} \DataTypeTok{F}\NormalTok{ a }\OtherTok{->} \DataTypeTok{F}\NormalTok{ b }\OtherTok{->} \DataTypeTok{F}\NormalTok{ c}
\end{Highlighting}
\end{Shaded}
\texttt{fmap} alone lets you take a single \texttt{F\ a} and transform it into
an \texttt{F\ b}. \texttt{fmap2} (or, \texttt{liftA2} in the standard libraries)
is a way of taking \emph{two} \texttt{F}-values and squishing them into one fat
\texttt{F} value.
It does this by letting us talk about combining the \emph{effects} of an
\texttt{F\ a}, independent of the \texttt{a} (the result). For example,
\texttt{sequenceA\_}:
\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{sequenceA_ ::} \DataTypeTok{Applicative}\NormalTok{ f }\OtherTok{=>}\NormalTok{ [f a] }\OtherTok{->}\NormalTok{ f ()}
\end{Highlighting}
\end{Shaded}
Basically will take a list of \texttt{f\ a}s, and return a new \texttt{f\ ()}
that has \emph{all} of the effects of the \texttt{f\ a}s in the list.
To do this sensibly, we need also to talk about a ``no-op'' value:
\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{pure}\OtherTok{ ::}\NormalTok{ a }\OtherTok{->} \DataTypeTok{F}\NormalTok{ a}
\end{Highlighting}
\end{Shaded}
\texttt{pure\ x} is intended to be a no-op with ``no effects''.
With this, we can say something about the behavior of
\texttt{\textless{}*\textgreater{}} or \texttt{fmap2} or \texttt{liftA2}.
Namely:
\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
The effects of \texttt{f\ \textless{}*\textgreater{}\ x} must have the effects
of \texttt{f} once \emph{and} the effects of \texttt{x} once -- no more, and
no less.
\item
\texttt{pure}'s results must have no ``effects'', and so if used with
\texttt{\textless{}*\textgreater{}}, introduces no extra effects:
\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{pure f }\FunctionTok{<*>}\NormalTok{ x }\FunctionTok{=}\NormalTok{ fmap f x}
\NormalTok{f }\FunctionTok{<*>}\NormalTok{ pure x }\FunctionTok{=}\NormalTok{ fmap (}\FunctionTok{$}\NormalTok{ x) f}
\end{Highlighting}
\end{Shaded}
(Remember that \texttt{fmap} is not allowed to affect ``effects'' in any way)
\item
Combining effects must be associative.
\end{enumerate}
With this guarantee, we can write \texttt{sequenceA\_} in a polymorphic way:
\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{sequenceA_ ::} \DataTypeTok{Applicative}\NormalTok{ f }\OtherTok{=>}\NormalTok{ [f a] }\OtherTok{->}\NormalTok{ f ()}
\NormalTok{sequenceA_ [] }\FunctionTok{=}\NormalTok{ pure ()}
\NormalTok{sequenceA_ (x}\FunctionTok{:}\NormalTok{xs) }\FunctionTok{=}\NormalTok{ x }\FunctionTok{*>}\NormalTok{ sequenceA_ xs}
\end{Highlighting}
\end{Shaded}
And we can say with certainty that:
\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\tightlist
\item
Each ``effect'' of each value in the \texttt{{[}f\ a{]}} will be executed
\emph{exactly} once: no more, and no less.
\item
\texttt{sequenceA\_} of an empty list has no effects.
\end{enumerate}
This makes \texttt{sequenceA\_} a \emph{useful} combinator. The fact that we can
talk about how \texttt{sequenceA\_} behaves for all Applicative instances makes
it something that is \emph{worth} defining. If you use \texttt{sequenceA\_} for
your type, you can do it knowing that it will behave in a well-defined way: it
\emph{must} execute every action once (no more, and no less), and sequencing an
empty list \emph{must} have no effects.
If it weren't for those Applicative laws and expectations, \texttt{sequenceA\_}
would be a pretty useless function. It might completely ignore all effects, or
it might perform some of the effects multiple times\ldots{}who knows! The fact
that we have Applicative laws and expectations means we can look at the
implementation of \texttt{sequenceA\_} and know with certainty (and make bold
claims about) how \texttt{sequenceA\_} combines effects.
For example, we can always make the program substitution:
\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{sequenceA_ xs }\FunctionTok{*>}\NormalTok{ sequenceA_ ys}
\CommentTok{-- can be substituted with}
\NormalTok{sequenceA_ (xs }\FunctionTok{++}\NormalTok{ ys)}
\end{Highlighting}
\end{Shaded}
If \texttt{sequenceA\_} combines all the effects in \texttt{xs} once, and
\texttt{sequenceA\_} combines all the effects in \texttt{ys} once, and
\texttt{*\textgreater{}} combines the effects of either side once, then this is
a \emph{legal substitution} that doesn't change what your program does.
However, if the \texttt{Applicative} instance doesn't have any rules, we can't
do this. For example, the original form uses \texttt{pure\ ()} \emph{twice}
(once for each list's \texttt{{[}{]}} end), and the second form uses
\texttt{pure\ ()} \emph{once} (since there's only one list). If
\texttt{pure\ ()} was allowed to have effects\ldots{}then the first version
would have more effects than the second.
\hypertarget{back-to-const}{%
\section{Back to Const}\label{back-to-const}}
With this new information in mind, let's revisit our instance for
\texttt{IntConst}.
In order for \texttt{IntConst}'s Applicative instance to behave meaningfully,
and in order to be able to match with user expectations of \texttt{Applicative}
instance, you need to make sure it follows the basic principles I mentioned
earlier (the effects of \texttt{f\ \textless{}*\textgreater{}\ x} has the
effects of \texttt{f} and \texttt{x} exactly once, and the properties about
\texttt{pure}).
We haven't defined what the ``effects'' of \texttt{IntConst} are yet, but let's
at least look at if our \texttt{pure} behaves sensibly with
\texttt{\textless{}*\textgreater{}}. Namely, let's check
\texttt{pure\ f\ \textless{}*\textgreater{}\ x\ =\ fmap\ f\ x}.
Note that this is a meaningful starting point because \texttt{fmap}'s definition
is \emph{fixed}. For any type, there is \emph{at most one} possible
\texttt{fmap} that is legal and lawful --- and in Haskell, we only have to check
that \texttt{fmap\ id} leaves all inputs unchanged.\footnote{There are other
laws, but because of parametric polymorphism in Haskell, we know they must be
true if and only if \texttt{fmap\ id\ =\ id}.}
With that out of the way, let's check our
\texttt{pure\ f\ \textless{}*\textgreater{}\ x\ =\ fmap\ f\ x} law with a simple
example for \texttt{x}\ldots{}say, \texttt{IntConst\ 5}. On the left hand side,
we have:
\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{-- pure _ = IntConst 42}
\CommentTok{-- IntConst x <*> InstConst _ = IntConst x}
\NormalTok{pure f }\FunctionTok{<*>} \DataTypeTok{IntConst} \DecValTok{5} \FunctionTok{=} \DataTypeTok{IntConst} \DecValTok{42} \FunctionTok{<*>} \DataTypeTok{IntConst} \DecValTok{5}
\FunctionTok{=} \DataTypeTok{IntConst} \DecValTok{42}
\end{Highlighting}
\end{Shaded}
On the right hand side, we have:
\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{-- fmap f (IntConst x) = IntConst x}
\NormalTok{fmap f (}\DataTypeTok{IntConst} \DecValTok{5}\NormalTok{) }\FunctionTok{=} \DataTypeTok{IntConst} \DecValTok{5}
\end{Highlighting}
\end{Shaded}
It is clear that this definition does not work, since \texttt{IntConst\ 42} is
not the same as \texttt{IntConst\ 5}.
What if we defined:
\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{instance} \DataTypeTok{Applicative} \DataTypeTok{IntConst} \KeywordTok{where}
\NormalTok{ pure _ }\FunctionTok{=} \DataTypeTok{IntConst} \DecValTok{42}
\DataTypeTok{IntConst}\NormalTok{ _ }\FunctionTok{<*>} \DataTypeTok{IntConst}\NormalTok{ y }\FunctionTok{=} \DataTypeTok{IntConst}\NormalTok{ y}
\end{Highlighting}
\end{Shaded}
Is that any better? Well,
\texttt{pure\ f\ \textless{}*\textgreater{}\ IntConst\ 5} is now equal to
\texttt{IntConst\ 5}, so that works out. But what about
\texttt{f\ \textless{}*\textgreater{}\ pure\ x\ =\ fmap\ (\$\ x)\ f}? Let's use
\texttt{IntConst\ 3} as our \texttt{f}. On the left hand side:
\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{-- pure _ = IntConst 42}
\CommentTok{-- IntConst _ <*> IntConst y = IntConst y}
\DataTypeTok{IntConst} \DecValTok{3} \FunctionTok{<*>}\NormalTok{ pure x }\FunctionTok{=} \DataTypeTok{IntConst} \DecValTok{3} \FunctionTok{<*>} \DataTypeTok{IntConst} \DecValTok{42}
\FunctionTok{=} \DataTypeTok{IntConst} \DecValTok{42}
\end{Highlighting}
\end{Shaded}
And on the right hand side:
\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{-- fmap f (IntConst x) = IntConst x}
\NormalTok{fmap (}\FunctionTok{$}\NormalTok{ x) (}\DataTypeTok{IntConst} \DecValTok{3}\NormalTok{) }\FunctionTok{=} \DataTypeTok{IntConst} \DecValTok{3}
\end{Highlighting}
\end{Shaded}
Ah, that's wrong too, then.
At this point it might seem like I am facetiously moving very slowly to an
answer that has to use \emph{both} inputs. After all, my earlier statement
claimed that \texttt{f\ \textless{}*\textgreater{}\ x} has to use both the
effects of \texttt{f} and the effects of \texttt{x}, each exactly once. Because
we didn't really know what the ``effects'' of \texttt{IntConst} are, we don't
know exactly ``how'' to combine them\ldots{}but we can probably guess it has to
use both \texttt{Int}s. So, with that in mind, let's try another definition:
\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{instance} \DataTypeTok{Applicative} \DataTypeTok{IntConst} \KeywordTok{where}
\NormalTok{ pure _ }\FunctionTok{=} \DataTypeTok{IntConst} \DecValTok{42}
\DataTypeTok{IntConst}\NormalTok{ x }\FunctionTok{<*>} \DataTypeTok{IntConst}\NormalTok{ y }\FunctionTok{=} \DataTypeTok{IntConst}\NormalTok{ (x }\FunctionTok{+}\NormalTok{ y)}
\end{Highlighting}
\end{Shaded}
Alright, now we use both \texttt{x} and \texttt{y} in the result. Let's see
again if this follows our expectations about \texttt{pure} -- if
\texttt{pure\ f\ \textless{}*\textgreater{}\ x} is the same as
\texttt{fmap\ f\ x}. Using \texttt{IntConst\ 5} again as \texttt{x}:
\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{-- pure _ = IntConst 42}
\CommentTok{-- IntConst x <*> InstConst y = IntConst (x + y)}
\NormalTok{pure f }\FunctionTok{<*>} \DataTypeTok{IntConst} \DecValTok{5} \FunctionTok{=} \DataTypeTok{IntConst} \DecValTok{42} \FunctionTok{<*>} \DataTypeTok{IntConst} \DecValTok{5}
\FunctionTok{=} \DataTypeTok{IntConst} \DecValTok{47}
\end{Highlighting}
\end{Shaded}
On the right hand side, we have:
\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{-- fmap f (IntConst x) = IntConst x}
\NormalTok{fmap f (}\DataTypeTok{IntConst} \DecValTok{5}\NormalTok{) }\FunctionTok{=} \DataTypeTok{IntConst} \DecValTok{5}
\end{Highlighting}
\end{Shaded}
Another dead end. It looks like it isn't just enough that we \emph{use} both
\texttt{Int}s\ldots{}we have to use them in a way such that the \texttt{Int} we
use as the result of \texttt{pure\ f} as to be an \emph{identity} to our
operation. Whatever \texttt{Int} is returned by \texttt{pure\ f} has to leave
any other \texttt{Int} unchanged when used with
\texttt{\textless{}*\textgreater{}}.
Thinking back, we remember that if our operation is \texttt{+}, we can use
\texttt{0}, since \texttt{0\ +\ x\ =\ x} and \texttt{x\ +\ 0\ =\ x}, for all
\texttt{x}. Luckily, our operation \texttt{x\ +\ y} is one that even \emph{has}
an identity. If we had chosen another operation (like \texttt{x\ +\ 2\ *\ y}),
we wouldn't be so lucky. Finally:
\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{instance} \DataTypeTok{Applicative} \DataTypeTok{IntConst} \KeywordTok{where}
\NormalTok{ pure _ }\FunctionTok{=} \DataTypeTok{IntConst} \DecValTok{0}
\DataTypeTok{IntConst}\NormalTok{ x }\FunctionTok{<*>} \DataTypeTok{IntConst}\NormalTok{ y }\FunctionTok{=} \DataTypeTok{IntConst}\NormalTok{ (x }\FunctionTok{+}\NormalTok{ y)}
\end{Highlighting}
\end{Shaded}
At last this feels like something that should make sense. And, does it? Testing
out, again, \texttt{pure\ f\ \textless{}*\textgreater{}\ x\ =\ fmap\ f\ x}:
\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{-- pure _ = IntConst 0}
\CommentTok{-- IntConst x <*> InstConst y = IntConst (x + y)}
\NormalTok{pure f }\FunctionTok{<*>} \DataTypeTok{IntConst} \DecValTok{5} \FunctionTok{=} \DataTypeTok{IntConst} \DecValTok{0} \FunctionTok{<*>} \DataTypeTok{IntConst} \DecValTok{5}
\FunctionTok{=} \DataTypeTok{IntConst} \DecValTok{5}
\end{Highlighting}
\end{Shaded}
\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{-- fmap f (IntConst x) = IntConst x}
\NormalTok{fmap f (}\DataTypeTok{IntConst} \DecValTok{5}\NormalTok{) }\FunctionTok{=} \DataTypeTok{IntConst} \DecValTok{5}
\end{Highlighting}
\end{Shaded}
Perfect! And, checking now
\texttt{f\ \textless{}*\textgreater{}\ pure\ x\ =\ fmap\ (\$\ x)\ f}:
\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{-- pure _ = IntConst 0}
\CommentTok{-- IntConst x <*> IntConst y = IntConst (x + y)}
\DataTypeTok{IntConst} \DecValTok{3} \FunctionTok{<*>}\NormalTok{ pure x }\FunctionTok{=} \DataTypeTok{IntConst} \DecValTok{3} \FunctionTok{<*>} \DataTypeTok{IntConst} \DecValTok{0}
\FunctionTok{=} \DataTypeTok{IntConst} \DecValTok{3}
\end{Highlighting}
\end{Shaded}
\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{-- fmap f (IntConst x) = IntConst x}
\NormalTok{fmap (}\FunctionTok{$}\NormalTok{ x) (}\DataTypeTok{IntConst} \DecValTok{3}\NormalTok{) }\FunctionTok{=} \DataTypeTok{IntConst} \DecValTok{3}
\end{Highlighting}
\end{Shaded}
This definition works for both\footnote{Note that in the real world we also have
to verify that our definition combines effects in an \emph{associative} way,
but we won't go too deeply into this for this article.}!
\hypertarget{the-effect-of-const}{%
\subsection{The Effect of Const}\label{the-effect-of-const}}
With our definition picked out, what do we think \texttt{sequenceA\_} does for
\texttt{IntConst}?
\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{sequenceA_ ::}\NormalTok{ [}\DataTypeTok{IntConst}\NormalTok{ a] }\OtherTok{->} \DataTypeTok{IntConst}\NormalTok{ ()}
\end{Highlighting}
\end{Shaded}
Well, if each application of \texttt{\textless{}*\textgreater{}} adds together
the \texttt{Int} in the \texttt{IntConst\ a}, and \texttt{sequenceA\_} uses
\texttt{\textless{}*\textgreater{}} once per every
\texttt{IntConst\ a}\ldots{}we can guess that \texttt{sequenceA\_} for
\texttt{IntConst} is just \texttt{sum}!
This might be more clear if we strip away the newtype wrappers (replacing
\texttt{IntConst\ a} with its contents, \texttt{Int}):
\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{sequenceA_ ::}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }\OtherTok{->} \DataTypeTok{Int}
\end{Highlighting}
\end{Shaded}
From this definition of \texttt{\textless{}*\textgreater{}}, we can form an idea
of what the effects of the \texttt{IntConst} Applicative are: they \emph{add} to
some accumulator environment! And \texttt{pure\ \_\ =\ IntConst\ 0} means that
\texttt{pure\ \_} adds zero to our accumulator -- it leaves our accumulator
\emph{unchanged}, and so effectively has no effect.
That's why \texttt{sequenceA\_} is \texttt{sum} -- it sequences every effect of
the \texttt{IntConst}, which means that it sequences all of those ``add to the
accumulator'' effects one after the other.
\hypertarget{alternative-pictures}{%
\subsection{Alternative Pictures}\label{alternative-pictures}}
Note that the requirements we gave for the \texttt{Applicative} instance doesn't
necessarily imply that the one we have is the only instance. For example, the
following instance is also valid:
\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{instance} \DataTypeTok{Applicative} \DataTypeTok{IntConst} \KeywordTok{where}
\NormalTok{ pure _ }\FunctionTok{=} \DataTypeTok{IntConst} \DecValTok{1}
\DataTypeTok{IntConst}\NormalTok{ x }\FunctionTok{<*>} \DataTypeTok{IntConst}\NormalTok{ y }\FunctionTok{=} \DataTypeTok{IntConst}\NormalTok{ (x }\FunctionTok{*}\NormalTok{ y)}
\end{Highlighting}
\end{Shaded}
If our ``combining'' action is \texttt{*}, then \texttt{pure} has to be an
identity. So, \texttt{pure\ \_\ =\ IntConst\ 1} works fine as an identity here,
since \texttt{1\ *\ x\ =\ x} and \texttt{x\ *\ 1\ =\ x}, for all \texttt{x}.
\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{-- pure _ = IntConst 1}
\CommentTok{-- IntConst x <*> InstConst y = IntConst (x * y)}
\NormalTok{pure f }\FunctionTok{<*>} \DataTypeTok{IntConst} \DecValTok{5} \FunctionTok{=} \DataTypeTok{IntConst} \DecValTok{1} \FunctionTok{<*>} \DataTypeTok{IntConst} \DecValTok{5}
\FunctionTok{=} \DataTypeTok{IntConst} \DecValTok{5}
\end{Highlighting}
\end{Shaded}
\begin{Shaded}
\begin{Highlighting}[]
\CommentTok{-- fmap f (IntConst x) = IntConst x}
\NormalTok{fmap f (}\DataTypeTok{IntConst} \DecValTok{5}\NormalTok{) }\FunctionTok{=} \DataTypeTok{IntConst} \DecValTok{5}
\end{Highlighting}
\end{Shaded}
\hypertarget{a-general-alternative}{%
\subsection{A General Alternative}\label{a-general-alternative}}
It looks like the Applicative for \texttt{IntConst} has to follow some pattern:
\begin{itemize}
\tightlist
\item
\texttt{\textless{}*\textgreater{}} has to combine the \texttt{Int}s inside
somehow using some operation \texttt{f}. (\texttt{f} also has to be
associative, which is a point we didn't touch on specifically)
\item
The \texttt{Int} that \texttt{pure} returns has to be an \emph{identity} to
\texttt{f}.
\end{itemize}
Sound familiar?
This is all satisfied if and only if \texttt{f} and the result of \texttt{pure}
form a
\textbf{\href{https://www.schoolofhaskell.com/user/mgsloan/monoids-tour}{monoid}}
on the integers!
There is a very fundamental link here: the \texttt{Applicative} laws for
\texttt{IntConst} are satisfied if and only if
\texttt{\textless{}*\textgreater{}} acts monoidally on the contents, with
\texttt{pure}'s result as the identity of that monoid.
(For those unfamiliar with monoids, a \texttt{Monoid} in Haskell is a type
\texttt{w} that has an associative operation
\texttt{(\textless{}\textgreater{})\ ::\ w\ -\textgreater{}\ w\ -\textgreater{}\ w}
along with an identity \texttt{mempty\ ::\ w} that leaves values unchanged when
used with \texttt{\textless{}\textgreater{}}.)
So, \emph{any} \texttt{f} and \texttt{pure} works, as long as they form a
\emph{monoid}. And any monoid in the Integers is a valid \texttt{Applicative}
instance for \texttt{IntConst}!
\hypertarget{general-const}{%
\section{General Const}\label{general-const}}
Let's revisit our original \texttt{Const} type:
\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{newtype} \DataTypeTok{Const}\NormalTok{ w a }\FunctionTok{=} \DataTypeTok{Const}\NormalTok{ \{}\OtherTok{ getConst ::}\NormalTok{ w \}}
\end{Highlighting}
\end{Shaded}
The \texttt{Functor} instance is unique, so there isn't any leeway we have
(\texttt{fmap} is always fixed for every type):
\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{instance} \DataTypeTok{Functor}\NormalTok{ (}\DataTypeTok{Const}\NormalTok{ w) }\KeywordTok{where}
\NormalTok{ fmap _ (}\DataTypeTok{Const}\NormalTok{ w) }\FunctionTok{=} \DataTypeTok{Const}\NormalTok{ w}
\end{Highlighting}
\end{Shaded}
This is the only definition that preserves \texttt{fmap\ id\ =\ id}.
Now we can actually write an \texttt{Applicative} instance for
\texttt{Const\ w}\ldots{}as long as we provide a \texttt{Monoid} to use with
\texttt{w}\footnote{Note that the Applicative laws are loose enough to allow a
different definition, with the same \texttt{pure}, but with
\texttt{Const\ x\ \textless{}*\textgreater{}\ Const\ y\ =\ Const\ (y\ \textless{}\textgreater{}\ x}).
But, this is just a different \texttt{Monoid} (\texttt{Const\ (Dual\ w)}).}!
\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{instance} \DataTypeTok{Monoid}\NormalTok{ w }\OtherTok{=>} \DataTypeTok{Applicative}\NormalTok{ (}\DataTypeTok{Const}\NormalTok{ w) }\KeywordTok{where}
\NormalTok{ pure _ }\FunctionTok{=} \DataTypeTok{Const}\NormalTok{ mempty}
\DataTypeTok{Const}\NormalTok{ x }\FunctionTok{<*>} \DataTypeTok{Const}\NormalTok{ y }\FunctionTok{=} \DataTypeTok{Const}\NormalTok{ (x }\FunctionTok{<>}\NormalTok{ y)}
\end{Highlighting}
\end{Shaded}
Like how we said, as long as the ``combining'' function for \texttt{x} and
\texttt{y} have the identity that is given by the result of \texttt{pure}, this
is a valid Applicative.
The ``effects'' of this Applicative instance are ``accumulate to some
accumulator''. If this sounds familiar, this is because this is exactly the
effect of the \texttt{Writer\ w} Applicative instance. \texttt{Const\ w} and
\texttt{Writer\ w} have the same effects (``accumulate to some accumulator''),
and this can be seen clearly by comparing the two types:
\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{data} \DataTypeTok{Const}\NormalTok{ w a }\FunctionTok{=} \DataTypeTok{Const}\NormalTok{ w}
\KeywordTok{data} \DataTypeTok{Writer}\NormalTok{ w a }\FunctionTok{=} \DataTypeTok{Writer}\NormalTok{ w a}
\end{Highlighting}
\end{Shaded}
(\texttt{Const} is just \texttt{Writer} without the \texttt{a} value)
\hypertarget{what-is-applicative-really}{%
\section{What is Applicative Really?}\label{what-is-applicative-really}}
If you think about this, this seems like a bit of a crazy coincidence.
Applicatives are an interesting concept, and Monoids are a different one.
But it looks like in order to make an \texttt{Applicative} instance for
\texttt{Const\ w}, the behavior of \texttt{\textless{}*\textgreater{}} and
\texttt{pure} have to follow some certain properties in order to fit the
Applicative laws\ldots{}and those properties are \emph{exactly} monoidal
properties and the Monoid laws.
To illustrate this link, we can see the type of \texttt{pure} and
\texttt{\textless{}*\textgreater{}} for \texttt{Const\ w}, without the newtype
wrappers (and ignored arguments)
\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{instance} \DataTypeTok{Monoid}\NormalTok{ w }\OtherTok{=>} \DataTypeTok{Applicative}\NormalTok{ (}\DataTypeTok{Const}\NormalTok{ w) }\KeywordTok{where}
\OtherTok{ pure ::}\NormalTok{ w}
\OtherTok{ (<*>) ::}\NormalTok{ w }\OtherTok{->}\NormalTok{ w }\OtherTok{->}\NormalTok{ w}
\end{Highlighting}
\end{Shaded}
And let's look at the \texttt{Monoid} typeclass:
\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{instance} \DataTypeTok{Monoid}\NormalTok{ w }\KeywordTok{where}
\OtherTok{ mempty ::}\NormalTok{ w}
\OtherTok{ (<>) ::}\NormalTok{ w }\OtherTok{->}\NormalTok{ w }\OtherTok{->}\NormalTok{ w}
\end{Highlighting}
\end{Shaded}
It seems like \texttt{Const} is nothing more than a (type-level) function on a
Monoid. As an \texttt{*\ -\textgreater{}\ (k\ -\textgreater{}\ *)}, it takes a
\texttt{*}-kinded Monoid and turns it into a
\texttt{k\ -\textgreater{}\ *}-kinded Monoid:
\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{instance} \DataTypeTok{Monoid}\NormalTok{ (}\OtherTok{w ::} \FunctionTok{*}\NormalTok{) }\OtherTok{=>} \DataTypeTok{Applicative}\NormalTok{ (}\DataTypeTok{Const}\OtherTok{ w ::}\NormalTok{ k }\OtherTok{->} \FunctionTok{*}\NormalTok{)}
\end{Highlighting}
\end{Shaded}
``Give me a \texttt{Monoid} and I'll give you something
\texttt{k\ -\textgreater{}\ *} that is also a monoid!''
\texttt{Const} is a
\emph{\href{https://bartoszmilewski.com/2015/07/21/free-monoids/}{monoid
homomorphism}}: it takes a monoid \texttt{w} with \texttt{mempty} and
\texttt{(\textless{}\textgreater{})}, and turns it into a monoid
\texttt{Const\ w} with \texttt{pure\ \_} and
\texttt{\textless{}*\textgreater{}}:
\begin{Shaded}
\begin{Highlighting}[]
\DataTypeTok{Const}\NormalTok{ (x }\FunctionTok{<>}\NormalTok{ y) }\FunctionTok{=} \DataTypeTok{Const}\NormalTok{ x }\FunctionTok{<*>} \DataTypeTok{Const}\NormalTok{ y}
\DataTypeTok{Const}\NormalTok{ mempty }\FunctionTok{=}\NormalTok{ pure ()}
\end{Highlighting}
\end{Shaded}
Meaning ``\texttt{\textless{}\textgreater{}} then \texttt{Const}'' is the same
as ``\texttt{Const} then \texttt{\textless{}*\textgreater{}}'', and
``\texttt{Const} the \texttt{mempty}'' is the same as \texttt{pure\ ()}. Both
things essentially convey the exact same monoid -- one with
\texttt{\textless{}\textgreater{}} and \texttt{mempty}, and the other with
\texttt{\textless{}*\textgreater{}} and \texttt{pure\ ()}. In fact, it's a bit
more than a monoid homomorphism -- it's a \textbf{monoid isomorphism}:
\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{getConst x }\FunctionTok{<>}\NormalTok{ getConst y }\FunctionTok{=}\NormalTok{ getConst (x }\FunctionTok{<*>}\NormalTok{ y)}
\NormalTok{mempty }\FunctionTok{=}\NormalTok{ getConst (pure ())}
\end{Highlighting}
\end{Shaded}
Which means ``\texttt{getConst} then \texttt{\textless{}\textgreater{}}'' is the
same as ``\texttt{\textless{}*\textgreater{}} then \texttt{getConst}'', and
\texttt{mempty} is the same as \texttt{getConst\ (pure\ ())}. \texttt{getConst}
takes you from one monoid (with \texttt{\textless{}*\textgreater{}} and
\texttt{pure\ ()}) to another (with \texttt{\textless{}\textgreater{}} and
\texttt{mempty}).
One incidental observation -- \texttt{sequenceA\_} for \texttt{Const\ w} might
look familiar:
\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{sequenceA_ ::} \DataTypeTok{Monoid}\NormalTok{ w }\OtherTok{=>}\NormalTok{ [}\DataTypeTok{Const}\NormalTok{ w a] }\OtherTok{->} \DataTypeTok{Const}\NormalTok{ w ()}
\CommentTok{-- strip out newtype wrappers}
\OtherTok{sequenceA_ ::} \DataTypeTok{Monoid}\NormalTok{ w }\OtherTok{=>}\NormalTok{ [w] }\OtherTok{->}\NormalTok{ w}
\end{Highlighting}
\end{Shaded}
It's just \texttt{mconcat}!
As an exercise, see if you can understand this definition of \texttt{mconcat} in
terms of \texttt{Const} and \texttt{traverse}:
\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{mconcat}\OtherTok{ ::} \DataTypeTok{Monoid}\NormalTok{ w }\OtherTok{=>}\NormalTok{ [w] }\OtherTok{->}\NormalTok{ w}
\NormalTok{mconcat }\FunctionTok{=}\NormalTok{ getConst }\FunctionTok{.}\NormalTok{ traverse_ }\DataTypeTok{Const}
\end{Highlighting}
\end{Shaded}
\texttt{traverse\_}, if you aren't familiar with it, an ``effectful'' function
(in our case, \texttt{Const\ ::\ w\ -\textgreater{}\ Const\ w\ w}) over all
values in a container, and sequences all of their effects.
\hypertarget{monoid-is-the-key}{%
\subsection{Monoid is the Key}\label{monoid-is-the-key}}
All of this actually witnesses the core of Applicative. A lot of people describe
Applicative as a ``lax monoidal functor''.
In this post, I was really handwavey with how I talked about ``effects''
(``\texttt{f\ \textless{}*\textgreater{}\ x} must use the effects of \texttt{f}
and \texttt{x} each once and only once'', I claimed, without defining what an
effect was). The notion of what an ``effect'' is really comes from each
individual Applicative, and each type really has its own conceptual picture of
what counts as an effect. The rigorous test of what is a meaningful way to have
an effect that can be combined comes from those laws
(\texttt{pure\ f\ \textless{}*\textgreater{}\ x\ =\ fmap\ f\ x}, etc.) and the
overall sentiment that the combination of effects is \emph{monoidal}.
At its heart, Applicative enforces that \texttt{liftA2} and
\texttt{\textless{}*\textgreater{}} are supposed to be ``monoidal'' in some way.
This fact is hidden by the normal form of the Applicative laws, but I feel like
seeing this play out in the \texttt{Applicative} instance for \texttt{Const} ---
how \texttt{Monoid} is exactly the constraint necessary to implement the
instance, and how \texttt{Const} forms a monoid isomorphism --- really helps
hammer in the monoidal nature of \emph{all} Applicative instances.
Applicative instances must be monoidal in how they sequence their effects.
Because \texttt{Const}'s effects are so simple (``accumulate a value''), this
makes it an especially obvious demonstration of this.
Hopefully this helps you gain some sense of appreciation between the link
between \texttt{Applicative} and \texttt{Monoid}, and also why \texttt{Const}'s
Applicative instance is defined the way it is!
\hypertarget{signoff}{%
\section{Signoff}\label{signoff}}
Hi, thanks for reading! You can reach me via email at
\href{mailto:justin@jle.im}{\nolinkurl{justin@jle.im}}, or at twitter at
\href{https://twitter.com/mstk}{@mstk}! This post and all others are published
under the \href{https://creativecommons.org/licenses/by-nc-nd/3.0/}{CC-BY-NC-ND
3.0} license. Corrections and edits via pull request are welcome and encouraged
at \href{https://github.com/mstksg/inCode}{the source repository}.
If you feel inclined, or this post was particularly helpful for you, why not
consider \href{https://www.patreon.com/justinle/overview}{supporting me on
Patreon}, or a \href{bitcoin:3D7rmAYgbDnp4gp4rf22THsGt74fNucPDU}{BTC donation}?
:)
\end{document}