\PassOptionsToPackage{unicode=true}{hyperref} % options for packages loaded elsewhere
\PassOptionsToPackage{hyphens}{url}
%
\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}
  \usepackage{textcomp} % provides euro and other symbols
\else % if luatex or xelatex
  \usepackage{unicode-math}
  \defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
\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}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
}
\usepackage{hyperref}
\hypersetup{
            pdftitle={CSci 555, Functional Programming, Spring 2016 Functional Programming in Scala Handling Errors without Exceptions},
            pdfauthor={H. Conrad Cunningham},
            pdfborder={0 0 0},
            breaklinks=true}
\urlstyle{same}  % don't use monospace 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}{0}
% 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}

\title{CSci 555, Functional Programming, Spring 2016\\
Functional Programming in Scala\\
Handling Errors without Exceptions}
\author{\textbf{H. Conrad Cunningham}}
\date{\textbf{14 April 2016 (minor edit 4 February 2018)}}

\begin{document}
\maketitle

{
\setcounter{tocdepth}{4}
\tableofcontents
}
Copyright (C) 2016, 2018, H. Conrad Cunningham

\textbf{Acknowledgements}: This is a set of notes written to accompany
my lectures on Chapter 4 of the book \emph{Functional Programming in
Scala} by Paul Chiusano and Runar Bjarnason (Manning, 2015). I
constructed the notes around the ideas and Scala examples from that
chapter. I encourage all students to study that chapter.

I also patterned some of the discussion of for-comprehensions on Chapter
10 of the document \emph{Scala by Example} by Martin Odersky, on Chapter
23 of the book \emph{Programming in Scala}, Second Edition, by Marin
Odersky, Lex Spoon, and Bill Venners (Artima Press, 2010), on the
relevant parts of the Scala language specification, and on a relevant
FAQ in the Scala documentation.

\textbf{Prerequisite}: This discussion assumes the reader is familiar
with the programming concepts and Scala features covered in my
\emph{Notes on Scala for Java Programmers}, \emph{Recursion Concepts and
Terminology}, and \emph{Functional Data Structures}.

\textbf{Advisory}: The HTML version of this document uses MathML in a
few locations. For best results, use a browser that supports the display
of MathML. A good choice as of April 2016 seems to be a recent version
of Firefox from Mozilla.

TODO: Change to use code blocks, restructure to match current style

\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
\texttt{try}-\texttt{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 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 \texttt{Option} and \texttt{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 as do 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{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 an algebraic data type \texttt{Option} using sealed trait
\texttt{Option} with case class \texttt{Some} to wrap a value and case
object \texttt{None} to denote an empty value. We specify the operations
on the data type using the method-chaining style.

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

The \texttt{import} statement above hides the standard definitions of
\texttt{Option} and \texttt{Either} from the Scala standard library.

Before we move on to the definition of these methods, let's consider two
issues raised in the signatures of the \texttt{getOrElse} and
\texttt{orElse} methods: one related to the generic parameters and the
other to the \texttt{default} parameters.

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

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

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

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

Why must we have this constraint?

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

In some sense, the \texttt{+A} annotation declares that, in all
contexts, it is safe to cast this type \texttt{A} to some supertype of
\texttt{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 \texttt{orElse} (incorrectly) as follows:

\begin{verbatim}
    trait Option[+A] {
      def orElse(o: Option[A]): Option[A]
      ...
    }
    
\end{verbatim}

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

Why?

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

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

So, we have a contradiction.

For the incorrect signature of \texttt{orElse}, the Scala compiler
generates an error message such as ``Covariant type \texttt{A} occurs in
contravariant position.'' We can get around this error by using a more
complicated signature that does not mention \texttt{A} in any of the
function arguments, such as:

\begin{verbatim}
      def orElse[B >: A](o: Option[B]): Option[B]
\end{verbatim}

Now consider the second new feature appearing in the signatures of
\texttt{getOrElse} and \texttt{orElse}--the \texttt{=\textgreater{}\ B}
and \texttt{=\textgreater{}\ 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
\texttt{default:\ =\textgreater{}\ B} feature in the declaration

\begin{verbatim}
      def getOrElse[B >: A](default: => B): B
\end{verbatim}

The type notation \texttt{=\textgreater{}\ B} means the calling program
leaves the argument of type \texttt{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 \texttt{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 \texttt{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.

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

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

The \texttt{Option} data type is similar to a list that is either empty
or has one element.

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

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

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

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

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

\begin{verbatim}
      def flatMap[B](f: A => Option[B]): Option[B] =
        map(f) getOrElse None
\end{verbatim}

We can also define \texttt{flatMap} using pattern matching directly.

\begin{verbatim}
      def flatMap_1[B](f: A => Option[B]): Option[B] = this match {
        case None    => None
        case Some(a) => f(a)
      }
\end{verbatim}

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

\begin{verbatim}
      def orElse[B >: A](ob: => Option[B]): Option[B] =
        this map (Some(_)) getOrElse ob

      def orElse_1[B>:A](ob: => Option[B]): Option[B] = 
        this match {
          case None => ob
          case _    => this
        }
\end{verbatim}

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

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

      def filter_1(p: A => Boolean): Option[A] =
        flatMap(a => if (p(a)) Some(a) else None)
        
\end{verbatim}

\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{verbatim}
      def mean(xs: List[Double]): Double
\end{verbatim}

But what should be returned for empty lists?

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

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

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 \texttt{List} type to its supertype
\texttt{Seq} from the Scala library. Type \texttt{Seq} denotes a family
of sequential data types that includes the \texttt{List} type,
array-like collections, etc. This type defines the methods
\texttt{isEmpty}, \texttt{sum}, and \texttt{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 \texttt{mean} function defined above, we can compute the
variance of a sequence of numbers as follows:

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

\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 \texttt{Digraph} case study, we defined the
following method to return the label on a vertex:

\begin{verbatim}
      def getVertexLabel(ov: A): B
      
\end{verbatim}

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

\begin{verbatim}
     def getVertexLabel(ov: A): B = 
       (vs dropWhile (w => w._1 != ov)) match {
         case Nil => sys.error("Vertex " + ov + " not in digraph")
         case ((_,l)::_) => l
       } 
\end{verbatim}

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

\begin{verbatim}
     def getVertexLabelOption(ov: A): Option[B] = 
       (vs dropWhile (w => w._1 != ov)) match {
         case Nil        => None
         case ((_,l)::_) => Some(l)
       } 
\end{verbatim}

Code that uses this new \texttt{Digraph} method can call the various
\texttt{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 \texttt{g} be a \texttt{Digraph} and be \texttt{v} be a
possible vertex, then

\begin{verbatim}
      (g getVertexLabelOption v) getOrElse ""
\end{verbatim}

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

Similarly, the code

\begin{verbatim}
      (g getVertexLabelOption v) getOrElse 
        (sys.error("undefined vertex " + v))
\end{verbatim}

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

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

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

It seems that that deciding to use of \texttt{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 \texttt{Option} type's \texttt{map} function enables us
to transform values of type \texttt{Option{[}A{]}} into values of type
\texttt{Option{[}B{]}} using a function of type
\texttt{A\ =\textgreater{}\ B}.

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

We can formalize this alternative view with the following function:

\begin{verbatim}
      def lift[A,B](f: A => B): Option[A] => Option[B] = _.map(f)
\end{verbatim}

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

\begin{verbatim}
     def sqrtO: Option[Double] => Option[Double] = lift(math.sqrt _)
\end{verbatim}

We can now use \texttt{sqrtO} such as \texttt{sqrtO(Some(4))}. This
evaluates to \texttt{Some(2)}.

Chapter 4 of \emph{Functional Programming in Scala} gives several
examples where \texttt{Option} types can be used effectively in
realistic scenarios.

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

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

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

This function applies a series of \texttt{map} and \texttt{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 \texttt{map}, \texttt{flatMap}, and \texttt{withFilter}.
(Method \texttt{withFilter} works like \texttt{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{verbatim}
      def map2fc[A,B,C](a: Option[A], b: Option[B])(f: (A, B) => C): 
        Option[C] =
          for { 
            aa <- a
            bb <- b 
          } yield f(aa, bb)
\end{verbatim}

Of course, for-comprehensions are more general than just their use with
\texttt{Option}. They can be used for the lists, arrays, iterators,
ranges, streams, and other types in the Scala standard library that
support the \texttt{map}, \texttt{flatMap}, and \texttt{withFilter} (or
\texttt{filter}) operations. m Consider a list \texttt{persons} of
person objects with \texttt{name} and \texttt{age} fields. We can
collect the names of all persons who are age 21 and above as follows:

\begin{verbatim}
    for (p <- persons if p.age >= 21) yield p.name
\end{verbatim}

This is equivalent to the following \texttt{List} expression

\begin{verbatim}
    filter (p => p.age >= 21) map (p => p.name)
    
\end{verbatim}

\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 \texttt{e} for each binding generated by the
enumerator sequence \texttt{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} \texttt{p\ \textless{}-\ e} produces a sequence of
  zero or more bindings from expression \texttt{e} by matching each
  value against pattern \texttt{p}.
\item
  A \emph{value definition} \texttt{p\ =\ e} binds the names in pattern
  \texttt{p} to the result of evaluating the expression \texttt{e}.
\item
  A \emph{guard} \texttt{if\ 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 \texttt{p\ \textless{}-\ e}, where
  \texttt{p} is a pattern and \texttt{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 \texttt{withFilter} to filter out those items that do not
  match the pattern \texttt{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 \texttt{...} 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 \texttt{p\ \textless{}-\ e} followed by a
    guard \texttt{if\ g} to a single generator

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

    where \texttt{x,...,xn} are the free variables of \texttt{p}.
  \item
    Translate a generator \texttt{p\ \textless{}-\ e} followed by a
    value definition \texttt{p1\ =\ e1} to the following generator of
    pairs of values, where \texttt{x} and \texttt{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 \texttt{x@p} means that name \texttt{x} is bound to
the value of the expression \texttt{p}.

Note: Above we do not consider the imperative for-loops. These can also
be translated as above except that the imperative method
\texttt{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 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 expression:

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

If no \texttt{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 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 \texttt{map}, \texttt{flatMap}, and
\texttt{withFilter} have particular type signatures. However, a
particular setup for some collection type \texttt{C} with elements of
type \texttt{A} is the following:

\begin{verbatim}
    trait C[A] {
      def map[B](f: A => B): C[B]
      def flatMap[B](f: A => C[B]): C[B]
      def withFilter(p: A => Boolean): C[A]
    }
\end{verbatim}

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 \texttt{map}, Scala allows
  for-comprehensions consisting of a single generator.
\item
  If the data type defines both \texttt{flatMap} and \texttt{map}, Scala
  allows for-comprehensions consisting of several generators.
\item
  If the data type defines \texttt{withFilter}, Scala allows
  for-comprehensions with guards. (If \texttt{withFilter} is not defined
  but \texttt{filter} is, Scala will currently use \texttt{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 \texttt{Option} type earlier. We
do the same for the \texttt{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 \texttt{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
\texttt{Either}.

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

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

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

\begin{verbatim}
     def map[B](f: A => B): Either[E, B] = 
       this match {
         case Left(e)  => Left(e)
         case Right(a) => Right(f(a))
       }

     def flatMap[EE >: E, B](f: A => Either[EE, B]): Either[EE, B] =
       this match {
         case Left(e)  => Left(e)
         case Right(a) => f(a)
       }
        
      def orElse[EE >: E, AA >: A](b: => Either[EE, AA]): Either[EE, AA] =
        this match {
          case Left(_)  => b
          case Right(a) => Right(a)
        }
\end{verbatim}

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

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

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

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

We can use the \texttt{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 \texttt{Exception} generated as we do in the
\texttt{safeDiv} function below.

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

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

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

Chapter 4 of \emph{Functional Programming in Scala} describes other
functions for type \texttt{Either}.

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

Both \texttt{Option} and \texttt{Either} appear in the standard library.

The standard library \texttt{Option} type is similar to the one
developed here, but the library version is missing some of the extended
functions described in Chapter 4.

The standard library \texttt{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.

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
\texttt{Option} and \texttt{Either} and functions such as \texttt{map},
\texttt{flatMap}, \texttt{filter}, and \texttt{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
  \url{Option2.scala}
\item
  \url{Either2.scala}
\end{itemize}

\end{document}