% Options for packages loaded elsewhere
\PassOptionsToPackage{unicode=true}{hyperref}
\PassOptionsToPackage{hyphens}{url}
%
\documentclass[
  english,
]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
  \usepackage{textcomp} % provides euro and other symbols
\else % if luatex or xelatex
  \usepackage{unicode-math}
  \defaultfontfeatures{Scale=MatchLowercase}
  \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
\fi
% Use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
\IfFileExists{microtype.sty}{% use microtype if available
  \usepackage[]{microtype}
  \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\makeatletter
\@ifundefined{KOMAClassName}{% if non-KOMA class
  \IfFileExists{parskip.sty}{%
    \usepackage{parskip}
  }{% else
    \setlength{\parindent}{0pt}
    \setlength{\parskip}{6pt plus 2pt minus 1pt}}
}{% if KOMA class
  \KOMAoptions{parskip=half}}
\makeatother
\usepackage{xcolor}
\IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
\IfFileExists{bookmark.sty}{\usepackage{bookmark}}{\usepackage{hyperref}}
\hypersetup{
  pdftitle={CSci 555: Functional Programming Functional Programming in Scala Handling Errors without Exceptions},
  pdfauthor={H. Conrad Cunningham},
  hidelinks,
}
\urlstyle{same} % disable monospaced font for URLs
\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}}}}
\setlength{\emergencystretch}{3em} % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{5}
% Redefines (sub)paragraphs to behave more like sections
\ifx\paragraph\undefined\else
  \let\oldparagraph\paragraph
  \renewcommand{\paragraph}[1]{\oldparagraph{#1}\mbox{}}
\fi
\ifx\subparagraph\undefined\else
  \let\oldsubparagraph\subparagraph
  \renewcommand{\subparagraph}[1]{\oldsubparagraph{#1}\mbox{}}
\fi

% Set default figure placement to htbp
\makeatletter
\def\fps@figure{htbp}
\makeatother

\usepackage{caption}
\DeclareCaptionLabelFormat{nolabel}{}
\captionsetup{labelformat=nolabel}
\ifxetex
  % Load polyglossia as late as possible: uses bidi with RTL langages (e.g. Hebrew, Arabic)
  \usepackage{polyglossia}
  \setmainlanguage[]{english}
\else
  \usepackage[shorthands=off,main=english]{babel}
\fi

\title{CSci 555: Functional Programming\\
Functional Programming in Scala\\
Handling Errors without Exceptions}
\author{\textbf{H. Conrad Cunningham}}
\date{\textbf{7 March 2019}}

\begin{document}
\maketitle

{
\setcounter{tocdepth}{4}
\tableofcontents
}
Copyright (C) 2016, 2018, 2019, \href{http://www.cs.olemiss.edu/~hcc}{H.
Conrad Cunningham}\\
Professor of \href{https://www.cs.olemiss.edu}{Computer and Information
Science}\\
\href{http://www.olemiss.edu}{University of Mississippi}\\
211 Weir Hall\\
P.O. Box 1848\\
University, MS 38677\\
(662) 915-5358

\textbf{Note:} This set of notes accompanies my lectures on Chapter 4 of
the book \emph{Functional Programming in Scala} {[}Chiusano 2015{]}
(i.e.~the Red Book).

\textbf{Prerequisites}: In this set of notes, I assume the reader is
familiar with the programming concepts and Scala features covered in my
\emph{Notes on Scala for Java Programmers} {[}Cunningham 2019a{]},
\emph{Recursion Styles, Correctness, and Efficiency (Scala Version)}
{[}Cunningham 2019b{]}, \emph{Type System Concepts} {[}Cunningham
2019c{]}, and \emph{Functional Data Structures} {[}Cunningham 2019d{]}
(i.e.~Chapter 3 of the Red Book {[}Chuisano 2015{]}).

\textbf{Browser Advisory:} The HTML version of this textbook requires a
browser that supports the display of MathML. A good choice as of March
2019 is a recent version of Firefox from Mozilla.

\newpage
\setcounter{section}{3}

\hypertarget{handling-errors-without-exceptions}{%
\section{Handling Errors without
Exceptions}\label{handling-errors-without-exceptions}}

\hypertarget{introduction}{%
\subsection{Introduction}\label{introduction}}

A benefit of Java or Scala exception handling (i.e.~using
\VERB|\KeywordTok{try}|-\VERB|\KeywordTok{catch}| blocks) is that it
consolidates error handling to well-defined places in the code.

However, code that throws exceptions typically exhibits two problems for
functional programming.

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  It is not \emph{referentially transparent}. It has side effects. Its
  meaning is thus dependent upon the context in which it is executed.
\item
  It is not \emph{type safe}. Exceptions may cause effects that are of a
  different type than the return value of the function.
\end{enumerate}

\emph{The key idea} from Chapter 4 \emph{is to use ordinary data values
to represent failures and exceptions} in programs. This preserves
referential transparency and type safety while also preserving the
benefit of exception-handling mechanisms, that is, the consolidation of
error-handling logic.

To do this, we introduce the \VERB|\NormalTok{Option}| and
\VERB|\NormalTok{Either}| algebraic data types. These are standard types
in the Scala library, but for pedagogical purposes Chapter 4 introduces
its own definition that is similar to the standard one.

This set of notes also introduces Scala features that we have not
previously discussed extensively: type variance, call-by-name parameter
passing, and for-comprehensions.

\hypertarget{aside-on-null-references}{%
\subsection{Aside: On Null References}\label{aside-on-null-references}}

What should a function do when it is required to return an object but no
suitable object exists?

One common approach is to return a \emph{null reference}. British
computing scientist Tony Hoare, who introduced the null reference into
the Algol type system in the mid-1960s, calls that his ``billion dollar
mistake'' because it ``has led to innumerable errors, vulnerabilities,
and system crashes'' {[}Hoare 2009{]}.

The software patterns community documented a safer approach to this
situation by identifying the \emph{Null Object} design pattern {[}Woolf
1998{]}{[}Wikipedia 2019{]}. This well-known object-oriented pattern
seeks to ``encapsulate the absence of an object by providing a
substitutable alternative that offers suitable default do nothing
behavior'' {[}SourceMaking 2019{]}. That is, the object must be of the
correct type. It must be possible to apply all operations on that type
to the object. But the operations should have a neutral behavior, with
no side effects. The null object should actively do nothing!

The functional programming community introduced \emph{option types}
(e.g.~Haskell's \VERB|\DataTypeTok{Maybe}| and
\VERB|\DataTypeTok{Either}| types) as an approach to the same general
problem. Scala's \VERB|\NormalTok{Option}| and \VERB|\NormalTok{Either}|
correspond to Haskell's \VERB|\DataTypeTok{Maybe}| and
\VERB|\DataTypeTok{Either}| types. Rust's \VERB|\DataTypeTok{Option}|
and Swift's \texttt{Optional} are similar to Haskell's
\VERB|\DataTypeTok{Maybe}|.

The concept of \emph{nullable types} {[}Wikipedia 2019{]}, such as
Java's \VERB|\NormalTok{Optional}|, Python's \VERB|\VariableTok{None}|,
and C\#'s \VERB|\NormalTok{?}| type annotations, are closely related to
option types.

\hypertarget{an-option-algebraic-data-type}{%
\subsection{\texorpdfstring{An \texttt{Option} Algebraic Data
Type}{An Option Algebraic Data Type}}\label{an-option-algebraic-data-type}}

We define a Scala algebraic data type \VERB|\NormalTok{Option}| using
sealed trait \VERB|\NormalTok{Option}| with case class
\VERB|\NormalTok{Some}| to wrap a value and case object
\VERB|\NormalTok{None}| to denote an empty value. We specify the
operations on the data type using the \emph{method-chaining} style.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{import}\NormalTok{ scala.\{Option => _, Either => _, _\} }\CommentTok{// hide standard}
    \KeywordTok{sealed} \KeywordTok{trait}\NormalTok{ Option[+A] \{}
        \KeywordTok{def}\NormalTok{ map[B](f: A => B): Option[B] }
        \KeywordTok{def}\NormalTok{ getOrElse[B >: A](default: => B): B }
        \KeywordTok{def}\NormalTok{ flatMap[B](f: A => Option[B]): Option[B]}
        \KeywordTok{def}\NormalTok{ orElse[B >: A](ob: => Option[B]): Option[B]}
        \KeywordTok{def} \FunctionTok{filter}\NormalTok{(f: A => Boolean): Option[A]}
\NormalTok{    \}}
    \KeywordTok{case} \KeywordTok{class}\NormalTok{ Some[+A](get: A) }\KeywordTok{extends}\NormalTok{ Option[A]}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ None }\KeywordTok{extends}\NormalTok{ Option[Nothing]}
\end{Highlighting}
\end{Shaded}

The \VERB|\KeywordTok{import}| statement above hides the standard
definitions of \VERB|\NormalTok{Option}| and \VERB|\NormalTok{Either}|
from the Scala standard library. The versions developed in this chapter
are similar, but add useful features above what is available in the
standard library.

Before we move on to the definition of these methods, let's review the
concept of method chaining and then consider issues raised in the
signatures of the \VERB|\NormalTok{getOrElse}| and
\VERB|\NormalTok{orElse}| methods: one related to the generic parameters
and the other to the \VERB|\NormalTok{default}| parameters.

\hypertarget{method-chaining-in-scala}{%
\subsubsection{Method chaining in
Scala}\label{method-chaining-in-scala}}

Consider function \VERB|\NormalTok{map}| in the
\VERB|\NormalTok{Option}| trait. It is implemented in this chapter as a
method on the classes that extend the \VERB|\NormalTok{Option}| trait.

Method \VERB|\NormalTok{map}| takes two arguments and returns a result
object. Its implicit ``left'' argument is the receiver object for the
method call, an \VERB|\NormalTok{Option}| object represented internally
by the variable \VERB|\KeywordTok{this}|. Its explicit ``right''
argument is a function. The result returned is itself an
\VERB|\NormalTok{Option}| object.

Suppose \VERB|\NormalTok{obj}| is an \VERB|\NormalTok{Option[A]}| object
and \VERB|\NormalTok{f}| is an \VERB|\NormalTok{A => B}| function. In
standard object-oriented style, we can issue the call
\VERB|\NormalTok{obj.}\FunctionTok{map}\NormalTok{(f)}| to operate on
object \VERB|\NormalTok{obj}| with method \VERB|\NormalTok{map}| and
argument \VERB|\NormalTok{f}|. Scala allows us to apply such a method in
an \emph{infix operator} style as follows:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    obj map f}
\end{Highlighting}
\end{Shaded}

Note that \VERB|\NormalTok{map}| takes an \VERB|\NormalTok{Option[A]}|
as its left operand (i.e.~argument) and returns an
\VERB|\NormalTok{Option[B]}| object as its result. Thus we can
\emph{chain} such method calls as follows (where functions
\VERB|\NormalTok{p}| and \VERB|\NormalTok{g}| have the appropriate
types):

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    obj.}\FunctionTok{map}\NormalTok{(f).}\FunctionTok{filter}\NormalTok{(p).}\FunctionTok{map}\NormalTok{(g)}
\end{Highlighting}
\end{Shaded}

In Scala's infix operator style, this would be:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    (obj map f) filter p)) map g}
\end{Highlighting}
\end{Shaded}

But these operators associate to the left, so can leave off the
parentheses and write the above as follows

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    obj map f filter p map g}
\end{Highlighting}
\end{Shaded}

or perhaps more readably as:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    obj }\FunctionTok{map}\NormalTok{(f) }\FunctionTok{filter}\NormalTok{(p) }\FunctionTok{map}\NormalTok{(g)}
\end{Highlighting}
\end{Shaded}

Note that this last way of writing the chain suggests the \emph{data
flow} nature of this computation. The data originates with the source
\VERB|\NormalTok{obj}|, which is then transformed by a
\VERB|\FunctionTok{map}\NormalTok{(f)}| operator, then by a
\VERB|\FunctionTok{filter}\NormalTok{(p)}| operator, and then by a
\VERB|\FunctionTok{map}\NormalTok{(g)}| operator to give the final
result.

Now let's consider an issue raised in the signatures of the
\VERB|\NormalTok{getOrElse}| and \VERB|\NormalTok{orElse}| methods
related to the generic parameter.

\hypertarget{type-variance-issues}{%
\subsubsection{Type variance issues}\label{type-variance-issues}}

As we have discussed previously, the \VERB|\NormalTok{+A}| annotation in
the \VERB|\NormalTok{Option[+A]}| definition declares that parameter
\VERB|\NormalTok{A}| is \emph{covariant}. That is, if
\VERB|\NormalTok{S}| is a subtype of \VERB|\NormalTok{T}|, then
\VERB|\NormalTok{Option[S]}| is a subtype of
\VERB|\NormalTok{Option[T]}|. Also remember that
\VERB|\NormalTok{Nothing}| is a subtype of all other types.

For example, suppose type \VERB|\NormalTok{Beagle}| is a subtype of type
\VERB|\NormalTok{Dog}|, which, in turn, is a subtype of type
\VERB|\NormalTok{Mammal}|. Then, because of the covariant definition,
\VERB|\NormalTok{Option[Beagle]}| is a subtype of
\VERB|\NormalTok{Option[Dog]}|, which is a subtype of
\VERB|\NormalTok{Option[Mammal]}|. This is intuitively what we expect.

However, in \VERB|\NormalTok{getOrElse}| and \VERB|\NormalTok{orElse}|,
we use type constraint \VERB|\NormalTok{B >: A}|. This means that
\VERB|\NormalTok{B}| must be equal to \VERB|\NormalTok{A}| or a
supertype of \VERB|\NormalTok{A}|. We also define value parameter of
these functions to have type \VERB|\NormalTok{Option[B]}| instead of
\VERB|\NormalTok{Option[A]}|.

Why must we have this constraint?

See the \href{https://github.com/fpinscala/fpinscala/wiki}{chapter
notes} for the \emph{Functional Programming in Scala} book {[}Chiusano
2015{]} for more detail on this complicated issue. We sketch the
argument below.

In some sense, the \VERB|\NormalTok{+A}| annotation declares that, in
all contexts, it is safe to cast this type \VERB|\NormalTok{A}| to some
supertype of \VERB|\NormalTok{A}|. The Scala compiler does not allow us
to use this annotation unless we can cast all members of a type safely.

Suppose we declare \VERB|\NormalTok{orElse}| (incorrectly!) as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{trait}\NormalTok{ Option[+A] \{}
        \KeywordTok{def} \FunctionTok{orElse}\NormalTok{(o: Option[A]): Option[A]}
\NormalTok{        ... }
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

We have a problem because this declaration of \VERB|\NormalTok{orElse}|
only allows us to cast \VERB|\NormalTok{A}| to a subtype of
\VERB|\NormalTok{A}|.

Why?

As with any function, \VERB|\NormalTok{orElse}| can only be safely
passed a subtype of its declared input type. That is, a function of type
\VERB|\NormalTok{Dog => R}| can be passed an object of subtype like
\VERB|\NormalTok{Beagle}| or of type \VERB|\NormalTok{Dog}| itself, but
it cannot be passed a supertype object of \VERB|\NormalTok{Dog}| such as
\VERB|\NormalTok{Mammal}|.

As we saw in the notes on Chapter 3 {[}Cunningham 2019d{]}, Scala
functions are contravariant in their input types.

But \VERB|\NormalTok{orElse}| has a parameter type of
\VERB|\NormalTok{Option[A]}|. Because of the covariance of
\VERB|\NormalTok{A}| (declared in the trait), this parameter only allows
subtypes of \VERB|\NormalTok{A}|---not supertypes as required by the
covariance.

So, we have a contradiction.

For the incorrect signature of \VERB|\NormalTok{orElse}|, the Scala
compiler generates an error message such as ``Covariant type
\VERB|\NormalTok{A}| occurs in contravariant position.''

We can get around this error by using a more complicated signature that
does not mention \VERB|\NormalTok{A}| (declared in the trait) in any of
the function arguments, such as:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{trait}\NormalTok{ Option[+A] \{}
        \KeywordTok{def}\NormalTok{ orElse[B >: A](o: Option[B]): Option[B]}
\NormalTok{        ... }
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

Now consider the second new feature appearing in the signatures of
\VERB|\NormalTok{getOrElse}| and \VERB|\NormalTok{orElse}|---the
\VERB|\NormalTok{=> B}| and \VERB|\NormalTok{=> Option[B]}| types for
the parameters.

\hypertarget{parameter-passing-modes}{%
\subsubsection{Parameter-passing modes}\label{parameter-passing-modes}}

Scala's primary parameter-passing mode is \emph{call by value} as in
Java and C. That is, the program evaluates the caller's argument and the
resulting value is bound to the corresponding formal parameter within
the called function.

If the argument's value is of a primitive type, then the value itself is
passed. If the value is an object, then the address of (i.e. reference
to) the object is passed.

A call-by-value parameter is called \emph{strict} because the called
function always requires that parameter's value before it can execute.
The corresponding argument must be evaluated \emph{eagerly} before
transferring control to the called function.

Scala also has \emph{call-by-name} parameter passing. Consider the
\VERB|\NormalTok{default: => B}| feature in the declaration

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ getOrElse[B >: A](default: => B): B}
\end{Highlighting}
\end{Shaded}

The type notation \VERB|\NormalTok{=> B}| means the calling program
leaves the argument of type \VERB|\NormalTok{B}| unevaluated. That is,
the calling program wraps the argument expression in an parameterless
function and passes the function to the called method. This
automatically generated parameterless function is sometimes called a
\emph{thunk}.

Every reference to the corresponding parameter causes the thunk to be
evaluated. If the method does not access the corresponding parameter
during some execution, then the parameter is never evaluated.

As with all higher-order arguments in Scala, a thunk is passed as a
\emph{closure}. In addition to the function, the closure captures any
\emph{free variables} occurring in the expression---that is, the
variables defined in the caller's environment but not within the
expression itself.

Note: The closure actually captures the variable itself, not its value.
So if the free variable is either a reference to a
\VERB|\KeywordTok{var}| or to a mutable data structure, then changes in
the value are seen inside the called function. But in this course, we
normally use immutable data structures and \VERB|\KeywordTok{val}|
declarations.

A call-by-name parameter is called \emph{nonstrict} because the called
function does not always require that parameter's value for its
execution. The corresponding argument can thus be evaluated
\emph{lazily}, that is, evaluated only if and when its value is needed.

We look at more implications of strict and nonstrict functions in
Chapter 5 {[}Chiusano 2015{]}.

Note: See
\href{../Closures/ClosureExample.scala}{\texttt{ClosureExample.scala}}
and \href{../Closures/ThunkExample.scala}{\texttt{ThunkExample.scala}}
for examples of using closures and thunks, respectively.

\hypertarget{implementing-the-option-methods}{%
\subsubsection{\texorpdfstring{Implementing the \texttt{Option}
methods}{Implementing the Option methods}}\label{implementing-the-option-methods}}

Now, let's define the methods in the \VERB|\NormalTok{Option}| data
type.

Above we defined the trait \VERB|\NormalTok{Option}| as follows. It is
parameterized by covariant type \VERB|\NormalTok{A}|.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{import}\NormalTok{ scala.\{Option => _, Either => _, _\} }\CommentTok{// hide standard}
    \KeywordTok{sealed} \KeywordTok{trait}\NormalTok{ Option[+A] \{}
        \KeywordTok{def}\NormalTok{ map[B](f: A => B): Option[B] }
        \KeywordTok{def}\NormalTok{ getOrElse[B >: A](default: => B): B}
        \KeywordTok{def}\NormalTok{ flatMap[B](f: A => Option[B]): Option[B]}
        \KeywordTok{def}\NormalTok{ orElse[B >: A](ob: => Option[B]): Option[B]}
        \KeywordTok{def} \FunctionTok{filter}\NormalTok{(f: A => Boolean): Option[A]}
\NormalTok{    \}}
    \KeywordTok{case} \KeywordTok{class}\NormalTok{ Some[+A](get: A) }\KeywordTok{extends}\NormalTok{ Option[A]}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ None }\KeywordTok{extends}\NormalTok{ Option[Nothing]}
\end{Highlighting}
\end{Shaded}

The \VERB|\NormalTok{Option}| data type is similar to a list that is
either empty or has one element. As with the \VERB|\NormalTok{List}|
algebraic data type from Chapter 3, we \emph{follow the types to
implementations}. (This is sometimes called \emph{type-driven
development}.) That is, we use the form of the data to guide us to
design the form of the function.

The \VERB|\NormalTok{map}| method applies a function to its implicit
\VERB|\NormalTok{Option[A]}| argument. If the implicit argument is a
\VERB|\NormalTok{Some}|, the method applies the function to the wrapped
value and returns the resulting \VERB|\NormalTok{Some}|. If it is a
\VERB|\NormalTok{None}|, the method just returns
\VERB|\NormalTok{None}|. We can implement \VERB|\NormalTok{map}| using
pattern matching directly as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ map[B](f: A => B): Option[B] = }\KeywordTok{this} \KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case}\NormalTok{ None    => None}
        \KeywordTok{case}\NormalTok{ Some(a) => Some(}\FunctionTok{f}\NormalTok{(a))}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

Similarly, we can use pattern matching directly to implement the
\VERB|\NormalTok{getOrElse}| function. If the implicit argument is of
type \VERB|\NormalTok{Some}|, this function returns the value it wraps.
If the implicit argument is of type \VERB|\NormalTok{None}|, this
function returns the value denoted by the \VERB|\NormalTok{default}|
argument. By passing \VERB|\NormalTok{default}| by name, the argument is
only evaluated when its value is needed.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ getOrElse[B >: A](default: => B): B = }\KeywordTok{this} \KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case}\NormalTok{ None    => default }\CommentTok{// evaluate the thunk}
        \KeywordTok{case}\NormalTok{ Some(a) => a}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

Function \VERB|\NormalTok{flatMap}| applies its argument function
\VERB|\NormalTok{f}|, which might fail, to its implicit
\VERB|\NormalTok{Option}| argument when this value is not
\VERB|\NormalTok{None}|. We can define \VERB|\NormalTok{flatMap}| in
terms of \VERB|\NormalTok{map}| and \VERB|\NormalTok{getOrElse}| as
shown below. (Reminder: If we apply method names as operators in an
infix manner, they associate to the left. The leftmost operator
implicitly operates on \VERB|\KeywordTok{this}| object.)

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ flatMap[B](f: A => Option[B]): Option[B] =}
        \FunctionTok{map}\NormalTok{(f) getOrElse None}
\end{Highlighting}
\end{Shaded}

We can also define \VERB|\NormalTok{flatMap}| using pattern matching
directly.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ flatMap_}\DecValTok{1}\NormalTok{[B](f: A => Option[B]): Option[B] = }\KeywordTok{this} \KeywordTok{match}\NormalTok{ \{}
       \KeywordTok{case}\NormalTok{ None    => None}
       \KeywordTok{case}\NormalTok{ Some(a) => }\FunctionTok{f}\NormalTok{(a)}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

Function \VERB|\NormalTok{orElse}| returns the implicit
\VERB|\NormalTok{Option}| argument if is not \VERB|\NormalTok{None}|;
otherwise, it returns the explicit \VERB|\NormalTok{Option}| argument.
We can define \VERB|\NormalTok{orElse}| in terms of
\VERB|\NormalTok{map}| and \VERB|\NormalTok{getOrElse}| or by directly
using pattern matching.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ orElse[B >: A](ob: => Option[B]): Option[B] =}
        \KeywordTok{this} \FunctionTok{map}\NormalTok{ (Some(_)) getOrElse ob}

    \KeywordTok{def}\NormalTok{ orElse_}\DecValTok{1}\NormalTok{[B>:A](ob: => Option[B]): Option[B] = }
        \KeywordTok{this} \KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case}\NormalTok{ None => ob}
            \KeywordTok{case}\NormalTok{ _    => }\KeywordTok{this}
\NormalTok{        \}}
\end{Highlighting}
\end{Shaded}

The \VERB|\NormalTok{filter}| function converts its implicit argument
from \VERB|\NormalTok{Some}| to \VERB|\NormalTok{None}| if it does not
satisfy the boolean function \VERB|\NormalTok{p}|. We can define
\VERB|\NormalTok{filter}| by using pattern matching directly or by using
\VERB|\NormalTok{flatMap}|.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{filter}\NormalTok{(p: A => Boolean): Option[A] = }
        \KeywordTok{this} \KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case}\NormalTok{ Some(a) }\KeywordTok{if} \FunctionTok{p}\NormalTok{(a) => }\KeywordTok{this}
            \KeywordTok{case}\NormalTok{ _               => None}
\NormalTok{        \}}

    \KeywordTok{def} \FunctionTok{filter_1}\NormalTok{(p: A => Boolean): Option[A] =}
        \FunctionTok{flatMap}\NormalTok{(a => }\KeywordTok{if}\NormalTok{ (}\FunctionTok{p}\NormalTok{(a)) Some(a) }\KeywordTok{else}\NormalTok{ None)}
\end{Highlighting}
\end{Shaded}

\hypertarget{using-option-for-statistical-mean-and-variance}{%
\subsubsection{\texorpdfstring{Using \texttt{Option} for statistical
\texttt{mean} and
\texttt{variance}}{Using Option for statistical mean and variance}}\label{using-option-for-statistical-mean-and-variance}}

Consider a function to calculate and return the \emph{mean}
(i.e.~average value) of a list of numbers. This function must sum the
list of numbers and divide by the number of elements. It might have a
signature such as:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{mean}\NormalTok{(xs: List[Double]): Double}
\end{Highlighting}
\end{Shaded}

But what should be returned for empty lists?

We can modify the signature to use \VERB|\NormalTok{Option}| and define
the function as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{mean}\NormalTok{(xs: Seq[Double]): Option[Double] =}
        \KeywordTok{if}\NormalTok{ (xs.}\FunctionTok{isEmpty}\NormalTok{) }
\NormalTok{            None}
        \KeywordTok{else} 
\NormalTok{            Some(xs.}\FunctionTok{sum}\NormalTok{ / xs.}\FunctionTok{length}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

The return type now allows the possibility that the mean may be
undefined. We thus extend a partial function to a total function in a
meaningful way.

Above we also generalize the \VERB|\NormalTok{List}| type to its
supertype \VERB|\NormalTok{Seq}| from the Scala library. Type
\VERB|\NormalTok{Seq}| denotes a family of sequential data types that
includes the \VERB|\NormalTok{List}| type, array-like collections, etc.
This type defines the methods \VERB|\NormalTok{isEmpty}|,
\VERB|\NormalTok{sum}|, and \VERB|\NormalTok{length}|.

If the mean of a sequence \(s\) is \(m\), then the (statistical)
\emph{variance} of the sequence \(s\) is the mean of the sequence formed
by the terms \((x-m)^{2}\) for each \(x \in s\) (perserving the order).

Using the \VERB|\NormalTok{mean}| function defined above, we can compute
the variance of a sequence of numbers as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{variance}\NormalTok{(xs: Seq[Double]): Option[Double] =}
        \FunctionTok{mean}\NormalTok{(xs) flatMap }
\NormalTok{            (m => }\FunctionTok{mean}\NormalTok{(xs.}\FunctionTok{map}\NormalTok{(x => math.}\FunctionTok{pow}\NormalTok{(x - m, }\DecValTok{2}\NormalTok{))))}
\end{Highlighting}
\end{Shaded}

\hypertarget{using-option-in-the-labelled-digraph}{%
\subsubsection{\texorpdfstring{Using \texttt{Option} in the labelled
digraph}{Using Option in the labelled digraph}}\label{using-option-in-the-labelled-digraph}}

In the doubly labelled \VERB|\NormalTok{Digraph}| case study, we define
the following method to return the label on a vertex:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{getVertexLabel}\NormalTok{(ov: A): B}
\end{Highlighting}
\end{Shaded}

In the case study's \VERB|\NormalTok{DigraphList}| implementation, we
define this function as follows. The function terminates with an error
when the the argument vertex is not present in the digraph.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{getVertexLabel}\NormalTok{(ov: A): B = }
\NormalTok{        (vs }\FunctionTok{dropWhile}\NormalTok{ (w => w._}\DecValTok{1}\NormalTok{ != ov)) }\KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case}\NormalTok{ Nil => }
\NormalTok{                sys.}\FunctionTok{error}\NormalTok{(}\StringTok{"Vertex "}\NormalTok{ + ov + }\StringTok{" not in digraph"}\NormalTok{)}
            \KeywordTok{case}\NormalTok{ ((_,l)::_) => l}
\NormalTok{        \} }
\end{Highlighting}
\end{Shaded}

We can avoid the error termination in this function by changing the
method signature to return an \VERB|\NormalTok{Option[B]}| instead of a
\VERB|\NormalTok{B}|.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{getVertexLabelOption}\NormalTok{(ov: A): Option[B] = }
\NormalTok{        (vs }\FunctionTok{dropWhile}\NormalTok{ (w => w._}\DecValTok{1}\NormalTok{ != ov)) }\KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case}\NormalTok{ Nil        => None}
            \KeywordTok{case}\NormalTok{ ((_,l)::_) => Some(l)}
\NormalTok{    \} }
\end{Highlighting}
\end{Shaded}

Code that uses this new \VERB|\NormalTok{Digraph}| method can call the
various \VERB|\NormalTok{Option}| methods (or directly use pattern
matching) to process the result appropriately.

For example, if the vertex label is a string, it may be appropriate in
some scenarios to just use a null string for the label of a nonexistent
vertex. Let \VERB|\NormalTok{g}| be a \VERB|\NormalTok{Digraph}| and be
\VERB|\NormalTok{v}| be a possible vertex, then

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    (g getVertexLabelOption v) getOrElse }\StringTok{""}
\end{Highlighting}
\end{Shaded}

would either return the label string for \VERB|\NormalTok{v}| if it
exists or the null string if \VERB|\NormalTok{v}| does not exist.

Similarly, the code

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    (g getVertexLabelOption v) getOrElse }
\NormalTok{        (sys.}\FunctionTok{error}\NormalTok{(}\StringTok{"undefined vertex "}\NormalTok{ + v))}
\end{Highlighting}
\end{Shaded}

would still terminate with an error. However, this design enables the
user of the \VERB|\NormalTok{Digraph}| library to decide under what
circumstances and at what point in the code to terminate.

Idiom: A common pattern for computing with the \VERB|\NormalTok{Option}|
type is to use \VERB|\NormalTok{map}|, \VERB|\NormalTok{flatMap}|, and
\VERB|\NormalTok{filter}| to transform values generated by a function
like \VERB|\NormalTok{getVertexLabelOption}| and then to use
\VERB|\NormalTok{getOrElse}| for error handling at the end.

\hypertarget{lifting}{%
\subsubsection{Lifting}\label{lifting}}

It seems that that deciding to use of \VERB|\NormalTok{Option}| could
cause lots of changes to ripple through our code, much like the
introduction of extensive exception-handling would. However, we can
avoid that somewhat by using a technique called \emph{lifting}.

For example, the \VERB|\NormalTok{Option}| type's \VERB|\NormalTok{map}|
function enables us to transform values of type
\VERB|\NormalTok{Option[A]}| into values of type
\VERB|\NormalTok{Option[B]}| using a function of type
\VERB|\NormalTok{A => B}|.

Alternatively, we could consider \VERB|\NormalTok{map}| as transforming
a function of type \VERB|\NormalTok{A => B}| into a function of type
\VERB|\NormalTok{Option[A] => Option[B]}|. That is, we \emph{lift} an
ordinary function into a function on \VERB|\NormalTok{Option}|.

We can formalize this alternative view with the following function:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ lift[A,B](f: A => B): Option[A] => Option[B] = _.}\FunctionTok{map}\NormalTok{(f)}
\end{Highlighting}
\end{Shaded}

Thus any existing function can be transformed to work within the context
of a single \VERB|\NormalTok{Option}| value. For example, we can lift
the square root function from type \VERB|\NormalTok{Double}| to work
with \VERB|\NormalTok{Option[Double]}| as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ sqrtO: Option[Double] => Option[Double] = }
        \FunctionTok{lift}\NormalTok{(math.}\FunctionTok{sqrt}\NormalTok{ _)}
\end{Highlighting}
\end{Shaded}

We can now use \VERB|\NormalTok{sqrtO}| such as
\VERB|\FunctionTok{sqrtO}\NormalTok{(Some(}\DecValTok{4}\NormalTok{))}|.
This evaluates to \VERB|\NormalTok{Some(}\DecValTok{2}\NormalTok{)}|.

Chapter 4 of \emph{Functional Programming in Scala} {[}Chiusano 2015{]}
gives several examples where \VERB|\NormalTok{Option}| types can be used
effectively in realistic scenarios. One of these examples illustrates
how to wrap an exception-oriented API to provide users with
\VERB|\NormalTok{Option}| results in error situations.

TODO: Add example of wrapping an exception-oriented API.

Note: See \href{WrapException.scala}{\texttt{WrapException.scala}} for
examples of how to wrap exception-throwing functions to return
\VERB|\NormalTok{Option}| and \VERB|\NormalTok{Either}| objects,
respectively.

\hypertarget{for-comprehensions}{%
\subsubsection{For comprehensions}\label{for-comprehensions}}

Another useful function on \VERB|\NormalTok{Option}| data types is the
function \VERB|\NormalTok{map2}| that combines two
\VERB|\NormalTok{Option}| values by lifting a binary function. If either
of the arguments are \VERB|\NormalTok{None}|, then the result should
also be \VERB|\NormalTok{None}|. We can define \VERB|\NormalTok{map2}|
as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ map2[A,B,C](a: Option[A], b: Option[B])(f: (A, B) => C): }
\NormalTok{        Option[C] =}
\NormalTok{            a }\FunctionTok{flatMap}\NormalTok{ (aa => }
\NormalTok{                b }\FunctionTok{map}\NormalTok{ (bb => }
                    \FunctionTok{f}\NormalTok{(aa, bb)))}
\end{Highlighting}
\end{Shaded}

This function applies a series of \VERB|\NormalTok{map}| and
\VERB|\NormalTok{flatMap}| calls.

Because lifting is so common in functional programming, Scala provides a
syntactic construct called a \emph{for-comprehension} to facilitate its
use. This construct is really \emph{syntactic sugar} for a series of
applications of \VERB|\NormalTok{map}|, \VERB|\NormalTok{flatMap}|, and
\VERB|\NormalTok{withFilter}|. (Method \VERB|\NormalTok{withFilter}|
works like \VERB|\NormalTok{filter}| except it filters on demand,
without creating a new collection as a result.)

Here is the same code expressed as a for-comprehension:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ map2fc[A,B,C](a: Option[A], b: Option[B])(f: (A, B) => C): }
\NormalTok{        Option[C] =}
            \KeywordTok{for}\NormalTok{ \{ }
\NormalTok{                aa <- a}
\NormalTok{                bb <- b }
\NormalTok{            \} }\KeywordTok{yield} \FunctionTok{f}\NormalTok{(aa, bb)}
\end{Highlighting}
\end{Shaded}

Of course, for-comprehensions are more general than just their use with
\VERB|\NormalTok{Option}|. They can be used for the lists, arrays,
iterators, ranges, streams, and other types in the Scala standard
library that support the \VERB|\NormalTok{map}|,
\VERB|\NormalTok{flatMap}|, and \VERB|\NormalTok{withFilter}| (or
\VERB|\NormalTok{filter}|) operations.

Consider a list \VERB|\NormalTok{persons}| of person objects with
\VERB|\NormalTok{name}| and \VERB|\NormalTok{age}| fields. We can
collect the names of all persons who are age 21 and above as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{for}\NormalTok{ (p <- persons }\KeywordTok{if}\NormalTok{ p.}\FunctionTok{age}\NormalTok{ >= }\DecValTok{21}\NormalTok{) }\KeywordTok{yield}\NormalTok{ p.}\FunctionTok{name}
\end{Highlighting}
\end{Shaded}

This is equivalent to the following \VERB|\NormalTok{List}| expression

\begin{Shaded}
\begin{Highlighting}[]
    \FunctionTok{filter}\NormalTok{ (p => p.}\FunctionTok{age}\NormalTok{ >= }\DecValTok{21}\NormalTok{) }\FunctionTok{map}\NormalTok{ (p => p.}\FunctionTok{name}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

\hypertarget{translating-desugaring-for-comprehensions}{%
\subsubsection{Translating (desugaring)
for-comprehensions}\label{translating-desugaring-for-comprehensions}}

In general, a for-comprehension

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{for}\NormalTok{ (enums) }\KeywordTok{yield}\NormalTok{ e}
\end{Highlighting}
\end{Shaded}

evaluates expression \VERB|\NormalTok{e}| for each binding generated by
the enumerator sequence \VERB|\NormalTok{enums}| and collects the
results. An enumerator sequence begins with a generator and may be
followed by additional generators, value definitions, and guards.

\begin{itemize}
\item
  A \emph{generator} \VERB|\NormalTok{p <- e}| produces a sequence of
  zero or more bindings from expression \VERB|\NormalTok{e}| by matching
  each value against pattern \VERB|\NormalTok{p}|.
\item
  A \emph{value definition} \VERB|\NormalTok{p = e}| binds the names in
  pattern \VERB|\NormalTok{p}| to the result of evaluating the
  expression \VERB|\NormalTok{e}|.
\item
  A \emph{guard} \VERB|\KeywordTok{if}\NormalTok{ e}| restricts the
  bindings to those that satisfy the boolean expression \texttt{e}.
\end{itemize}

We can translate (or \emph{desugar}) for-comprehension (more or less) as
follows:

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  We replace every generator \VERB|\NormalTok{p <- e}|, where
  \VERB|\NormalTok{p}| is a pattern and \VERB|\NormalTok{e}| is an
  expression, by:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    p <- e.}\FunctionTok{withFilter}\NormalTok{ \{ }\KeywordTok{case}\NormalTok{ p => }\KeywordTok{true}\NormalTok{ ; }\KeywordTok{case}\NormalTok{ _ => }\KeywordTok{false}\NormalTok{ \}}
\end{Highlighting}
\end{Shaded}

  Here we use \VERB|\NormalTok{withFilter}| to filter out those items
  that do not match the pattern \VERB|\NormalTok{p}|.
\item
  While all comprehension have not been eliminated, repeat the
  following:

  \begin{enumerate}
  \def\labelenumii{\alph{enumii}.}
  \item
    Translate for-comprehension

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{for}\NormalTok{ (p <- e) }\KeywordTok{yield}\NormalTok{ e1}
\end{Highlighting}
\end{Shaded}

    to the expression:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    e.}\FunctionTok{map}\NormalTok{ \{ }\KeywordTok{case}\NormalTok{ p => e1 \}}
\end{Highlighting}
\end{Shaded}
  \item
    Translate for-comprehension

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{for}\NormalTok{ (p <- e; p1 <- e1; ... ) }\KeywordTok{yield}\NormalTok{ e2 }
\end{Highlighting}
\end{Shaded}

    where \VERB|\NormalTok{...}| is a (possibly empty) sequence of
    generators, definitions, or guards, to the expression:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    e.}\FunctionTok{flatMap}\NormalTok{ \{ }\KeywordTok{case}\NormalTok{ p => }\KeywordTok{for}\NormalTok{ (p1 <- e1; ... ) }\KeywordTok{yield}\NormalTok{ e2 \}}
\end{Highlighting}
\end{Shaded}
  \item
    Translate a generator \VERB|\NormalTok{p <- e}| followed by a guard
    \VERB|\KeywordTok{if}\NormalTok{ g}| to a single generator

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    p <- e.}\FunctionTok{withFilter}\NormalTok{((x1,...,xn) => g)}
\end{Highlighting}
\end{Shaded}

    where \VERB|\NormalTok{x,...,xn}| are the free variables of
    \VERB|\NormalTok{p}|.
  \item
    Translate a generator \VERB|\NormalTok{p <- e}| followed by a value
    definition \VERB|\NormalTok{p1 = e1}| to the following generator of
    pairs of values, where \VERB|\NormalTok{x}| and
    \VERB|\NormalTok{x1}| are fresh names:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    (p, p1) <- }\KeywordTok{for}\NormalTok{ (x@p <- e) }\KeywordTok{yield}
\NormalTok{        \{ }\KeywordTok{val}\NormalTok{ x1@p1 = e1; (x, x1) \}}
\end{Highlighting}
\end{Shaded}
  \end{enumerate}
\end{enumerate}

The Scala notation \VERB|\NormalTok{x@p}| means that name
\VERB|\NormalTok{x}| is bound to the value of the expression
\VERB|\NormalTok{p}|.

Note: Above we do not consider the imperative for-loops. These can also
be translated as above except that the imperative method
\VERB|\NormalTok{forEach}| is also needed.

As an example, we can translate (desugar) the for-comprehension

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{for}\NormalTok{(x <- e1; y <- e2; z <- e3) }\KeywordTok{yield}\NormalTok{ \{...\}}
\end{Highlighting}
\end{Shaded}

into the expression:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    e1.}\FunctionTok{flatMap}\NormalTok{(x => e2.}\FunctionTok{flatMap}\NormalTok{(y => e3.}\FunctionTok{map}\NormalTok{(z => \{...\}))) }
\end{Highlighting}
\end{Shaded}

As a second example, we can also translate the for-comprehension

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{for}\NormalTok{(x <- e; }\KeywordTok{if}\NormalTok{ p) }\KeywordTok{yield}\NormalTok{ \{...\}}
\end{Highlighting}
\end{Shaded}

into the expression:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    e.}\FunctionTok{withFilter}\NormalTok{(x => p).}\FunctionTok{map}\NormalTok{(x => \{...\})}
\end{Highlighting}
\end{Shaded}

If no \VERB|\NormalTok{withFilter}| method is available, we can instead
use:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    e.}\FunctionTok{filter}\NormalTok{(x => p).}\FunctionTok{map}\NormalTok{(x => \{...\}) }
\end{Highlighting}
\end{Shaded}

As a third example, we can translate for-comprehension

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{for}\NormalTok{(x <- e1; y = e2) }\KeywordTok{yield}\NormalTok{ \{...\}}
\end{Highlighting}
\end{Shaded}

into the expression:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    e1.}\FunctionTok{map}\NormalTok{(x => (x, e2)).}\FunctionTok{map}\NormalTok{((x,y) => \{...\}) }
\end{Highlighting}
\end{Shaded}

\hypertarget{adding-for-comprehensions-to-data-types}{%
\subsubsection{Adding for-comprehensions to data
types}\label{adding-for-comprehensions-to-data-types}}

The Scala language has no typing rules for the for-comprehensions
themselves. The Scala compiler first translates for-comprehensions into
calls on the various method and then checks the types. It does not
require that methods \VERB|\NormalTok{map}|, \VERB|\NormalTok{flatMap}|,
and \VERB|\NormalTok{withFilter}| have particular type signatures.
However, a particular setup for some collection type
\VERB|\NormalTok{C}| with elements of type \VERB|\NormalTok{A}| is the
following:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{trait}\NormalTok{ C[A] \{}
        \KeywordTok{def}\NormalTok{ map[B](f: A => B): C[B]}
        \KeywordTok{def}\NormalTok{ flatMap[B](f: A => C[B]): C[B]}
        \KeywordTok{def} \FunctionTok{withFilter}\NormalTok{(p: A => Boolean): C[A]}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

We can define our own data types to support for-comprehension by
providing one or more of the required operations above.

\begin{itemize}
\item
  If the data type defines just \VERB|\NormalTok{map}|, Scala allows
  for-comprehensions consisting of a single generator.
\item
  If the data type defines both \VERB|\NormalTok{flatMap}| and
  \VERB|\NormalTok{map}|, Scala allows for-comprehensions consisting of
  several generators.
\item
  If the data type defines \VERB|\NormalTok{withFilter}|, Scala allows
  for-comprehensions with guards. (If \VERB|\NormalTok{withFilter}| is
  not defined but \VERB|\NormalTok{filter}| is, Scala will currently use
  \VERB|\NormalTok{filter}| instead. However, this gives a deprecation
  warning, so this fallback feature may be eliminated in a future
  release of Scala.)
\end{itemize}

We added for-comprehensions to our own \VERB|\NormalTok{Option}| type
earlier. We do the same for the \VERB|\NormalTok{Either}| type in the
next section.

Note: A for-comprehension is, in general, convenient syntactic sugar for
expressing compositions of monadic operators. If time allows, we will
discuss monads later in the semester.

\hypertarget{an-either-algebraic-data-type}{%
\subsection{\texorpdfstring{An \texttt{Either} Algebraic Data
Type}{An Either Algebraic Data Type}}\label{an-either-algebraic-data-type}}

We can use data type \VERB|\NormalTok{Option}| to encode that a failure
or exception has occurred. However, it does not give any information
about what went wrong.

We can encode this additional information using the algebraic data type
\VERB|\NormalTok{Either}|.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{import}\NormalTok{ scala.\{Option => _, Either => _, _\} }\CommentTok{// hide builtin}
    \KeywordTok{sealed} \KeywordTok{trait}\NormalTok{ Either[+E,+A] \{}
        \KeywordTok{def}\NormalTok{ map[B](f: A => B): Either[E,B]}
        \KeywordTok{def}\NormalTok{ flatMap[EE >: E, B](f: A => Either[EE,B]): }
\NormalTok{            Either[EE,B]}
        \KeywordTok{def}\NormalTok{ orElse[EE >: E, AA >: A](b: => Either[EE,AA]): }
\NormalTok{            Either[EE,AA]}
        \KeywordTok{def}\NormalTok{ map2[EE >: E, B, C](b: Either[EE, B])(f: (A,B) => C): }
\NormalTok{            Either[EE, C] }
\NormalTok{    \}}
    \KeywordTok{case} \KeywordTok{class}\NormalTok{ Left[+E](get: E) }\KeywordTok{extends}\NormalTok{ Either[E,Nothing]}
    \KeywordTok{case} \KeywordTok{class}\NormalTok{ Right[+A](get: A) }\KeywordTok{extends}\NormalTok{ Either[Nothing,A]}
\end{Highlighting}
\end{Shaded}

By convention, we use the constructor \VERB|\NormalTok{Right}| to denote
success and constructor \VERB|\NormalTok{Left}| to denote failure.

We can implement \VERB|\NormalTok{map}|, \VERB|\NormalTok{flatMap}|, and
\VERB|\NormalTok{orElse}| directly using pattern matching on the
\texttt{Either} type.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ map[B](f: A => B): Either[E, B] = }
        \KeywordTok{this} \KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case} \FunctionTok{Left}\NormalTok{(e)  => }\FunctionTok{Left}\NormalTok{(e)}
            \KeywordTok{case} \FunctionTok{Right}\NormalTok{(a) => }\FunctionTok{Right}\NormalTok{(}\FunctionTok{f}\NormalTok{(a))}
\NormalTok{        \}}
   
    \KeywordTok{def}\NormalTok{ flatMap[EE >: E, B](f: A => Either[EE, B]): }
\NormalTok{        Either[EE, B] = }\KeywordTok{this} \KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case} \FunctionTok{Left}\NormalTok{(e)  => }\FunctionTok{Left}\NormalTok{(e)}
            \KeywordTok{case} \FunctionTok{Right}\NormalTok{(a) => }\FunctionTok{f}\NormalTok{(a)}
\NormalTok{        \}}
            
    \KeywordTok{def}\NormalTok{ orElse[EE >: E, AA >: A](b: => Either[EE, AA]): }
\NormalTok{        Either[EE, AA] = }\KeywordTok{this} \KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case} \FunctionTok{Left}\NormalTok{(_)  => b}
            \KeywordTok{case} \FunctionTok{Right}\NormalTok{(a) => }\FunctionTok{Right}\NormalTok{(a)}
\NormalTok{        \}}
\end{Highlighting}
\end{Shaded}

The availability of \VERB|\NormalTok{flatMap}| and
\VERB|\NormalTok{map}| enable us to use for-comprehension generators
with \VERB|\NormalTok{Either}|. We can thus implement
\VERB|\NormalTok{map2}| using a for-comprehension, as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ map2[EE >: E, B, C](b: Either[EE, B])(f: (A, B) => C): }
\NormalTok{        Either[EE, C] =}
            \KeywordTok{for}\NormalTok{ \{ a <- }\KeywordTok{this}\NormalTok{; b1 <- b \} }\KeywordTok{yield} \FunctionTok{f}\NormalTok{(a,b1)}
\end{Highlighting}
\end{Shaded}

Let's again use \VERB|\NormalTok{mean}| as an example and use a
\VERB|\NormalTok{String}| to describe the failure in
\VERB|\NormalTok{Left}|.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{mean}\NormalTok{(xs: IndexedSeq[Double]): Either[String, Double] = }
        \KeywordTok{if}\NormalTok{ (xs.}\FunctionTok{isEmpty}\NormalTok{) }
            \FunctionTok{Left}\NormalTok{(}\StringTok{"mean of empty list!"}\NormalTok{)}
        \KeywordTok{else} 
            \FunctionTok{Right}\NormalTok{(xs.}\FunctionTok{sum}\NormalTok{ / xs.}\FunctionTok{length}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

We can use the \VERB|\NormalTok{Left}| value to encode more information,
such as the location of the error in the program. For example, we might
catch and return the value of an \VERB|\NormalTok{Exception}| generated
as we do in the \VERB|\NormalTok{safeDiv}| function below.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{safeDiv}\NormalTok{(x: Int, y: Int): Either[Exception, Int] = }
        \KeywordTok{try} \FunctionTok{Right}\NormalTok{(x / y)}
            \KeywordTok{catch}\NormalTok{ \{ }\KeywordTok{case}\NormalTok{ e: Exception => }\FunctionTok{Left}\NormalTok{(e) \}}
\end{Highlighting}
\end{Shaded}

We can abstract the computational pattern in the
\VERB|\NormalTok{safeDiv}| function as function \VERB|\NormalTok{Try}|
defined below:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ Try[A](a: => A): Either[Exception, A] =}
        \KeywordTok{try} \FunctionTok{Right}\NormalTok{(a)  }\CommentTok{// evaluate thunk}
        \KeywordTok{catch}\NormalTok{ \{ }\KeywordTok{case}\NormalTok{ e: Exception => }\FunctionTok{Left}\NormalTok{(e) \}}
\end{Highlighting}
\end{Shaded}

Chapter 4 of \emph{Functional Programming in Scala} {[}Chiusano 2015{]}
describes other functions for type \VERB|\NormalTok{Either}|.

\hypertarget{standard-library}{%
\subsection{Standard Library}\label{standard-library}}

Both \VERB|\NormalTok{Option}| and \VERB|\NormalTok{Either}| appear in
the standard library.

The standard library \VERB|\NormalTok{Option}| type is similar to the
one developed here, but the library version is missing some of the
extended functions described in Chapter 4 {[}Chiusano 2015{]}.

The standard library \VERB|\NormalTok{Either}| type is similar but more
complicated, using projections on the left and right. It is also missing
some of the extended functions from Chapter 4 {[}Chiusano 2015{]}.

Study the Scala API documentation for more information on these data
types.

\hypertarget{summary}{%
\subsection{Summary}\label{summary}}

The big idea in this chapter is to use ordinary values to represent
exceptions and use higher-order functions for handling and propagating
errors. As examples, we considered the algebraic data types
\VERB|\NormalTok{Option}| and \VERB|\NormalTok{Either}| and functions
such as \VERB|\NormalTok{map}|, \VERB|\NormalTok{flatMap}|,
\VERB|\NormalTok{filter}|, and \VERB|\NormalTok{orElse}| to process
their values.

We will use this general technique of using values to represent effects
in the subsequent studies in this course.

We introduced the idea of nonstrict functions. We examine the
implications and use of these more in Chapter 5.

\hypertarget{source-code-for-chapter}{%
\subsection{Source Code for Chapter}\label{source-code-for-chapter}}

\begin{itemize}
\item
  \href{Option2.scala}{\texttt{Option2.scala}}
\item
  \href{Either2.scala}{\texttt{Either2.scala}}
\end{itemize}

\hypertarget{exercises}{%
\subsection{Exercises}\label{exercises}}

TODO: Add

\hypertarget{acknowledgements}{%
\subsection{Acknowledgements}\label{acknowledgements}}

In Spring 2016, I wrote this set of notes to accompany my lectures on
Chapter 4 of the book \emph{Functional Programming in Scala} {[}Chiusano
2015{]} (i.e.~the Red Book). I constructed the notes around the ideas,
general structure, and Scala examples from that chapter and its
associated materials.

I also patterned some of the discussion of for-comprehensions on Chapter
10 of the document \emph{Scala by Example} by Martin Odersky {[}Odersky
2014{]}, on Chapter 23 of 2nd Edition of the book \emph{Programming in
Scala} {[}Odersky 2016{]}, on the relevant parts of the Scala language
specification, and on a relevant FAQ in the Scala documentation.

In 2018 and 2019, I updated the format of the document to be more
compatible with my evolving document structures and corrected a few
errors. In 2019, I also added the sections on null references and method
chaining.

I maintain these notes as text in Pandoc's dialect of Markdown using
embedded LaTeX markup for the mathematical formulas and then translate
the notes to HTML, PDF, and other forms as needed.

\hypertarget{references}{%
\subsection{References}\label{references}}

\begin{description}
\tightlist
\item[{[}Chiusano 2015{]}:]
Paul Chiusano and Runar Bjarnason. \emph{Functional Programming in
Scala}, Manning, 2015. This book is sometimes called the Red Book. The
chapter notes for this book are available on GitHub at
\url{https://github.com/fpinscala/fpinscala/wiki}.
\item[{[}Cunningham 2019a{]}:]
H. Conrad Cunningham.
\href{../ScalaForJava/ScalaForJava.html}{\emph{Notes on Scala for Java
Programmers}}, 2019.
\item[{[}Cunningham 2019b{]}:]
H. Conrad Cunningham.
\href{../RecursionStyles/RecursionStylesScala.html}{\emph{Recursion
Styles, Correctness, and Efficiency (Scala Version)}}, 2019.
\item[{[}Cunningham 2019c{]}:]
H. Conrad Cunningham.
\href{../TypeConcepts/TypeSystemConcepts.html}{\emph{Type System
Concepts}}, 2019.
\item[{[}Cunningham 2019d{]}:]
H. Conrad Cunningham. \href{../FPS03/FunctionalDS.html}{\emph{Functional
Data Structures}}, 2019.
\item[{[}Hoare 2009{]}:]
Tony Hoare. Null References: The Billion Dollar Mistake,
\emph{InfoQ.com}, August 25, 2009, Available at
\url{https://www.infoq.com/presentations/Null-References-The-Billion-Dollar-Mistake-Tony-Hoare},
referenced 27 February 2019.
\item[{[}Odersky 2014{]}:]
Martin Odersky. \emph{Scala by Example}, EPFL, 2014. Available at
\url{https://www.scala-lang.org/docu/files/ScalaByExample.pdf}.
\item[{[}Odersky 2016{]}:]
Martin Odersky, Lex Spoon, and Bill Venners. \emph{Programming in
Scala}, 3rd Edition, Artima Inc, 2016; 1st Edition, 2007; 2nd Edition,
2010.
\item[{[}SourceMaking 2019{]}:]
SourceMaking. Null Object Design Pattern, \emph{Design Patterns},
Available at
\url{https://sourcemaking.com/design/_patterns/null/_object}, referenced
27 February 2019.
\item[{[}Wikipedia 2019{]}:]
Wikipedia. Articles on
\href{https://en.wikipedia.org/wiki/Null_object_pattern}{Null Object
Pattern} Nullable Type
{]}(\url{https://en.wikipedia.org/wiki/Nullable/_type}), accessed 28
February 2019.
\item[{[}Woolf 1998{]}:]
Bobby Woolf. Null Object, Chapter 1, In, Robert Martin, Dirk Riehle, and
Frank Buschmann, editors, \emph{Pattern Languages of Program Design 3},
Addison Wesley Longman, 1998.
\end{description}

\hypertarget{terms-and-concepts}{%
\subsection{Terms and Concepts}\label{terms-and-concepts}}

\emph{Big idea}: Using ordinary data values to represent failures and
exceptions in programs. This preserves referential transparency and type
safety while also preserving the benefit of exception-handling
mechanisms, that is, the consolidation of error-handling logic.

\emph{Concepts}: Error handling, exceptions referential transparency,
type safety, null reference, Null Object design pattern, option types,
nullabile types, \VERB|\NormalTok{Option}| and \VERB|\NormalTok{Either}|
algebraic data types in Scala, method chaining, type variance, covariant
and contravariant, parameter passing (by-value, by-name), thunk, free
variables, closure, strict and nonstrict parameters/functions, eager and
lazy evaluation, follow the types to implementation (type-driven
development), lifting, for-comprehensions, syntactic sugar, (generators,
definitions, guards), desugaring.

\end{document}