% 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 Functional Data Structures},
  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}}}}
\usepackage{graphicx,grffile}
\makeatletter
\def\maxwidth{\ifdim\Gin@nat@width>\linewidth\linewidth\else\Gin@nat@width\fi}
\def\maxheight{\ifdim\Gin@nat@height>\textheight\textheight\else\Gin@nat@height\fi}
\makeatother
% Scale images if necessary, so that they will not overflow the page
% margins by default, and it is still possible to overwrite the defaults
% using explicit options in \includegraphics[width, height, ...]{}
\setkeys{Gin}{width=\maxwidth,height=\maxheight,keepaspectratio}
\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\\
Functional Data Structures}
\author{\textbf{H. Conrad Cunningham}}
\date{\textbf{6 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)

\textbf{Note:} This set of notes accompanies my lectures on Chapter 3 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{]}, and \emph{Type System Concepts} {[}Cunningham
2019c{]}.

\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}{2}

\hypertarget{functional-data-structures}{%
\section{Functional Data Structures}\label{functional-data-structures}}

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

To do functional programming, we construct programs from collections of
pure functions. Given the same arguments, a \emph{pure function} always
returns the same result. The function application is thus referentially
transparent. By \emph{referentially transparent} we mean that a name or
symbol always denotes the same value in some well-defined context in the
program.

Such a pure function does not have \emph{side effects}. It does not
modify a variable or a data structure in place. It does not set throw an
exception or perform input/output. It does nothing that can be seen from
outside the function except return its value.

Thus the data structures in pure functional programs must be
\emph{immutable}, not subject to change as the program executes. (If
\emph{mutable} data structures are used, no changes to the structures
must be detectable outside the function.)

For example, the Scala empty list---written as \VERB|\NormalTok{Nil}| or
\VERB|\NormalTok{List()}|---represents a value as immutable as the
numbers \VERB|\DecValTok{2}| and \VERB|\DecValTok{7}|.

Just as evaluating the expression
\VERB|\DecValTok{2}\NormalTok{ + }\DecValTok{7}| yields a new number
\VERB|\DecValTok{9}|, the concatenation of list \VERB|\NormalTok{c}| and
list \VERB|\NormalTok{d}| yields a new list (written
\VERB|\NormalTok{c ++ d}|) with the elements of \VERB|\NormalTok{c}|
followed by the elements of \VERB|\NormalTok{d}|. It does not change the
values of the original input lists \VERB|\NormalTok{c}| and
\VERB|\NormalTok{d}|.

Perhaps surprisingly, list concatenation does not require both lists to
be copied, as we see below.

\hypertarget{a-list-algebraic-data-type}{%
\subsection{\texorpdfstring{A \texttt{List} algebraic data
type}{A List algebraic data type}}\label{a-list-algebraic-data-type}}

To explore how to build immutable data structures in Scala, we examine a
simplified, singly linked list structure implemented as an algebraic
data type. This \emph{list data type} is similar to the builtin Scala
\VERB|\NormalTok{List}| data type.

What do we mean by algebraic data type?

\hypertarget{algebraic-data-types}{%
\subsubsection{Algebraic data types}\label{algebraic-data-types}}

An \emph{algebraic data type} is a type formed by combining other types,
that is, it is a \emph{composite} data type. The data type is created by
an algebra of operations of two primary kinds:

\begin{itemize}
\item
  a \emph{sum} operation that constructs values to have one variant
  among several possible variants. These sum types are also called
  \emph{tagged}, \emph{disjoint union}, or \emph{variant} types.

  The combining operation is the alternation operator, which denotes the
  choice of one but not both between two alternatives.
\item
  a \emph{product} operation that combines several values
  (i.e.~\emph{fields}) together to construct a single value. These are
  \emph{tuple} and \emph{record} types.

  The combining operation is the Cartesian product from set theory.
\end{itemize}

We can combine sums and products recursively into arbitrarily large
structures.

An \emph{enumerated type} is a sum type in which the constructors take
no arguments. Each constructor corresponds to a single value.

\hypertarget{adt-confusion}{%
\subsubsection{ADT confusion}\label{adt-confusion}}

Although sometimes the acronym ADT is used for both, an \emph{algebraic
data type} is a different concept from an \emph{abstract data type}.

\begin{itemize}
\item
  We specify an algebraic data type with its \emph{syntax} (i.e.
  structure)---with rules on how to compose and decompose them.
\item
  We specify an abstract data type with its \emph{semantics} (i.e.
  meaning)---with rules about how the operations behave in relation to
  one another.

  TODO: Update paragraph below better for Scala course

  The modules we build with abstract interfaces, contracts, and data
  abstraction, such as the Rational Arithmetic modules from Chapter 7 of
  reference {[}Cunningham 2018{]}, are abstract data types.
\end{itemize}

Perhaps to add to the confusion, in functional programming we sometimes
use an algebraic data type to help define an abstract data type.

\hypertarget{using-a-scala-trait}{%
\subsubsection{Using a Scala trait}\label{using-a-scala-trait}}

A \emph{list} consists of a sequence of values, all of which have the
same type. It is a hierarchical data structure. It is either
\emph{empty} or it is a pair consisting of a \emph{head} element and a
\emph{tail} that is itself a list of elements.

We define \VERB|\NormalTok{List}| as an abstract type using a Scala
\VERB|\KeywordTok{trait}|. (We could also use an
\VERB|\KeywordTok{abstract} \KeywordTok{class}| instead of a
\VERB|\KeywordTok{trait}|.) We define the \emph{constructors} for the
algebraic data type using the Scala
\VERB|\KeywordTok{case} \KeywordTok{class}| and
\VERB|\KeywordTok{case} \KeywordTok{object}| features.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{sealed} \KeywordTok{trait}\NormalTok{ List[+A]}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ Nil }\KeywordTok{extends}\NormalTok{ List[Nothing] }
    \KeywordTok{case} \KeywordTok{class}\NormalTok{ Cons[+A](head: A, tail: List[A]) }\KeywordTok{extends}\NormalTok{ List[A]}
\end{Highlighting}
\end{Shaded}

Thus \VERB|\NormalTok{List}| is a \emph{sum type} with two alternatives:

\begin{itemize}
\item
  \VERB|\NormalTok{Nil}| constructs the singleton case object that
  represents the empty list.
\item
  \VERB|\FunctionTok{Cons}\NormalTok{(h,t)}| constructs a new list from
  an element \VERB|\NormalTok{h}|, called the \emph{head}, and a list
  \VERB|\NormalTok{t}|, called the \emph{tail}.
\end{itemize}

\VERB|\NormalTok{Cons}| itself is a \emph{product (tuple) type} with two
fields, one of which is itself a \VERB|\NormalTok{List}|.

The \VERB|\KeywordTok{sealed}| keyword tells the Scala compiler that all
alternative cases (i.e.~subtypes) are declared in the current source
file. No new cases can be added elsewhere. This enables the compiler to
generate safe and efficient code for pattern matching.

As we have seen previously, for each
\VERB|\KeywordTok{case} \KeywordTok{class}| and
\VERB|\KeywordTok{case} \KeywordTok{object}|, the Scala compiler
generates:

\begin{itemize}
\item
  a constructor function (e.g.~\VERB|\NormalTok{Cons}|)
\item
  accessor functions (methods) for each field
  (e.g.~\VERB|\NormalTok{head}| and \VERB|\NormalTok{tail}| on
  \VERB|\NormalTok{Cons}|)
\item
  new definitions for \VERB|\NormalTok{equals}|,
  \VERB|\NormalTok{hashcode}|, and \VERB|\NormalTok{toString}|
\end{itemize}

In addition, the \VERB|\KeywordTok{case} \KeywordTok{object}| construct
generates a \emph{singleton object}---a new type with exactly one
instance.

Programs can use the constructors to build instances and use the pattern
matching to recognize the structure of instances and decompose them for
processing.

\VERB|\NormalTok{List}| is a polymorphic type. What does polymorphic
mean? We examine that in the next subsection.

\hypertarget{aside-on-haskell}{%
\paragraph{Aside on Haskell}\label{aside-on-haskell}}

In Haskell, an algebraic data type similar to the Scala
\VERB|\NormalTok{List[A]}| is the following:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{data} \DataTypeTok{List}\NormalTok{ a }\OtherTok{=} \DataTypeTok{Nil} \OperatorTok{|} \DataTypeTok{Cons}\NormalTok{ a (}\DataTypeTok{List}\NormalTok{ a)}
                  \KeywordTok{deriving}\NormalTok{ (}\DataTypeTok{Show}\NormalTok{, }\DataTypeTok{Eq}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

The Haskell \VERB|\DataTypeTok{List}\NormalTok{ a}| is a type similar to
the Scala \texttt{List{[}A{]}}. However, \VERB|\NormalTok{Nil}| and
\VERB|\NormalTok{Cons[A]}| are subtypes of \VERB|\NormalTok{List}| in
Scala, but they are not types in Haskell. In Haskell, they are
constructor functions that return values of type
\VERB|\DataTypeTok{List}\NormalTok{ a}|.

\hypertarget{polymorphism}{%
\subsubsection{Polymorphism}\label{polymorphism}}

\emph{Polymorphism} refers to the property of having ``many shapes''. In
programming languages, we are primarily interested in how
\emph{polymorphic} function names (or operator symbols) are associated
with implementations of the functions (or operations).

Scala is a hybrid, object-functional language. Its type system supports
all three types of polymorphism discussed in the notes on
\href{../TypeConcepts/TypeSystemConcepts.html}{\emph{Type System
Concepts}}.

\begin{itemize}
\item
  \emph{subtyping} by extending classes and traits
\item
  \emph{parametric polymorphism} by using generic type parameters,
\item
  \emph{overloading} through both the Java-like mechanisms and
  Haskell-like ``type classes''
\end{itemize}

Scala's \emph{type class pattern} builds on the languages's
\VERB|\KeywordTok{implicit}| classes and conversions. A type class
enables a programmer to enrich an existing class with an extended
interface and new methods without redefining the class or subclassing
it.

For example, Scala extends the Java \VERB|\NormalTok{String}| class
(which is \VERB|\KeywordTok{final}| and thus cannot be subclassed) with
new features from the \VERB|\NormalTok{RichString}| wrapper class. The
Scala \VERB|\KeywordTok{implicit}| mechanisms associate the two classes
``behind the scene''. We defer further discussion of implicits until
later in the semester.

Note: The type class feature arose from the language Haskell. Similar
capabilities are called extension methods in C\# and protocols in
Clojure and Elixir.

The \VERB|\NormalTok{List}| data type defined above is polymorphic; it
exhibits both subtyping and parametric polymorphism.
\VERB|\NormalTok{Nil}| and \VERB|\NormalTok{Cons}| are subtypes of
\VERB|\NormalTok{List}|. The generic type parameter \VERB|\NormalTok{A}|
denotes the type of the elements that occur in the list. For example,
\VERB|\NormalTok{List[Double]}| denotes a list of double-precision
floating point numbers.

What does the \VERB|\NormalTok{+}| annotation mean in the definition
\VERB|\NormalTok{List[+A]}|?

\hypertarget{variance}{%
\subsubsection{Variance}\label{variance}}

The presence of both subtyping and parametric polymorphism leads to the
question of how these features interact---that is, the concept of
\emph{variance}.

\hypertarget{covariance-and-contravariance}{%
\paragraph{Covariance and
contravariance}\label{covariance-and-contravariance}}

Suppose we have a supertype \VERB|\NormalTok{Fish}| with a subtype
\VERB|\NormalTok{Bass}|, which in turn has a subtype
\VERB|\NormalTok{BlackBass}|.

For generic data type \VERB|\NormalTok{List[A]}| as defined above,
consider \VERB|\NormalTok{List[Fish]}| and
\VERB|\NormalTok{List[Bass]}|.

\begin{itemize}
\item
  If \VERB|\NormalTok{List[Bass]}| is a subtype of
  \VERB|\NormalTok{List[Fish]}|, preserving the subtyping order, then
  the relationship is \emph{covariant}.
\item
  If \VERB|\NormalTok{List[Fish]}| is a subtype of
  \VERB|\NormalTok{List[Bass]}|, reversing the subtyping order, then the
  relationship is \emph{contravariant}.
\item
  If there is no subtype relationship between
  \VERB|\NormalTok{List[Fish]}| and \VERB|\NormalTok{List[Bass]}|, the
  the relationship is \emph{invariant} (sometimes called
  \emph{nonvariant}).
\end{itemize}

In the Scala definition \VERB|\NormalTok{List[+A]}| above, the
\VERB|\NormalTok{+}| annotation in front of the \VERB|\NormalTok{A}| is
a \emph{variance annotation}. The \VERB|\NormalTok{+}| means that
parameter \VERB|\NormalTok{A}| is a \emph{covariant} parameter of
\VERB|\NormalTok{List}|. That is, for all types \VERB|\NormalTok{X}| and
\VERB|\NormalTok{Y}| such that \VERB|\NormalTok{X}| is a subtype of
\VERB|\NormalTok{Y}|, then then \VERB|\NormalTok{List[X]}| is a is
subtype of \VERB|\NormalTok{List[Y]}|.

If we leave off the variance annotation, then \VERB|\NormalTok{List}|
would be \emph{invariant} in the type parameter. Regardless of how types
\VERB|\NormalTok{X}| and \VERB|\NormalTok{Y}| may be related,
\VERB|\NormalTok{List[X]}| and \VERB|\NormalTok{List[Y]}| are unrelated.

If we were put a \VERB|\NormalTok{-}| annotation in front of
\VERB|\NormalTok{A}|, then we declare parameter \VERB|\NormalTok{A}| to
be \emph{contravariant}. That is, for all types \VERB|\NormalTok{X}| and
\VERB|\NormalTok{Y}| such that \VERB|\NormalTok{X}| is a subtype of
\VERB|\NormalTok{Y}|, then then \VERB|\NormalTok{List[Y]}| is a is
subtype of \VERB|\NormalTok{List[X]}|.

In the definition of the \VERB|\NormalTok{List}| algebraic data type,
\VERB|\NormalTok{Nil}| extends \VERB|\NormalTok{List[Nothing]}|.
\VERB|\NormalTok{Nothing}| is a subtype of all other types. In
conjunction with covariance, the \VERB|\NormalTok{Nil}| list can be
considered a list of any type.

Aside: Note the position of \VERB|\NormalTok{Nothing}| in Scala's
\href{https://docs.scala-lang.org/tour/unified-types.html}{unified type
hierarchy}.

\hypertarget{function-subtypes}{%
\paragraph{Function subtypes}\label{function-subtypes}}

Now consider first-class functions. When is one function a subtype of
another?

From the notes on
\href{../TypeConcepts/TypeSystemConcepts.html}{\emph{Type System
Concepts}} {[}Cunningham 2019c{]}, we recall that we should be able to
safely \emph{substitute} elements of a subtype \VERB|\NormalTok{S}| for
elements of type \VERB|\NormalTok{T}| because \VERB|\NormalTok{S}|'s
operations behave the ``same'' as \VERB|\NormalTok{T}|'s operations.
That is, the relationship satisfies the \emph{Liskov Substitution
Principle} {[}Liskov 1987{]} {[}Wikipedia 2019{]}.

Using the \VERB|\NormalTok{Fish}| type hierarchy above, consider a
function of type \VERB|\NormalTok{Bass => X}| (for some type
\VERB|\NormalTok{X}|). It would be unsafe to use a function of type
\VERB|\NormalTok{BlackBass => X}| in its place. The function would be
undefined for any values that are of type \VERB|\NormalTok{Bass}| but
are not of type \VERB|\NormalTok{BlackBass}|. So a function with a input
type \VERB|\NormalTok{BlackBass}| is not a subtype of a function with
input \VERB|\NormalTok{Bass}|.

However, a function of type \VERB|\NormalTok{Fish => X}| would be
defined for any value that is of type \VERB|\NormalTok{Bass}|. So we
need to examine the relationships between the output types to determine
what the subtyping relationship is between the functions.

Consider a function of type \VERB|\NormalTok{X => Bass}|. A function of
type \VERB|\NormalTok{X => BlackBass}| can be safely used in its place
because a \VERB|\NormalTok{BlackBass}| is a \VERB|\NormalTok{Bass}|, so
the function yields a value of the expected type.

However, a function of type \VERB|\NormalTok{X => Fish}| cannot be
safely used in place of the \VERB|\NormalTok{X => Bass}| function. It
may yield some value that is a \VERB|\NormalTok{Fish}| but not a
\VERB|\NormalTok{Bass}|.

Thus we could safely use a \VERB|\NormalTok{Bass => Bass}| function in
place of a \VERB|\NormalTok{Bass => Fish}|,
\VERB|\NormalTok{BlackBass => Bass}|, or
\VERB|\NormalTok{BlackBass => Fish}| function. Thus
\VERB|\NormalTok{Bass => Bass}| is a subtype of the others.

However, we could not safely use a \VERB|\NormalTok{Bass => Bass}|
function in place of a \VERB|\NormalTok{Bass => BlackBass}|,
\VERB|\NormalTok{BlackBass => BlackBass}|,
\VERB|\NormalTok{Fish => Fish}|, \VERB|\NormalTok{Fish => Bass}|, or
\VERB|\NormalTok{Fish => BlackBass}| function. Thus
\VERB|\NormalTok{Bass => Bass}| is a not a subtype of the others.

Bringing these observations together, a function type
\VERB|\NormalTok{S1 => S2}| is a subtype of a function type
\VERB|\NormalTok{T1 => T2}| if and only if:

\begin{itemize}
\item
  \VERB|\NormalTok{T1}| is a subtype of \VERB|\NormalTok{S1}|
  (i.e.~contravariant on the input type)
\item
  \VERB|\NormalTok{S2}| is a subtype of \VERB|\NormalTok{T2}|
  (i.e.~covariant on the output type)
\end{itemize}

This general observation is consistent with the applicable theory.

For a Scala function of type \VERB|\NormalTok{S => T}|, we thus say the
\VERB|\NormalTok{S}| is in a \emph{contravariant position} and
\VERB|\NormalTok{T}| is in a \emph{covariant position}.

TODO: May want to discuss multiargument functions.

\hypertarget{defining-functions-in-companion-object}{%
\subsubsection{Defining functions in companion
object}\label{defining-functions-in-companion-object}}

The \emph{companion object} for a trait or class is a singleton object
with the same name as the trait or class. The companion object for the
\VERB|\NormalTok{List}| trait is a convenient place to define functions
for manipulating the lists.

Because \VERB|\NormalTok{List}| is a Scala algebraic data type
(implemented with case classes), we can use pattern matching in our
function definitions. Pattern matching helps enable the \emph{form of
the algorithm} to match the \emph{form of the data structure}. Or, in
terms that Chiusano and Bjarnason use, it helps in \emph{following types
to implementations} {[}Chiusano 2015{]}.

Note: Other writers call this design approach \emph{type-driven
development} {[}Brady 2017{]} or \emph{type-first development}
{[}Petricek 2012{]}.

This is considered elegant. It is also pragmatic. The structure of the
data often suggests the algorithm needed for a task.

In general, lists have two cases that must be handled: the empty list
(represented by \VERB|\NormalTok{Nil}|) and the nonempty list
(represented by \VERB|\NormalTok{Cons}|). The first yields a \emph{base
leg} of a recursive algorithm; the second yields a \emph{recursive leg}.

Breaking a definition for a list-processing function into these two
cases is usually a good place to begin. We must ensure the recursion
\emph{terminates}---that each successive recursive call gets closer to
the base case.

\hypertarget{function-to-sum-a-list}{%
\subsubsection{Function to sum a list}\label{function-to-sum-a-list}}

Consider a function \VERB|\NormalTok{sum}| to add together all the
elements in a list of integers. That is, if the list is
\(v_{1}, v_{2}, v_{3}, \cdots, v_{n}\), then the sum of the list is the
value resulting from inserting the addition operator between consecutive
elements of the list:

\begin{quote}
\(v_{1} + v_{2} + v_{3} + \cdots + v_{n}\)
\end{quote}

Because addition is an \emph{associative} operation, the additions can
be computed in any order. That is, for any integers \(x\), \(y\), and
\(z\):

\begin{quote}
\((x + y) + z = x + (y + z)\)
\end{quote}

We can use the form of the data to guide the form of the algorithm---or
\emph{follow the type to the implementation} of the function.

What is the sum of an empty list?

Because there are no numbers to add, then, intuitively, zero seems to be
the proper value for the sum.

In general, if some binary operation is inserted between the elements of
a list, then the result for an empty list is the \emph{identity element}
for the operation. Zero is the identity element for addition because,
for all integers \(x\):

\begin{quote}
\(0 + x = x = x + 0\)
\end{quote}

Now, how can we compute the sum of a nonempty list?

Because a nonempty list has at least one element, we can remove one
element and add it to the sum of the rest of the list. Note that the
``rest of the list'' is a simpler (i.e.~shorter) list than the original
list. This suggests a recursive definition.

The fact that we define lists recursively as a \VERB|\NormalTok{Cons}|
of a head element with a tail list suggests that we structure the
algorithm around the structure of the \emph{beginning} of the list.

Bringing together the two cases above, we can define the function
\VERB|\NormalTok{sum}| in Scala using pattern matching as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{sum}\NormalTok{(ints: List[Int]): Int = ints }\KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case}\NormalTok{ Nil        => }\DecValTok{0} 
        \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(x,xs) => x + }\FunctionTok{sum}\NormalTok{(xs)}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

The length of a non-nil argument decreases by one for each successive
recursive application. Thus \VERB|\NormalTok{sum}| will eventually be
applied to a \VERB|\NormalTok{Nil}| argument and terminate.

For a list consisting of elements 2, 4, 6, and 8, that is,

\begin{Shaded}
\begin{Highlighting}[]
    \FunctionTok{Cons}\NormalTok{(}\DecValTok{2}\NormalTok{,}\FunctionTok{Cons}\NormalTok{(}\DecValTok{4}\NormalTok{,}\FunctionTok{Cons}\NormalTok{(}\DecValTok{6}\NormalTok{,}\FunctionTok{Cons}\NormalTok{(}\DecValTok{8}\NormalTok{,Nil))))}
\end{Highlighting}
\end{Shaded}

function \VERB|\NormalTok{sum}| computes:

\begin{verbatim}
    2 + (4 + (6 + (8 + 0)))
\end{verbatim}

Function \VERB|\NormalTok{sum}| is backward linear recursive; its time
and space complexity are both O(\(n\)), where \(n\) is the length of the
input list.

We could, of course, redefine this to use a tail-recursive auxiliary
function. With \emph{tail call optimization}, the recursion could be
converted into a loop. It would still be order O(\(n\))in time
complexity (but with a smaller constant factor) and O(1) space.

\hypertarget{function-to-multiply-a-list}{%
\subsubsection{Function to multiply a
list}\label{function-to-multiply-a-list}}

Now consider a function \VERB|\NormalTok{product}| to multiply together
a list of floating point numbers. The product of an empty list is 1
(which is the identity element for multiplication). The product of a
nonempty list is the head of the list multiplied by the product of the
tail of the list, except that, if a 0 occurs anywhere in the list, the
product of the list is 0. We can thus define \VERB|\NormalTok{product}|
with two bases cases and one recursive case, as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{product}\NormalTok{(ds: List[Double]): Double = ds }\KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case}\NormalTok{ Nil          => }\FloatTok{1.0}
        \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(}\FloatTok{0.0}\NormalTok{, _) => }\FloatTok{0.0}
        \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(x,xs)   => x * }\FunctionTok{product}\NormalTok{(xs)}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

Note: 0 is the \emph{zero element} for the multiplication operation on
real numbers. That is, for all real numbers \(x\):

\begin{quote}
\(0 * x = x * 0 = 0\)
\end{quote}

For a list consisting of elements 2.0, 4.0, 6.0, and 8.0, that is,

\begin{Shaded}
\begin{Highlighting}[]
    \FunctionTok{Cons}\NormalTok{(}\FloatTok{2.0}\NormalTok{,}\FunctionTok{Cons}\NormalTok{(}\FloatTok{4.0}\NormalTok{,}\FunctionTok{Cons}\NormalTok{(}\FloatTok{6.0}\NormalTok{,}\FunctionTok{Cons}\NormalTok{(}\FloatTok{8.0}\NormalTok{,Nil))))}
\end{Highlighting}
\end{Shaded}

function \VERB|\NormalTok{product}| computes:

\begin{Shaded}
\begin{Highlighting}[]
    \FloatTok{2.0}\NormalTok{ * (}\FloatTok{4.0}\NormalTok{ * (}\FloatTok{6.0}\NormalTok{ * (}\FloatTok{8.0}\NormalTok{ * }\FloatTok{1.0}\NormalTok{))) }
\end{Highlighting}
\end{Shaded}

For a list consisting of elements 2.0, 0.0, 6.0, and 8.0, function
\VERB|\NormalTok{product}| ``short circuits'' the computation as:

\begin{Shaded}
\begin{Highlighting}[]
    \FloatTok{2.0}\NormalTok{ * }\FloatTok{0.0}
\end{Highlighting}
\end{Shaded}

Like \VERB|\NormalTok{sum}|, function \VERB|\NormalTok{product}| is
backward linear recursive; it has a worst-case time complexity of
O(\(n\)), where \(n\) is the length of the input list. It terminates
because the argument of each successive recursive call is one element
shorter than the previous call, approaching one of the base cases.

\hypertarget{function-to-remove-adjacent-duplicates}{%
\subsubsection{Function to remove adjacent
duplicates}\label{function-to-remove-adjacent-duplicates}}

Consider the problem of removing adjacent duplicate elements from a
list. That is, we want to replace a group of adjacent elements having
the same value by a single occurrence of that value.

As with the above functions, we let the form of the data guide the form
of the algorithm, following the type to the implementation.

The notion of adjacency is only meaningful when there are two or more of
something. Thus, in approaching this problem, there seem to be three
cases to consider:

\begin{itemize}
\item
  The argument is a list whose first two elements are duplicates; in
  which case one of them should be removed from the result.
\item
  The argument is a list whose first two elements are not duplicates; in
  which case both elements are needed in the result.
\item
  The argument is a list with fewer than two elements; in which case the
  remaining element, if any, is needed in the result.
\end{itemize}

Of course, we must be careful that sequences of more than two duplicates
are handled properly.

Our algorithm thus can examine the first two elements of the list. If
they are equal, then the first is discarded and the process is repeated
recursively on the list remaining. If they are not equal, then the first
element is retained in the result and the process is repeated on the
list remaining. In either case the remaining list is one element shorter
than the original list. When the list has fewer than two elements, it is
simply returned as the result.

In Scala, we can define function \VERB|\NormalTok{remdups}| as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ remdups[A](ls: List[A]): List[A] = ls }\KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(x, }\FunctionTok{Cons}\NormalTok{(y,ys)) =>}
            \KeywordTok{if}\NormalTok{ (x == y)}
                \FunctionTok{remdups}\NormalTok{(}\FunctionTok{Cons}\NormalTok{(y,ys))         }\CommentTok{// duplicate}
            \KeywordTok{else}
                \FunctionTok{Cons}\NormalTok{(x,}\FunctionTok{remdups}\NormalTok{(}\FunctionTok{Cons}\NormalTok{(y,ys))) }\CommentTok{// non-duplicate}
        \KeywordTok{case}\NormalTok{ _                   => ls}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

Function \VERB|\NormalTok{remdups}| puts the base case last in the
pattern match to take advantage of the wildcard match using
\VERB|\NormalTok{_}|. This needs to match either \VERB|\NormalTok{Nil}|
and \VERB|\FunctionTok{Cons}\NormalTok{(_,Nil)}|.

The function also depends upon the ability to compare any two elements
of the list for equality. Because \VERB|\NormalTok{equals}| is builtin
operation on all types in Scala, we can define this function
polymorphically Without constraints on the type variable
\VERB|\NormalTok{A}|.

Like the previous functions, \VERB|\NormalTok{remdups}| is backward
linear recursive; it takes a number of steps that is proportional to the
length of the list. This function has a recursive call on both the
duplicate and non-duplicate legs. Each of these recursive calls uses a
list that is shorter than the previous call, thus moving closer to the
base case.

\hypertarget{variadic-function-apply}{%
\subsubsection{\texorpdfstring{Variadic function
\texttt{apply}}{Variadic function apply}}\label{variadic-function-apply}}

We can also add a function \VERB|\NormalTok{apply}| to the companion
object \VERB|\NormalTok{List}|.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ apply[A](as: A*): List[A] = }
        \KeywordTok{if}\NormalTok{ (as.}\FunctionTok{isEmpty}\NormalTok{) }
\NormalTok{            Nil }
        \KeywordTok{else} 
            \FunctionTok{Cons}\NormalTok{(as.}\FunctionTok{head}\NormalTok{, }\FunctionTok{apply}\NormalTok{(as.}\FunctionTok{tail}\NormalTok{: _*)) }
\end{Highlighting}
\end{Shaded}

Scala treats an \VERB|\NormalTok{apply}| method in an
\VERB|\KeywordTok{object}| specially. We can invoke the
\VERB|\NormalTok{apply}| method using a postfix \VERB|\NormalTok{()}|
operator. Given a singleton object \VERB|\NormalTok{X}| with an
\VERB|\NormalTok{apply}| method, the Scala complier translates the
notation \VERB|\FunctionTok{X}\NormalTok{(p)}| into the method call
\VERB|\NormalTok{X.}\FunctionTok{apply}\NormalTok{(p)}|.

In the \VERB|\NormalTok{List}| data type, function
\VERB|\NormalTok{apply}| is a \emph{variadic function}. It accepts zero
or more arguments of type \VERB|\NormalTok{A}| as denoted by the type
annotation \VERB|\NormalTok{A*}| in the parameter list. Scala collects
these arguments into a \VERB|\NormalTok{Seq}| (sequence) data type for
processing within the function. The special syntax \VERB|\NormalTok{_*}|
reverses this and passes a sequence to another function as variadic
parameters. Builtin Scala data structures such as lists, queues, and
vectors implement \VERB|\NormalTok{Seq}|. It provides methods such as
the \VERB|\NormalTok{isEmpty}|, \VERB|\NormalTok{head}|, and
\VERB|\NormalTok{tail}| methods used in \VERB|\NormalTok{apply}|.

It is common to define a variadic \VERB|\NormalTok{apply}| methods for
algebraic data types. This method enables us to create instances of the
data type conveniently. For example,
\VERB|\NormalTok{List(}\DecValTok{1}\NormalTok{,}\DecValTok{2}\NormalTok{,}\DecValTok{3}\NormalTok{)}|
creates a three-element list of integers with \VERB|\DecValTok{1}| at
the head.

\hypertarget{data-sharing}{%
\subsection{Data sharing}\label{data-sharing}}

Suppose we have the declaration

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{val}\NormalTok{ xs = }\FunctionTok{Cons}\NormalTok{(}\DecValTok{1}\NormalTok{,}\FunctionTok{Cons}\NormalTok{(}\DecValTok{2}\NormalTok{,}\FunctionTok{Cons}\NormalTok{(}\DecValTok{3}\NormalTok{,Nil)))}
\end{Highlighting}
\end{Shaded}

or the more concise equivalent using the \VERB|\NormalTok{apply}|
method:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{val}\NormalTok{ xs = List(}\DecValTok{1}\NormalTok{,}\DecValTok{2}\NormalTok{,}\DecValTok{3}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

As we learned in the data structures course, we can implement this list
as a linked list \VERB|\NormalTok{xs}| with three cells with the values
\VERB|\DecValTok{1}|, \VERB|\DecValTok{2}|, and \VERB|\DecValTok{3}|, as
shown in Figure 3-1.

\begin{figure}
\centering
\includegraphics{fig_03_01.png}
\caption{\textbf{Figure 3-1: Data sharing in lists}}
\end{figure}

Consider the following declarations

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{val}\NormalTok{ ys = }\FunctionTok{Cons}\NormalTok{(}\DecValTok{0}\NormalTok{,xs)}
    \KeywordTok{val}\NormalTok{ zs = xs.}\FunctionTok{tail}
\end{Highlighting}
\end{Shaded}

where

\begin{itemize}
\item
  \VERB|\FunctionTok{Cons}\NormalTok{(}\DecValTok{0}\NormalTok{,xs)}|
  returns a list that has a new cell containing \VERB|\DecValTok{0}| in
  front of the previous list
\item
  \VERB|\NormalTok{xs.}\FunctionTok{tail}| returns the list consisting
  of the last two elements of \VERB|\NormalTok{xs}|
\end{itemize}

If the linked list \VERB|\NormalTok{xs}| is immutable (i.e.~the values
and pointers in the three cells cannot be changed), then neither of
these operations requires any copying.

\begin{itemize}
\item
  The first just constructs a new cell containing \VERB|\DecValTok{0}|,
  links it to the first cell in list \VERB|\NormalTok{xs}|, and
  initializes \VERB|\NormalTok{ys}| with a reference to the new cell.
\item
  The second just returns a reference to the second cell in list
  \VERB|\NormalTok{xs}| and initializes \VERB|\NormalTok{zs}| with this
  reference.
\item
  The original list \VERB|\NormalTok{xs}| is still available, unaltered.
\end{itemize}

This is called \emph{data sharing}. It enables the programming language
to implement immutable data structures efficiently, without copying in
many key cases.

Also, such functional data structures are \emph{persistent} because
existing references are never changed by operations on the data
structure.

\hypertarget{function-to-take-tail-of-list}{%
\subsubsection{Function to take tail of
list}\label{function-to-take-tail-of-list}}

Consider a function that takes a \VERB|\NormalTok{List}| and returns its
tail \VERB|\NormalTok{List}|. (This is different from the
\VERB|\NormalTok{tail}| accessor method on \VERB|\NormalTok{Cons}|.)

If the \VERB|\NormalTok{List}| is a \VERB|\NormalTok{Cons}|, then the
function can return the \VERB|\NormalTok{tail}| element of the cell.
What should it do if the list is a \VERB|\NormalTok{Nil}|?

There are several possibilities:

\begin{itemize}
\item
  return \VERB|\NormalTok{Nil}|
\item
  throw an exception (with perhaps a custom error string)
\item
  leave the function undefined in this case (which would result with a
  standard pattern match exception)
\end{itemize}

Generally speaking, the first choice seems misleading. It seems
illogical for an empty list to have a tail. And consider a typical usage
of the function. It is normally an error for a program to attempt to get
the tail of an empty list. A program can efficiently check whether a
list is empty or not. So, in this case, it is probably better to take
the second or third approach.

We choose to implement \VERB|\NormalTok{tailList}| so that it explicitly
throws an exception. It can be defined in the companion object for
\VERB|\NormalTok{List}| as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ tailList[A](ls: List[A]): List[A] = ls }\KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case}\NormalTok{ Nil        => sys.}\FunctionTok{error}\NormalTok{(}\StringTok{"tail of empty list"}\NormalTok{)}
        \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(_,xs) => xs}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

Above, the value of the \VERB|\NormalTok{head}| field of the
\VERB|\NormalTok{Cons}| pattern is irrelevant in the computation on the
right-hand side. There is no need to introduce a new variable for that
value, so we use the wildcard variable \VERB|\NormalTok{_}| to indicate
that the value is not needed.

Function \VERB|\NormalTok{tailList}| is O(1) in time complexity. It does
not need to copy the list. It is sufficient for it to just return a
reference to the tail of the original immutable list. This return value
shares the data with its input argument.

\hypertarget{function-to-drop-from-beginning-of-list}{%
\subsubsection{Function to drop from beginning of
list}\label{function-to-drop-from-beginning-of-list}}

We can generalize \VERB|\NormalTok{tailList}| to a function
\VERB|\NormalTok{drop}| that removes the first \VERB|\NormalTok{n}|
elements of a list, as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ drop[A](ls: List[A], n: Int): List[A] =}
        \KeywordTok{if}\NormalTok{ (n <= }\DecValTok{0}\NormalTok{) ls}
        \KeywordTok{else}\NormalTok{ ls }\KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case}\NormalTok{ Nil        => Nil}
            \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(_,xs) => }\FunctionTok{drop}\NormalTok{(xs, n}\DecValTok{-1}\NormalTok{)}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

The \VERB|\NormalTok{drop}| function terminates when either the list
argument is \VERB|\NormalTok{Nil}| or the integer argument 0 or
negative. The function eventually terminates because each recursive call
both shortens the list and decrements the integer.

This function takes a different approach to the empty list issue than
\VERB|\NormalTok{tailList}| does. Although it seems illogical to take
the \VERB|\NormalTok{tailList}| of an empty list, dropping the first
element from an empty list seems subtly different. Given that we often
use \VERB|\NormalTok{drop}| in cases where the length of the input list
is unknown, dropping the first element of an empty list does not
necessarily indicate a program error.

Suppose \VERB|\NormalTok{drop}| throws an exception when called with an
empty list. To avoid this situation, the program might need to determine
the length of the list argument. This is inefficient, usually requiring
a traversal of the entire list to count the elements.

\hypertarget{function-to-append-lists}{%
\subsubsection{Function to append
lists}\label{function-to-append-lists}}

Consider the definition of an \emph{append} (list concatenation)
function. We must define the \VERB|\NormalTok{append}| function in terms
of the constructors \VERB|\NormalTok{Nil}| and \VERB|\NormalTok{Cons}|,
already defined list functions, and recursive applications of itself.

As with previous functions, we follow the type to the
implementation---let the form of the data guide the form of the
algorithm.

The \VERB|\NormalTok{Cons}| constructor takes an element as its left
operand and a list as its right operand and returns a new list with the
left operand as the head and the right operand as the tail.

Similarly, append must take a list as its left operand and a list as its
right operand and return a new list with the left operand as the initial
segment and the right operand as the final segment.

Given the definition of \VERB|\NormalTok{Cons}|, it seems reasonable
that an algorithm for \VERB|\NormalTok{append}| must consider the
structure of its left operand. Thus we consider the cases for nil and
non-nil left operands.

\begin{itemize}
\item
  If the left operand is \VERB|\NormalTok{Nil}|, then the function can
  just return the right operand.
\item
  If the left operand is a \VERB|\NormalTok{Cons}| (that is, non-nil),
  then the result consists of the left operand's head followed by the
  append of the left operand's tail to the right operand.
\end{itemize}

In following the type to the implementation, we use the form of the left
operand in a pattern match. We define \VERB|\NormalTok{append}| as
follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ append[A](ls: List[A], rs: List[A]): List[A] = ls }\KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case}\NormalTok{ Nil        => rs}
        \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(x,xs) => }\FunctionTok{Cons}\NormalTok{(x, }\FunctionTok{append}\NormalTok{(xs, rs))}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

For the recursive application of \VERB|\NormalTok{append}|, the length
of the left operand decreases by one. Hence the left operand of an
\VERB|\NormalTok{append}| application eventually becomes
\VERB|\NormalTok{Nil}|, allowing the evaluation to terminate.

The number of steps needed to evaluate
\VERB|\FunctionTok{append}\NormalTok{(as,bs)}| is proportional to the
length of \VERB|\NormalTok{as}|, the left operand. That is, it is
O(\(n\)), where \(n\) is the length of list \texttt{as}.

Moreover, \VERB|\FunctionTok{append}\NormalTok{(as,bs)}| only needs to
copy the list \VERB|\NormalTok{as}|. The list \VERB|\NormalTok{bs}| is
shared between the second operand and the result. If we did a similar
function to append two (mutable) arrays, we would need to copy both
input arrays to create the output array. Thus, in this case, a linked
list is more efficient than arrays!

The append operation has a number of useful mathematical (algebraic)
properties, for example, associativity and an identity element.

Associativity---For any finite lists \VERB|\NormalTok{xs}|,
\VERB|\NormalTok{ys}|, and \VERB|\NormalTok{zs}|:

\begin{Shaded}
\begin{Highlighting}[]
    \FunctionTok{append}\NormalTok{(xs,}\FunctionTok{append}\NormalTok{(ys,zs)) = }\FunctionTok{append}\NormalTok{(}\FunctionTok{append}\NormalTok{(xs,ys),zs)}
\end{Highlighting}
\end{Shaded}

Identity---For any finite list \VERB|\NormalTok{xs}|:

\begin{Shaded}
\begin{Highlighting}[]
    \FunctionTok{append}\NormalTok{(Nil,xs) = }\FunctionTok{append}\NormalTok{(xs,Nil) = xs}
\end{Highlighting}
\end{Shaded}

Scala's builtin \VERB|\NormalTok{List}| type uses the infix operator
\VERB|\NormalTok{++}| for the ``append'' operation. For this operator,
associativity can be stated conveniently with the equation:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    xs ++ (ys ++ zs) = (xs ++ ys) ++ zs}
\end{Highlighting}
\end{Shaded}

Mathematically, the \VERB|\NormalTok{List}| data type and the binary
operation \VERB|\NormalTok{append}| form a kind of abstract algebra
called a \emph{monoid}. Function \VERB|\NormalTok{append}| is closed
(i.e.~it takes two lists and gives a list back), is associative, and has
an identity element.

Aside: For more information on operations and algebraic structures, see
Chapter 80,
\href{https://john.cs.olemiss.edu/~hcc/csci450/ELIFP/Ch80/80_Math_Review.html}{``Review
of Relevant Mathematics''}, in the Haskell-based book
\href{https://john.cs.olemiss.edu/~hcc/csci450/ELIFP/ExploringLanguages.html}{\emph{Exploring
Languages with Interpreters and Functional Programming}} {[}Cunningham
2018{]}. For discussion of how to prove properties like those above, see
Chapter 25,
\href{https://john.cs.olemiss.edu/~hcc/csci450/ELIFP/Ch25/25_Laws.html}{``Proving
Haskell Laws''}, in the same book.

\hypertarget{other-list-functions}{%
\subsection{Other list functions}\label{other-list-functions}}

\hypertarget{tail-recursive-function-reverse}{%
\subsubsection{Tail recursive function
reverse}\label{tail-recursive-function-reverse}}

Consider the problem of reversing the order of the elements in a list.

Again we can use the structure of the data to guide the algorithm
development. If the argument is a nil list, then the function returns a
nil list. If the argument is a non-nil list, then the function can
append the head element at the back of the reversed tail.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ rev[A](ls: List[A]): List[A] = ls }\KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case}\NormalTok{ Nil        => Nil}
        \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(x,xs) => }\FunctionTok{append}\NormalTok{(}\FunctionTok{rev}\NormalTok{(xs),List(x))}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

Given that evaluation of \VERB|\NormalTok{append}| terminates, the
evaluation of \VERB|\NormalTok{rev}| also terminates because all
recursive applications decrease the length of the argument by one.

How efficient is this function?

The evaluation of \VERB|\NormalTok{rev}| takes O(\(n^{2}\)) steps, where
\(n\) is the length of the argument. There are O(\(n\)) applications of
\VERB|\NormalTok{rev}| . For each application of \VERB|\NormalTok{rev}|
there are O(\(n\)) applications of \VERB|\NormalTok{append}| .

The initial list and its reverse do not share data.

Function \VERB|\NormalTok{rev}| has a number of useful properties, for
example a distribution and an inverse properties.

Distribution---For any finite lists \VERB|\NormalTok{xs}| and
\VERB|\NormalTok{ys}|:

\begin{Shaded}
\begin{Highlighting}[]
    \FunctionTok{rev}\NormalTok{(}\FunctionTok{append}\NormalTok{(xs,ys)) = }\FunctionTok{append}\NormalTok{(}\FunctionTok{rev}\NormalTok{(ys), }\FunctionTok{rev}\NormalTok{(xs))}
\end{Highlighting}
\end{Shaded}

Inverse---For any finite list \VERB|\NormalTok{xs}|:

\begin{Shaded}
\begin{Highlighting}[]
    \FunctionTok{rev}\NormalTok{(}\FunctionTok{rev}\NormalTok{(xs)) = xs}
\end{Highlighting}
\end{Shaded}

Can we define a function to reverse a list using a ``more efficient''
tail recursive solution?

As we have seen, a common technique for converting a backward linear
recursive definition like \VERB|\NormalTok{rev}| into a \emph{tail
recursive} definition is to use an \emph{accumulating parameter} to
build up the desired result incrementally. A possible definition for a
tail recursive auxiliary function is:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ revAux[A](ls: List[A], as: List[A]): List[A] = ls }\KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case}\NormalTok{ Nil        => as}
        \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(x,xs) => }\FunctionTok{revAux}\NormalTok{(xs,}\FunctionTok{Cons}\NormalTok{(x,as))}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

In this definition parameter \VERB|\NormalTok{as}| is the accumulating
parameter. The head of the first argument becomes the new head of the
accumulating parameter for the tail recursive call. The tail of the
first argument becomes the new first argument for the tail recursive
call.

We know that \VERB|\NormalTok{revAux}| terminates because, for each
recursive application, the length of the first argument decreases toward
the base case of \VERB|\NormalTok{Nil}|.

We note that \VERB|\FunctionTok{rev}\NormalTok{(xs)}| is equivalent to
\VERB|\FunctionTok{revAux}\NormalTok{(xs,Nil)}| .

To define a single-argument replacement for \VERB|\NormalTok{rev}| , we
can embed the definition of \VERB|\NormalTok{revAux’}| as an
\emph{auxiliary} function within the definition of a new function
\VERB|\NormalTok{reverse}| .

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ reverse[A](ls: List[A]): List[A] = \{}
        \KeywordTok{def}\NormalTok{ revAux[A](rs: List[A], as: List[A]): List[A] = }
\NormalTok{            rs }\KeywordTok{match}\NormalTok{ \{}
                \KeywordTok{case}\NormalTok{ Nil        => as}
                \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(x,xs) => }\FunctionTok{revAux}\NormalTok{(xs,}\FunctionTok{Cons}\NormalTok{(x,as))}
\NormalTok{            \}}
        \FunctionTok{revAux}\NormalTok{(ls,Nil)}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

Function \VERB|\FunctionTok{reverse}\NormalTok{(xs)}| returns the value
from \VERB|\FunctionTok{revAux}\NormalTok{(xs,Nil)}|.

How efficient is this function?

The evaluation of \VERB|\NormalTok{reverse}| takes O(\(n\)) steps, where
\(n\) is the length of the argument. There is one application of
\VERB|\NormalTok{revAux}| for each element; \VERB|\NormalTok{revAux}|
requires a single O(1) \VERB|\NormalTok{Cons}| operation in the
accumulating parameter.

Where did the increase in efficiency come from?

Each application of \VERB|\NormalTok{rev}| applies
\VERB|\NormalTok{append}|, a linear time (i.e.~O(\(n\))) function. In
\texttt{revAux}, we replaced the applications of
\VERB|\NormalTok{append}| by applications of \VERB|\NormalTok{Cons}|, a
constant time (i.e.~O(1)) function.

In addition, a compiler or interpreter that does tail call optimization
can translate this tail recursive call into a loop on the host machine.

\hypertarget{higher-order-function-dropwhile}{%
\subsubsection{Higher-order function
dropWhile}\label{higher-order-function-dropwhile}}

Consider a function \VERB|\NormalTok{dropWhile}| that removes elements
from the front of a \VERB|\NormalTok{List}| while its predicate argument
(a Boolean function) holds.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ dropWhile [A](ls: List[A], f: A => Boolean): List[A] =}
\NormalTok{        ls }\KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(x,xs) }\KeywordTok{if} \FunctionTok{f}\NormalTok{(x) => }\FunctionTok{dropWhile}\NormalTok{(xs, f)}
            \KeywordTok{case}\NormalTok{ _                  => ls}
\NormalTok{        \}}
\end{Highlighting}
\end{Shaded}

This higher-order function terminates when either the list is empty or
the head of the list makes the predicate false. For each successive
recursive call, the list argument is one element shorter than the
previous call, so the function eventually terminates.

If evaluation of function argument \VERB|\NormalTok{p}| is O(1), then
function \VERB|\NormalTok{dropWhile}| has worst-case time complexity
O(\(n\)), where \(n\) is the length of its first operand. The result
list shares data with the input list.

\hypertarget{curried-function-dropwhile}{%
\subsubsection{Curried function
dropWhile}\label{curried-function-dropwhile}}

We often pass \emph{anonymous functions} to higher-order utility
functions like \VERB|\NormalTok{dropwhile}|, which has the signature:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ dropWhile[A](ls: List[A], f: A => Boolean): List[A]}
\end{Highlighting}
\end{Shaded}

When we call \VERB|\NormalTok{dropWhile}| with an anonymous function for
\VERB|\NormalTok{f}|, we must specify the type of its argument, as
follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{val}\NormalTok{ xs: List[Int] = List(}\DecValTok{1}\NormalTok{,}\DecValTok{2}\NormalTok{,}\DecValTok{3}\NormalTok{,}\DecValTok{4}\NormalTok{,}\DecValTok{5}\NormalTok{)}
    \KeywordTok{val}\NormalTok{ ex1 = }\FunctionTok{dropWhile}\NormalTok{(xs, (x: Int) => x < }\DecValTok{4}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

Even though it is clear from the first argument that higher order
argument \VERB|\NormalTok{f}| must take an integer as its argument, the
Scala \emph{type inference} mechanism cannot detect this.

However, if we rewrite \VERB|\NormalTok{dropWhile}| in the following
form, type inference can work as we want:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ dropWhile2[A](ls: List[A])(f: A => Boolean): List[A] =}
\NormalTok{        ls }\KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(x,xs) }\KeywordTok{if} \FunctionTok{f}\NormalTok{(x) => }\FunctionTok{dropWhile2}\NormalTok{(xs)(f)}
            \KeywordTok{case}\NormalTok{ _                  => ls}
\NormalTok{        \}}
\end{Highlighting}
\end{Shaded}

Function \VERB|\NormalTok{dropWhile2}| is written in \emph{curried} form
above. In this form, a function that takes two arguments can be
represented as a function that takes the first argument and returns a
function, which itself takes the second argument.

If we apply \VERB|\NormalTok{dropWhile2}| to just the first argument, we
get a function. We call this a \emph{partial application} of
\VERB|\NormalTok{dropWhile2}|.

More generally, a function that takes multiple arguments can be
represented by a function that takes its arguments in groups of one or
more from left to right. If the function is partially applied to the
first group, it returns a function that takes the remaining groups, and
so forth.

Currying and partial application are directly useful in a number of ways
in our programs. Here currying is indirectly useful by assisting type
inference. If a function is defined with multiple groups of arguments,
the type information flows from one group to another, left to right. In
\VERB|\NormalTok{dropWhile2}|, the first argument group binds type
variable \VERB|\NormalTok{A}| to \VERB|\NormalTok{Int}|. Then this
binding can be used in the second argument group.

\hypertarget{generalizing-to-higher-order-functions}{%
\subsection{Generalizing to Higher Order
Functions}\label{generalizing-to-higher-order-functions}}

\hypertarget{fold-right}{%
\subsubsection{Fold Right}\label{fold-right}}

Consider the \VERB|\NormalTok{sum}| and \VERB|\NormalTok{product}|
functions we defined above, ignoring the short-cut handling of the zero
element in \VERB|\NormalTok{product}|.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{sum}\NormalTok{(ints: List[Int]): Int = ints }\KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case}\NormalTok{ Nil        => }\DecValTok{0} 
        \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(x,xs) => x + }\FunctionTok{sum}\NormalTok{(xs)}
\NormalTok{    \}}

    \KeywordTok{def} \FunctionTok{product}\NormalTok{(ds: List[Double]): Double = ds }\KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case}\NormalTok{ Nil          => }\FloatTok{1.0}
        \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(x,xs)   => x * }\FunctionTok{product}\NormalTok{(xs)}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

What do \VERB|\NormalTok{sum}| and \VERB|\NormalTok{product}| have in
common? What differs?

Both exhibit the same \emph{pattern of computation}.

\begin{itemize}
\item
  Both take a list as input.

  But the element type differs. Function \VERB|\NormalTok{sum}| takes a
  list of \VERB|\NormalTok{Int}| values and \VERB|\NormalTok{product}|
  takes a list of \VERB|\NormalTok{Double}| values.
\item
  Both insert a binary operator between all the consecutive elements of
  the list in order to reduce the list to a single value.

  But the binary operation differs. Function \VERB|\NormalTok{sum}|
  applies integer addition and \VERB|\NormalTok{product}| applies
  double-precision floating-point multiplication.
\item
  Both group the operations from the right to the left.
\item
  Both functions return some value for an empty list. The function
  extends nonempty input lists to implicitly include this value as the
  ``rightmost'' value of the input list.

  But the actual value differs.

  Function \VERB|\NormalTok{sum}| returns integer 0, the (right)
  identity element for addition.

  Function \VERB|\NormalTok{product}| returns 1.0, the (right) identity
  element for multiplication.

  In general, this value could be something other than the (right)
  identity element.
\item
  Both return a value of the same element type as the input list.

  But the input type differs, as we noted above.
\end{itemize}

Both functions insert operations of type \VERB|\NormalTok{(A,A) => A}|
between elements a list of type \VERB|\NormalTok{List[A]}|, for some
generic type \VERB|\NormalTok{A}|.

But these are special cases of more general operations of type
\VERB|\NormalTok{(A,B) => B}|. In this case, the value returned must be
of type \VERB|\NormalTok{B}| in the case of both empty and nonempty
lists.

Whenever we recognize a pattern like this, we can systematically
\emph{generalize the function} definition as follows:

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Do a \emph{scope-commonality-variability} (SCV) analysis on the set of
  related functions.

  That is, identify what is to be included and what not (i.e.~the
  \emph{scope}), the parts of functions that are the same (the
  \emph{commonalities} or \emph{frozen spots}), and the parts that
  differ (the \emph{variabilities} or \emph{hot spots}).
\item
  Leave the commonalities in the generalized function's body.
\item
  Move the variabilities into the generalized function's header---its
  type signature and parameter list.

  \begin{itemize}
  \item
    If the part moved to the generalized function's parameter list is an
    expression, then make that part a function with a parameter for each
    local variable accessed.
  \item
    If a data type potentially differs from a specific type used in the
    set of related functions, then add a type parameter to the
    generalized function.
  \item
    If the same data value or type appears in multiple roles, then
    consider adding distinct type or value parameters for each role.
  \end{itemize}
\item
  Consider other approaches if the generalized function's type signature
  and parameter list become too complex.

  For example, we can introduce new data or procedural abstractions for
  parts of the generalized function. These may be in the same ``module''
  (i.e.~object, class, etc.) as the generalized function, in an
  appropriately defined separate ``module'' that is imported, etc. A
  separate module may better accomplish the desired parameterization of
  the function.
\end{enumerate}

A similar approach can be used to generalize a whole class.

Following the above guidelines, we can express the common pattern from
\VERB|\NormalTok{sum}| and \VERB|\NormalTok{product}| as a new (broadly
useful) polymorphic, higher-order function \VERB|\NormalTok{foldRight}|,
which we define as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ foldRight[A,B](ls: List[A], z: B)(f: (A, B) => B): B = }
\NormalTok{        ls }\KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case}\NormalTok{ Nil        => z}
            \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(x,xs) => }\FunctionTok{f}\NormalTok{(x, }\FunctionTok{foldRight}\NormalTok{(xs, z)(f))}
\NormalTok{        \}}
\end{Highlighting}
\end{Shaded}

This function:

\begin{itemize}
\item
  passes in the binary operation \VERB|\NormalTok{f}| that combines the
  list elements
\item
  passes in the element \VERB|\NormalTok{z}| to be returned for empty
  lists (often the right identity element for the operation, but this is
  not required)
\item
  uses two type parameters \VERB|\NormalTok{A}| and
  \VERB|\NormalTok{B}|---one for the type of elements in the list and
  one for the type of the result
\end{itemize}

The \VERB|\NormalTok{foldRight}| function ``folds'' the list elements
(of type \VERB|\NormalTok{A}|) into a value (of type
\VERB|\NormalTok{B}|) by ``inserting'' operation \VERB|\NormalTok{f}|
between the elements, with value \VERB|\NormalTok{z}| ``appended'' as
the rightmost element. For example,
\VERB|\FunctionTok{foldRight}\NormalTok{(List(}\DecValTok{1}\NormalTok{,}\DecValTok{2}\NormalTok{,}\DecValTok{3}\NormalTok{),z)(f)}|
expands to
\VERB|\FunctionTok{f}\NormalTok{(}\DecValTok{1}\NormalTok{,}\FunctionTok{f}\NormalTok{(}\DecValTok{2}\NormalTok{,}\FunctionTok{f}\NormalTok{(}\DecValTok{3}\NormalTok{,z)))}|.

Function \VERB|\NormalTok{foldRight}| is not tail recursive, so it needs
a new stack frame for each element of the input list. If its list
argument is long or the folding function itself is expensive, then the
function can terminate with a \emph{stack overflow} error.

We can specialize \VERB|\NormalTok{foldRight}| to have the same
functionality as \VERB|\NormalTok{sum}| and \VERB|\NormalTok{product}|.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{sum2}\NormalTok{(ns: List[Int]) =}
        \FunctionTok{foldRight}\NormalTok{(ns, }\DecValTok{0}\NormalTok{)((x,y) => x + y)}

    \KeywordTok{def} \FunctionTok{product2}\NormalTok{(ns: List[Double]) =}
        \FunctionTok{foldRight}\NormalTok{(ns, }\FloatTok{1.0}\NormalTok{)(_ * _)}
\end{Highlighting}
\end{Shaded}

The expression \VERB|\NormalTok{(_ * _)}| in \VERB|\NormalTok{product2}|
is a concise notation for the anonymous function
\VERB|\NormalTok{(x,y) => x * y}|. The two underscores denote two
distinct anonymous variables. This concise notation can be used in a
context where Scala's type inference mechanism can determine the types
of the anonymous variables.
{]}\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash\textbackslash{}\\
We can construct a recursive function to compute the length of a
polymorphic list. However, we can also express this computation using
\VERB|\NormalTok{foldRight}|, as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ length[A](ls: List[A]): Int =}
        \FunctionTok{foldRight}\NormalTok{(ls, }\DecValTok{0}\NormalTok{)((_,acc) => acc + }\DecValTok{1}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

We use the \VERB|\NormalTok{z}| parameter to accumulate the count,
starting it at 0. Higher order argument \VERB|\NormalTok{f}| is a
function that takes an element of the list as its left argument and the
previous accumulator as its right argument and returns it incremented by
1. In this application, \VERB|\NormalTok{z}| is not the identity element
for \VERB|\NormalTok{f}| by a convenient beginning value for the
counter.

We can construct an ``append'' function that uses
\VERB|\NormalTok{foldRight}| as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ append2[A](ls: List[A], rs: List[A]): List[A] =}
        \FunctionTok{foldRight}\NormalTok{(ls, rs)(}\FunctionTok{Cons}\NormalTok{(_,_))}
\end{Highlighting}
\end{Shaded}

Here the the list that \VERB|\NormalTok{foldRight}| operates on the
first argument of the append. The \VERB|\NormalTok{z}| parameter is the
entire second argument and the combining function is just \texttt{Cons}.
So the effect is to replace the \VERB|\NormalTok{Nil}| at the end of the
first list by the entire second list.

We can construct a recursive function that takes a list of lists and
returns a ``flat'' list that has the same elements in the same order. We
can also express this \VERB|\NormalTok{concat}| function in terms of
\VERB|\NormalTok{foldRight}|, as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ concat[A](ls: List[List[A]]): List[A] =}
        \FunctionTok{foldRight}\NormalTok{(ls, Nil: List[A])(append) }
\end{Highlighting}
\end{Shaded}

Function \VERB|\NormalTok{append}| takes time proportional to the length
of its first list argument. This argument does not grow larger because
of right associativity of \VERB|\NormalTok{foldRight}|. Thus
\VERB|\NormalTok{concat}| takes time proportional to the total length of
all the lists.

Above, we ``pass'' the \VERB|\NormalTok{append}| function without
writing an explicit anonymous function definition (i.e.~\emph{function
literal}) such as
\VERB|\NormalTok{(xs,ys) => }\FunctionTok{append}\NormalTok{(xs,ys)}| or
\VERB|\FunctionTok{append}\NormalTok{(_,_)}|.

In \VERB|\NormalTok{concat}|, for which Scala can infer the types of
\VERB|\NormalTok{append}|'s arguments, the compiler can generate the
needed function literal. In other cases, we would need to use
\emph{partial application} notation such as

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    append _}
\end{Highlighting}
\end{Shaded}

or an explicit function literal such as

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    (xs: List[A], ys: List[A]) => }\FunctionTok{append}\NormalTok{(xs,ys)}
\end{Highlighting}
\end{Shaded}

to enable the compiler to infer the types.

Above we defined function \VERB|\NormalTok{foldRight}| as a backward
recursive function that processes the elements of a list one by one.
However, as we have seen, it is often more useful to think of
\VERB|\NormalTok{foldRight}| as a powerful list operator that reduces
the element of the list into a single value. We can combine
\VERB|\NormalTok{foldRight}| with other operators to conveniently
construct list processing programs.

\hypertarget{fold-left}{%
\subsubsection{Fold Left}\label{fold-left}}

We designed function \VERB|\NormalTok{foldRight}| above as a backward
linear recursive function with the signature:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    foldRight[A,B](as: List[A], z: B)(f: (A, B) => B): B}
\end{Highlighting}
\end{Shaded}

As noted:

\begin{Shaded}
\begin{Highlighting}[]
    \FunctionTok{foldRight}\NormalTok{(List(}\DecValTok{1}\NormalTok{,}\DecValTok{2}\NormalTok{,}\DecValTok{3}\NormalTok{),z)(f) == }\FunctionTok{f}\NormalTok{(}\DecValTok{1}\NormalTok{,}\FunctionTok{f}\NormalTok{(}\DecValTok{2}\NormalTok{,}\FunctionTok{f}\NormalTok{(}\DecValTok{3}\NormalTok{,z)))}
\end{Highlighting}
\end{Shaded}

Consider a function \VERB|\NormalTok{foldLeft}| such that:

\begin{Shaded}
\begin{Highlighting}[]
    \FunctionTok{foldLeft}\NormalTok{(List(}\DecValTok{1}\NormalTok{,}\DecValTok{2}\NormalTok{,}\DecValTok{3}\NormalTok{),z)(f) == }\FunctionTok{f}\NormalTok{(}\FunctionTok{f}\NormalTok{(}\FunctionTok{f}\NormalTok{(z,}\DecValTok{1}\NormalTok{),}\DecValTok{2}\NormalTok{),}\DecValTok{3}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

This function folds from the left. It offers us the opportunity to use
parameter \VERB|\NormalTok{z}| as an accumulating parameter in a tail
recursive implementation, as follows:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    @annotation.}\FunctionTok{tailrec}
    \KeywordTok{def}\NormalTok{ foldLeft[A,B](ls: List[A], z: B)(f: (B, A) => B): B = }
\NormalTok{        ls }\KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case}\NormalTok{ Nil        => z}
            \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(x,xs) => }\FunctionTok{foldLeft}\NormalTok{(xs, }\FunctionTok{f}\NormalTok{(z,x))(f)}
\NormalTok{        \}}
\end{Highlighting}
\end{Shaded}

In the first line above, we \emph{annotate} function
\VERB|\NormalTok{foldLeft}| as tail recursive using
\VERB|\NormalTok{@annotation.}\FunctionTok{tailrec}|. If the function is
not tail recursive, the compiler gives an error, rather than silently
generating code that does not use tail call optimization (i.e.~does not
convert the recursion to a loop).

We can implement list sum, product, and length functions with
\VERB|\NormalTok{foldLeft}|, similar to what we did with
\VERB|\NormalTok{foldRight}|.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{sum3}\NormalTok{(ns: List[Int]) =}
        \FunctionTok{foldLeft}\NormalTok{(ns, }\DecValTok{0}\NormalTok{)(_ + _) }
        
    \KeywordTok{def} \FunctionTok{product3}\NormalTok{(ns: List[Double]) =}
        \FunctionTok{foldLeft}\NormalTok{(ns, }\FloatTok{1.0}\NormalTok{)(_ * _)}
\end{Highlighting}
\end{Shaded}

Given that addition and multiplication of numbers are associative and
have identity elements, \VERB|\NormalTok{sum3}| and
\VERB|\NormalTok{product3}| use the same values for parameters
\VERB|\NormalTok{z}| and \VERB|\NormalTok{f}| as
\VERB|\NormalTok{foldRight}|.

Function \VERB|\NormalTok{length2}| that uses
\VERB|\NormalTok{foldLeft}| is like \VERB|\NormalTok{length}| except
that the arguments of function \VERB|\NormalTok{f}| are reversed.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ length2[A](ls: List[A]): Int =}
        \FunctionTok{foldLeft}\NormalTok{(ls, }\DecValTok{0}\NormalTok{)((acc,_) => acc + }\DecValTok{1}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

We can also implement list reversal using \VERB|\NormalTok{foldLeft}| as
follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ reverse2[A](ls: List[A]): List[A] =}
        \FunctionTok{foldLeft}\NormalTok{(ls, List[A]())((acc,x) => }\FunctionTok{Cons}\NormalTok{(x,acc))}
\end{Highlighting}
\end{Shaded}

This gives a solution similar to the tail recursive
\VERB|\NormalTok{reverse}| function above. The \VERB|\NormalTok{z}|
value is initially an empty list; the folding function
\VERB|\NormalTok{f}| uses \VERB|\NormalTok{Cons}| to ``attach'' each
element of the list to front of the accumulator, incrementally building
the list in reverse order.

Because \VERB|\NormalTok{foldLeft}| is tail recursive and
\VERB|\NormalTok{foldRight}| is not, \VERB|\NormalTok{foldLeft}| is
usually safer and more efficient to use in than
\VERB|\NormalTok{foldRight}|. (If the list argument is lazily evaluated
or the function argument \VERB|\NormalTok{f}| is nonstrict in at least
one of its arguments, then there are other factors to consider. We will
discuss what we mean by ``lazily evaluated'' and ``nonstrict'' later in
the course.)

To avoid the stack overflow situation with \VERB|\NormalTok{foldRight}|,
we can first apply \VERB|\NormalTok{reverse}| to the list argument and
then apply \VERB|\NormalTok{foldLeft}| as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ foldRight2[A,B](ls: List[A], z: B)(f: (A,B) => B): B =}
        \FunctionTok{foldLeft}\NormalTok{(}\FunctionTok{reverse}\NormalTok{(ls), z)((b,a) => }\FunctionTok{f}\NormalTok{(a,b))}
\end{Highlighting}
\end{Shaded}

The combining function in the call to \VERB|\NormalTok{foldLeft}| is the
same as the one passed to \VERB|\NormalTok{foldRight2}| except that its
arguments are reversed.

\hypertarget{map}{%
\subsubsection{Map}\label{map}}

Consider the following two functions, noting their type signatures and
patterns of recursion.

The first, \VERB|\NormalTok{squareAll}|, takes a list of integers and
returns the corresponding list of squares of the integers.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{squareAll}\NormalTok{(ns: List[Int]): List[Int] = ns }\KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case}\NormalTok{ Nil         => Nil}
        \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(x, xs) => }\FunctionTok{Cons}\NormalTok{(x*x, }\FunctionTok{squareAll}\NormalTok{(xs))}
\NormalTok{    \} }
\end{Highlighting}
\end{Shaded}

The second, \VERB|\NormalTok{lengthAll}|, takes a list of lists and
returns the corresponding list of the lengths of the element lists

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ lengthAll[A](lss: List[List[A]]): List[Int] =}
\NormalTok{        lss }\KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case}\NormalTok{ Nil           => Nil}
            \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(xs, xss) => }\FunctionTok{Cons}\NormalTok{(}\FunctionTok{length}\NormalTok{(xs),}\FunctionTok{lengthAll}\NormalTok{(xss))}
\NormalTok{        \}}
\end{Highlighting}
\end{Shaded}

Although these functions take different kinds of data (a list of
integers versus a list of polymorphically typed lists) and apply
different operations (squaring versus list length), they exhibit the
same pattern of computation. That is, both take a list and apply some
function to each element to generate a resulting list of the same size
as the original.

As with the fold functions, the combination of polymorphic typing and
higher-order functions allows us to abstract this pattern of computation
into a higher-order function.

We can abstract the pattern of computation common to
\VERB|\NormalTok{squareAll}| and \VERB|\NormalTok{lengthAll}| as the
(broadly useful) function \VERB|\NormalTok{map}|, defined as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ map[A,B](ls: List[A])(f: A => B): List[B] = ls }\KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case}\NormalTok{ Nil        => Nil}
        \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(x,xs) => }\FunctionTok{Cons}\NormalTok{(}\FunctionTok{f}\NormalTok{(x),}\FunctionTok{map}\NormalTok{(xs)(f))}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

Function \VERB|\NormalTok{map}| takes a list of type
\VERB|\NormalTok{A}| elements, applies function \VERB|\NormalTok{f}| of
type \VERB|\NormalTok{A => B}| to each element, and returns a list of
the resulting type \VERB|\NormalTok{B}| elements.

Thus we can redefine \VERB|\NormalTok{squareAll}| and
\VERB|\NormalTok{lengthAll}| using \VERB|\NormalTok{map}| as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{squareAll2}\NormalTok{(ns: List[Int]): List[Int] =}
        \FunctionTok{map}\NormalTok{(ns)(x => x*x)}
        
    \KeywordTok{def}\NormalTok{ lengthAll2[A](lss: List[List[A]]): List[Int] =}
        \FunctionTok{map}\NormalTok{(lss)(length)}
\end{Highlighting}
\end{Shaded}

We can implement \VERB|\NormalTok{map}| itself using
\VERB|\NormalTok{foldRight}| as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ map1[A,B](ls: List[A])(f: A => B): List[B] =}
        \FunctionTok{foldRight}\NormalTok{(ls, Nil: List[B])((x,xs) => }\FunctionTok{Cons}\NormalTok{(}\FunctionTok{f}\NormalTok{(x),xs))}
\end{Highlighting}
\end{Shaded}

The folding function
\VERB|\NormalTok{(x,xs) => }\FunctionTok{Cons}\NormalTok{(}\FunctionTok{f}\NormalTok{(x),xs)}|
applies the mapping function \VERB|\NormalTok{f}| to the next element of
the list (moving right to left) and attaches the result on the front of
the processed tail.

As implemented above, function \VERB|\NormalTok{map}| is backward
recursive; it thus requires a stack frame for each element of its list
argument. For long lists, the recursion can cause a stack overflow
error. Function \VERB|\NormalTok{map1}| uses
\VERB|\NormalTok{foldRight}|, which has similar characteristics. So we
need to use these functions with care. However, we can use the reversal
technique illustrated in \VERB|\NormalTok{foldRight2}| if necessary.

We could also optimize function \VERB|\NormalTok{map}| using \emph{local
mutation}. That is, we can use a mutable data structure within the
\VERB|\NormalTok{map}| function but not allow this structure to be
accessed outside of \VERB|\NormalTok{map}|. The following function takes
that approach, using a \VERB|\NormalTok{ListBuffer}|:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ map2[A,B](ls: List[A])(f: A => B): List[B] = \{}
        \KeywordTok{val}\NormalTok{ buf = }\KeywordTok{new}\NormalTok{ collection.}\FunctionTok{mutable}\NormalTok{.}\FunctionTok{ListBuffer}\NormalTok{[B]}

\NormalTok{        @annotation.}\FunctionTok{tailrec}
        \KeywordTok{def} \FunctionTok{go}\NormalTok{(ls: List[A]): Unit = ls }\KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case}\NormalTok{ Nil        => ()}
            \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(x,xs) => buf += }\FunctionTok{f}\NormalTok{(x); }\FunctionTok{go}\NormalTok{(xs)}
\NormalTok{        \}}
    
        \FunctionTok{go}\NormalTok{(ls)}
\NormalTok{        List(buf.}\FunctionTok{toList}\NormalTok{: _*) }
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

A \VERB|\NormalTok{ListBuffer}| is a mutable list data structure from
the Scala library. The operation \VERB|\NormalTok{+=}| appends a single
element to the end of the buffer in constant time. The method
\VERB|\NormalTok{toList}| converts the \VERB|\NormalTok{ListBuffer}| to
a Scala immutable list, which is similar to the data structure we are
developing in this module.

\hypertarget{filter}{%
\subsubsection{Filter}\label{filter}}

Consider the following two functions.

The first, \VERB|\NormalTok{getEven}|, takes a list of integers and
returns the list of those integers that are even (i.e.~are multiples of
2). The function preserves the relative order of the elements in the
list.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{getEven}\NormalTok{(ns: List[Int]): List[Int] = ns }\KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case}\NormalTok{ Nil        => Nil}
        \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(x,xs) =>}
            \KeywordTok{if}\NormalTok{ (x % }\DecValTok{2}\NormalTok{ == }\DecValTok{0}\NormalTok{)  }\CommentTok{// divisible evenly by 2}
                \FunctionTok{Cons}\NormalTok{(x,}\FunctionTok{getEven}\NormalTok{(xs))}
            \KeywordTok{else}
                \FunctionTok{getEven}\NormalTok{(xs)}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

The second, \VERB|\NormalTok{doublePos}|, takes a list of integers and
returns the list of doubles of the positive integers from the input
list; it preserves the order of the elements.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{doublePos}\NormalTok{(ns: List[Int]): List[Int]  = ns }\KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case}\NormalTok{ Nil        => Nil}
        \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(x,xs) =>}
            \KeywordTok{if}\NormalTok{ (}\DecValTok{0}\NormalTok{ < x)}
                \FunctionTok{Cons}\NormalTok{(}\DecValTok{2}\NormalTok{*x, }\FunctionTok{doublePos}\NormalTok{(xs))}
            \KeywordTok{else}
                \FunctionTok{doublePos}\NormalTok{(xs)}
\NormalTok{    \}           }
\end{Highlighting}
\end{Shaded}

We can abstract the pattern of computation common to
\VERB|\NormalTok{getEven}| and \VERB|\NormalTok{doublePos}| as the
(broadly useful) function \VERB|\NormalTok{filter}|, defined as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ filter[A](ls: List[A])(p: A => Boolean): List[A] =}
\NormalTok{        ls }\KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case}\NormalTok{ Nil        => Nil}
            \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(x,xs) =>}
                \KeywordTok{val}\NormalTok{ fs = }\FunctionTok{filter}\NormalTok{(xs)(p)}
                \KeywordTok{if}\NormalTok{ (}\FunctionTok{p}\NormalTok{(x)) }\FunctionTok{Cons}\NormalTok{(x,fs) }\KeywordTok{else}\NormalTok{ fs}
\NormalTok{        \}}
\end{Highlighting}
\end{Shaded}

Function \VERB|\NormalTok{filter}| takes a predicate
\VERB|\NormalTok{p}| of type \VERB|\NormalTok{A => Boolean}| a list of
type \VERB|\NormalTok{List[A]}| and returns a list containing those
elements that satisfy \VERB|\NormalTok{p}|, in the same order as the
input list.

Therefore, we can redefine \VERB|\NormalTok{getEven}| and
\VERB|\NormalTok{doublePos}| as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{getEven2}\NormalTok{(ns: List[Int]): List[Int] =}
        \FunctionTok{filter}\NormalTok{(ns)(x => x % }\DecValTok{2}\NormalTok{ == }\DecValTok{0}\NormalTok{)}

    \KeywordTok{def} \FunctionTok{doublePos2}\NormalTok{(ns: List[Int]): List[Int] =}
        \FunctionTok{map}\NormalTok{(}\FunctionTok{filter}\NormalTok{(ns)(x => }\DecValTok{0}\NormalTok{ < x))(y => }\DecValTok{2}\NormalTok{ * y)}
\end{Highlighting}
\end{Shaded}

Function \VERB|\NormalTok{doublePos2}| exhibits both the
\VERB|\NormalTok{filter}| and the \VERB|\NormalTok{map}| patterns of
computation.

The higher-order functions \VERB|\NormalTok{map}| and
\VERB|\NormalTok{filter}| allowed us to restate the definitions of
\VERB|\NormalTok{getEven}| and \VERB|\NormalTok{doublePos}| in a
succinct form.

We can implement \VERB|\NormalTok{filter}| in terms of
\VERB|\NormalTok{foldRight}| as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ filter1[A](ls: List[A])(p: A => Boolean): List[A] =}
        \FunctionTok{foldRight}\NormalTok{(ls, Nil:List[A])((x,xs) => }\KeywordTok{if}\NormalTok{ (}\FunctionTok{p}\NormalTok{(x)) }\FunctionTok{Cons}\NormalTok{(x,xs) }\KeywordTok{else}\NormalTok{ xs)}
\end{Highlighting}
\end{Shaded}

Above, the folding function

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    (x,xs) => }\KeywordTok{if}\NormalTok{ (}\FunctionTok{p}\NormalTok{(x)) }\FunctionTok{Cons}\NormalTok{(x,xs) }\KeywordTok{else}\NormalTok{ xs}
\end{Highlighting}
\end{Shaded}

applies the filter predicate \VERB|\NormalTok{p}| to the next element of
the list (moving right to left). If the predicate evaluates to true, the
folding function attaches that element on the front of the processed
tail; otherwise, it omits the element from the result.

\hypertarget{flat-map}{%
\subsubsection{Flat Map}\label{flat-map}}

The higher-order function \VERB|\NormalTok{map}| applies its function
argument \VERB|\NormalTok{f}| to every element of a list and returns the
list of results. If the function argument \VERB|\NormalTok{f}| returns a
list, then the result is a list of lists. Often we wish to flatten this
into a single list, that is, apply a function like
\VERB|\NormalTok{concat}| defined in a previous section.

This computation is sufficiently common that we give it the name
\VERB|\NormalTok{flatMap}|. We can define it in terms of
\VERB|\NormalTok{map}| and \VERB|\NormalTok{concat}| as

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ flatMap[A,B](ls: List[A])(f: A => List[B]): List[B] =}
        \FunctionTok{concat}\NormalTok{(}\FunctionTok{map}\NormalTok{(ls)(f))}
\end{Highlighting}
\end{Shaded}

or by combining \VERB|\NormalTok{map}| and \VERB|\NormalTok{concat}|
into one \VERB|\NormalTok{foldRight}| as:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ flatMap1[A,B](ls: List[A])(f: A => List[B]): List[B] =}
        \FunctionTok{foldRight}\NormalTok{(ls, Nil: List[B])(}
\NormalTok{            (x: A, ys: List[B]) => }\FunctionTok{append}\NormalTok{(}\FunctionTok{f}\NormalTok{(x),ys))}
\end{Highlighting}
\end{Shaded}

Above, the function argument to \VERB|\NormalTok{foldRight}| applies the
\VERB|\NormalTok{flatMap}| function argument \VERB|\NormalTok{f}| to
each element of the list argument and then appends the resulting list in
front of the result from processing the elements to the right.

We can also define \VERB|\NormalTok{filter}| in terms of
\VERB|\NormalTok{flatMap}| as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ filter2[A](ls: List[A])(p: A => Boolean): List[A] =}
        \FunctionTok{flatMap}\NormalTok{(ls)(x => }\KeywordTok{if}\NormalTok{ (}\FunctionTok{p}\NormalTok{(x)) List(x) }\KeywordTok{else}\NormalTok{ Nil)}
\end{Highlighting}
\end{Shaded}

The function argument to \VERB|\NormalTok{flatMap}| generates a
one-element list if the filter predicate \VERB|\NormalTok{p}| is true
and an empty list if it is false.

\hypertarget{classic-algorithms-on-lists}{%
\subsection{Classic algorithms on
lists}\label{classic-algorithms-on-lists}}

\hypertarget{insertion-sort-and-bounded-generics}{%
\subsubsection{Insertion sort and bounded
generics}\label{insertion-sort-and-bounded-generics}}

Consider a function to sort the elements of a list into ascending order.
A simple algorithm to do this is \emph{insertion sort}. To sort a
non-empty list with head \VERB|\NormalTok{x}| and tail
\VERB|\NormalTok{xs}|, sort the tail \VERB|\NormalTok{xs}| and insert
the element \VERB|\NormalTok{x}| at the right position in the result. To
sort an empty list, just return it.

If we restrict the function to integer lists, we get the following Scala
functions:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{isort}\NormalTok{(ls: List[Int]): List[Int] = ls }\KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case}\NormalTok{ Nil        => Nil}
        \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(x,xs) => }\FunctionTok{insert}\NormalTok{(x,}\FunctionTok{isort}\NormalTok{(xs))}
\NormalTok{    \}}

    \KeywordTok{def} \FunctionTok{insert}\NormalTok{(x: Int, xs: List[Int]): List[Int] = xs }\KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case}\NormalTok{ Nil        => List(x)}
        \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(y,ys) =>}
            \KeywordTok{if}\NormalTok{ (x <= y)}
                \FunctionTok{Cons}\NormalTok{(x,xs)}
            \KeywordTok{else}
                \FunctionTok{Cons}\NormalTok{(y,}\FunctionTok{insert}\NormalTok{(x,ys))}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

Insertion sort has a (worst and average case) time complexity of
O(\(n^{2}\)) where \(n\) is the length of the input list. (Function
\VERB|\NormalTok{isort}| requires \(n\) consecutive recursive calls;
each call uses function \VERB|\NormalTok{insert}| which itself requires
on the order of \(n\) recursive calls.)

Now suppose we want to generalize the sorting function and make it
polymorphic. We cannot just add a type parameter \VERB|\NormalTok{A}|
and substitute it for \VERB|\NormalTok{Int}| everywhere. Although all
Scala data types support equality and inequality comparison, not all
types can be compared on a \emph{total ordering} (\VERB|\NormalTok{<}|,
\VERB|\NormalTok{<=}|, \VERB|\NormalTok{>}|, and \VERB|\NormalTok{>=}|
as well).

Fortunately, the Scala library provides a trait
\VERB|\NormalTok{Ordered}|. Any class that provides the other
comparisons can extend this trait; the standard types in the library do
so. This trait adds the comparison operators as methods so that they can
be called in infix form.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{trait}\NormalTok{ Ordered[A] \{}
        \KeywordTok{def} \FunctionTok{compare}\NormalTok{(that: A): Int}
        \KeywordTok{def}\NormalTok{ < (that: A): Boolean = (}\KeywordTok{this}\NormalTok{ compare that) <  }\DecValTok{0}
        \KeywordTok{def}\NormalTok{ > (that: A): Boolean = (}\KeywordTok{this}\NormalTok{ compare that) >  }\DecValTok{0}
        \KeywordTok{def}\NormalTok{ <=(that: A): Boolean = (}\KeywordTok{this}\NormalTok{ compare that) <= }\DecValTok{0}
        \KeywordTok{def}\NormalTok{ >=(that: A): Boolean = (}\KeywordTok{this}\NormalTok{ compare that) >= }\DecValTok{0}
        \KeywordTok{def} \FunctionTok{compareTo}\NormalTok{(that: a) = }\FunctionTok{compare}\NormalTok{(that)}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

We thus need to restrict the polymorphism on \VERB|\NormalTok{A}| to be
a subtype of \VERB|\NormalTok{Ordered[A]}| by putting an \emph{upper
bound} on the type as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ isort[A <: Ordered[A]](ls: List[A]): List[A]}
\end{Highlighting}
\end{Shaded}

Note: In addition to upper bounds, we can use a \emph{lower bound}. A
constraint \VERB|\NormalTok{A :> T}| requires type \VERB|\NormalTok{A}|
to be a supertype of type \VERB|\NormalTok{T}|. We can also specify both
an upper and a lower bound on a type such as
\VERB|\NormalTok{T1 <: A <: T2}|,

By using the upper bound constraint, we can sort data from any type that
extends \VERB|\NormalTok{Ordered}|. However, the primitive types
inherited from Java do not extend \VERB|\NormalTok{Ordered}|.

Fortunately, the Scala library defines implicit conversions between the
Java primitive types and Scala's enriched wrapper types. (This is the
``type class'' mechanism we discussed earlier.) We can use a weaker
\emph{view bound} constraint, denoted by \VERB|\NormalTok{<%}| instead
of \VERB|\NormalTok{<:}|. This \VERB|\NormalTok{A}| to be any type that
is a subtype of or convertible to \VERB|\NormalTok{Ordered[A]}|.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ isort1[A <% Ordered[A]](ls: List[A]): List[A] = }
\NormalTok{        ls }\KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case}\NormalTok{ Nil        => Nil}
            \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(x,xs) => }\FunctionTok{insert1}\NormalTok{(x,}\FunctionTok{isort1}\NormalTok{(xs))}
\NormalTok{        \}}

    \KeywordTok{def}\NormalTok{ insert1[A <% Ordered[A]](x: A, xs: List[A]): List[A] =}
\NormalTok{        xs }\KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case}\NormalTok{ Nil        => List(x)}
            \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(y,ys) =>}
                \KeywordTok{if}\NormalTok{ (x <= y)}
                    \FunctionTok{Cons}\NormalTok{(x,xs)}
                \KeywordTok{else}
                    \FunctionTok{Cons}\NormalTok{(y,}\FunctionTok{insert1}\NormalTok{(x,ys))}
\NormalTok{        \}}
\end{Highlighting}
\end{Shaded}

We could define \VERB|\NormalTok{insert}| inside
\VERB|\NormalTok{isort}| and avoid the separate type parameterization.
But \VERB|\NormalTok{insert}| is separately useful, so it is reasonable
to leave it external.

An alternative to use of the bound would be to pass in the needed
comparison predicate, as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ isort2[A](ls: List[A])(leq: (A,A) => Boolean): List[A] =}
\NormalTok{        ls }\KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case}\NormalTok{ Nil        => Nil}
            \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(x,xs) => }\FunctionTok{insert2}\NormalTok{(x,}\FunctionTok{isort2}\NormalTok{(xs)(leq))(leq)}
\NormalTok{        \}}

    \KeywordTok{def}\NormalTok{ insert2[A](x:A, xs:List[A])(leq:(A,A)=>Boolean):List[A] =}
\NormalTok{        xs }\KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case}\NormalTok{ Nil        => List(x)}
            \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(y,ys) =>}
                \KeywordTok{if}\NormalTok{ (}\FunctionTok{leq}\NormalTok{(x,y))}
                    \FunctionTok{Cons}\NormalTok{(x,xs)}
                \KeywordTok{else}
                    \FunctionTok{Cons}\NormalTok{(y,}\FunctionTok{insert2}\NormalTok{(x,ys)(leq))}
\NormalTok{        \}}
\end{Highlighting}
\end{Shaded}

Above we expressed both functions in curried form. By putting the
comparison function last, we enabled the compiler to infer the argument
types for the function.

If we placed the function in the first argument group, the user of the
function would have to supply the types. However, putting the comparison
function first might allow a more useful partial application of the
\VERB|\NormalTok{isort}| to a comparison function.

\hypertarget{merge-sort}{%
\subsubsection{Merge sort}\label{merge-sort}}

The insertion sort given in the previous section has an average case
time complexity of O(\(n^{2}\)) where \(n\) is the length of the input
list.

We now consider a more efficient function to sort the elements of a
list: \emph{merge sort}. Merge sort works as follows:

\begin{itemize}
\item
  If the list has fewer than two elements, then it is already sorted.
\item
  If the list has two or more elements, then we split it into two
  sublists, each with about half the elements, and sort each
  recursively.
\item
  We merge the two ascending sublists into an ascending list.
\end{itemize}

For a general implementation, we specify the type of list elements and
the function to be used for the comparison of elements, giving the
following implementation:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ msort[A](less: (A, A) => Boolean)(ls: List[A]): List [A] =}
\NormalTok{    \{}
        \KeywordTok{def} \FunctionTok{merge}\NormalTok{(as: List[A], bs: List[A]): List[A] = }
\NormalTok{            (as,bs) }\KeywordTok{match}\NormalTok{ \{}
                \KeywordTok{case}\NormalTok{ (Nil,_)                 => bs}
                \KeywordTok{case}\NormalTok{ (_,Nil)                 => as}
                \KeywordTok{case}\NormalTok{ (}\FunctionTok{Cons}\NormalTok{(x,xs),}\FunctionTok{Cons}\NormalTok{(y,ys)) =>}
                    \KeywordTok{if}\NormalTok{ (}\FunctionTok{less}\NormalTok{(x,y))}
                        \FunctionTok{Cons}\NormalTok{(x,}\FunctionTok{merge}\NormalTok{(xs,bs))}
                    \KeywordTok{else}
                        \FunctionTok{Cons}\NormalTok{(y,}\FunctionTok{merge}\NormalTok{(as,ys))}
\NormalTok{        \}}

        \KeywordTok{val}\NormalTok{ n = }\FunctionTok{length}\NormalTok{(ls)/}\DecValTok{2}
        \KeywordTok{if}\NormalTok{ (n == }\DecValTok{0}\NormalTok{)}
\NormalTok{            ls}
        \KeywordTok{else}
            \FunctionTok{merge}\NormalTok{(}\FunctionTok{msort}\NormalTok{(less)(}\FunctionTok{take}\NormalTok{(ls,n)),}
                  \FunctionTok{msort}\NormalTok{(less)(}\FunctionTok{drop}\NormalTok{(ls,n)))}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

The \VERB|\NormalTok{merge}| forms a tuple of the two lists and does
pattern matching against that tuple. This allowed the pattern match to
be expressed more symmetrically.

The above function uses a function we have not yet defined.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ take[A](ls: List[A], n: Int): List[A]}
\end{Highlighting}
\end{Shaded}

returns the first \VERB|\NormalTok{n}| elements of the list; it is the
dual of \VERB|\NormalTok{drop}|.

By nesting the definition of \VERB|\NormalTok{merge}|, we enabled it to
directly access the the parameters of \VERB|\NormalTok{msort}|. In
particular, we did not need to pass the comparison function to
\VERB|\NormalTok{merge}|.

The average case time complexity of \VERB|\NormalTok{msort}| is
O(\(n\; \log(n)\)), where \(n\) is the length of the input list.

\begin{itemize}
\item
  Each call level requires splitting of the list in half and merging of
  the two sorted lists. This takes time proportional to the length of
  the list argument.
\item
  Each call of \VERB|\NormalTok{msort}| for lists longer than one
  results in two recursive calls of \VERB|\NormalTok{msort}|.
\item
  But each successive call of \VERB|\NormalTok{msort}| halves the number
  of elements in its input, so there are O(\(\log(n)\)) recursive calls.
\end{itemize}

So the total cost is O(\(n\; \log(n)\)). The cost is independent of
distribution of elements in the original list.

We can apply \VERB|\NormalTok{msort}| as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \FunctionTok{msort}\NormalTok{((x: Int, y: Int) => x < y)(List(}\DecValTok{5}\NormalTok{, }\DecValTok{7}\NormalTok{, }\DecValTok{1}\NormalTok{, }\DecValTok{3}\NormalTok{))}
\end{Highlighting}
\end{Shaded}

We defined \VERB|\NormalTok{msort}| in curried form with the comparison
function first (unlike what we did with \VERB|\NormalTok{isort1}|). This
enables us to conveniently specialize \VERB|\NormalTok{msort}| with a
specific comparison function. For example,

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{val}\NormalTok{ intSort     = }\FunctionTok{msort}\NormalTok{((x: Int, y: Int) => x < y) _}
    \KeywordTok{val}\NormalTok{ descendSort = }\FunctionTok{msort}\NormalTok{((x: Int, y: Int) => x > y) _}
\end{Highlighting}
\end{Shaded}

However, we do have to give explicit type annotations for the parameters
of the comparison function.

\hypertarget{lists-in-the-scala-standard-library}{%
\subsection{Lists in the Scala standard
library}\label{lists-in-the-scala-standard-library}}

In this discussion (and in Chapter 3 of \emph{Functional Programming in
Scala} {[}Chuisano 2015{]}), we developed several functions for a simple
\VERB|\NormalTok{List}| module. Our module is related to the builtin
Scala \VERB|\NormalTok{List}| module (from
\VERB|\NormalTok{scala.}\FunctionTok{collection}\NormalTok{.}\FunctionTok{immutable}|),
but it differs in several ways.

Our \VERB|\NormalTok{List}| module is standalone module; the Scala
\VERB|\NormalTok{List}| inherits from an abstract class with several
traits mixed in. These classes and traits structure the interfaces
shared among several data structures in the Scala library. Many of the
functions work for different data structures. For example, in Scala
release 2.12.8 \VERB|\NormalTok{List}| is defined as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{sealed} \KeywordTok{abstract} \KeywordTok{class}\NormalTok{ List[+A] }\KeywordTok{extends}\NormalTok{ AbstractSeq[A]}
        \KeywordTok{with}\NormalTok{ LinearSeq[A]}
        \KeywordTok{with}\NormalTok{ Product}
        \KeywordTok{with}\NormalTok{ GenericTraversableTemplate[A, List]}
        \KeywordTok{with}\NormalTok{ LinearSeqOptimized[A, List[A]]}
        \KeywordTok{with}\NormalTok{ scala.}\FunctionTok{Serializable} 
\end{Highlighting}
\end{Shaded}

Our \VERB|\NormalTok{List}| module consists of functions in which all
arguments must be given explicitly; the Scala \VERB|\NormalTok{List}|
consists of methods on the \VERB|\NormalTok{List}| class. Scala enables
methods with one implicit argument (i.e.~\texttt{this}) and one explicit
argument to be called as infix operators with different associativities.
It allows symbols such as \VERB|\NormalTok{<}| to be used for method
names.

Scala's approach to functional programming uses \emph{method chaining}
in its object system to support composition of pure functions. Each
method returns an immutable object that becomes the receiver of the
subsequent method call in the same statement.

Extensive use of method chaining in an object-oriented program with
mutable objects---sometimes called a \emph{train wreck}---can make
programs difficult to understand. However, disciplined use of method
chaining helps make the functional and object-oriented aspects of Scala
work together. (In different ways, method chaining is also useful in
development of fluent library interfaces for domain-specific languages.)

Our \VERB|\FunctionTok{Cons}\NormalTok{(x,xs)}| is written as
\VERB|\NormalTok{x :: xs}| using the standard Scala library. The
\VERB|\NormalTok{::}| is a method that has one implicit argument (the
tail list) and one explicit argument (the head element).

Any Scala method name that ends with a \VERB|\NormalTok{:}| is right
associative. Thus method \VERB|\NormalTok{x :: xs}| represents the
method call \VERB|\NormalTok{xs.::(x)}|, which in turn calls the data
constructor. We can write \VERB|\NormalTok{x :: y :: z :: zs}| without
parentheses to mean \VERB|\NormalTok{x :: (y :: (z :: zs))}|.

We can also use multiple \VERB|\NormalTok{::}| constructors in cases for
pattern matching. For example, where we wrote the pattern

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(x, }\FunctionTok{Cons}\NormalTok{(y,ys))}
\end{Highlighting}
\end{Shaded}

in the \VERB|\NormalTok{remdups}| function, we can write the pattern:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{case}\NormalTok{ x :: y :: ys}
\end{Highlighting}
\end{Shaded}

Our \VERB|\NormalTok{append}| function is normally written with the
infix operator \VERB|\NormalTok{++}| in the Scala library. (But there
are several variations for special circumstances.)

Several of our functions with a single list parameter may appear as
parameterless methods with the same name in the Scala library. These
include \VERB|\NormalTok{sum}|, \VERB|\NormalTok{product}|,
\VERB|\NormalTok{reverse}|, and \VERB|\NormalTok{length}|. There is also
a \VERB|\NormalTok{head}| function to retrieve the head element of a
nonempty list.

Our \VERB|\NormalTok{concat}| function is parameterless method
\VERB|\NormalTok{flatten}| in the Scala library.

Our functions with two parameters, a list and a modifier, are
one-parameter methods with the same name in the Scala library, and,
hence, usable as infix operators. These include \VERB|\NormalTok{drop}|,
\VERB|\NormalTok{dropWhile}|, \VERB|\NormalTok{map}|,
\VERB|\NormalTok{filter}|, and \VERB|\NormalTok{flatMap}|. There are
also analogous functions \VERB|\NormalTok{take}| and
\VERB|\NormalTok{takeWhile}|.

Our functions \VERB|\NormalTok{foldRight}| and
\VERB|\NormalTok{foldLeft}|, which have three parameters, are methods in
the Scala library with two curried parameters. The list argument becomes
implicit; the other arguments are in the same order. The Scala library
contains several folding and reducing functions with related
functionality.

Other than \VERB|\NormalTok{head}|, \VERB|\NormalTok{take}|,
\VERB|\NormalTok{takeWhile}|, and the appending and folding methods
mentioned above, the Scala List library has other useful methods such as
\VERB|\NormalTok{forall}|, \VERB|\NormalTok{exists}|,
\VERB|\NormalTok{scanLeft}|, \VERB|\NormalTok{scanRight}|,
\VERB|\NormalTok{zip}|, and \VERB|\NormalTok{zipWith}|.

Check out the Scala API documentation on the Scala website.

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

\begin{itemize}
\item
  Chapter 3 source: \href{List2.scala}{\texttt{List2.scala}}
\item
  Chapter 3 tests: \href{TestList2.scala}{\texttt{TestList2.scala}}
\end{itemize}

\hypertarget{exercise-set-a}{%
\subsection{Exercise Set A}\label{exercise-set-a}}

TODO: Edit and reorder these exercises. This order corresponds to
Assignment \#2 in Spring 2019.

In the following exercises, extend the
\href{List2.scala}{\texttt{List2.scala}} algebraic data type
implementation developed in these notes to add the following functions.
In the descriptions below, type \VERB|\NormalTok{List}| refers to the
trait defined in that package, not the standard Scala list.

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Write a Scala function \VERB|\NormalTok{orList}| that takes a
  \VERB|\NormalTok{List}| of \VERB|\NormalTok{Boolean}| values and
  returns the logical \texttt{or} of the values (i.e.~true if any are
  true, otherwise false).
\item
  Write a Scala function \VERB|\NormalTok{andList}| that takes a
  \VERB|\NormalTok{List}| of \VERB|\NormalTok{Boolean}| values and
  returns the logical \texttt{and} of the values (i.e.~true if all are
  true, otherwise false).
\item
  Write a Scala function \VERB|\NormalTok{maxList}| that takes a
  nonempty \VERB|\NormalTok{List}| of values and returns its maximum
  value.

  Hint: First solve this with \VERB|\NormalTok{Int}|, then generalize to
  a generic type. Study the subsection on insertion sort in this set of
  notes.
\item
  Write a Scala \VERB|\NormalTok{remdups1}| that is like
  \VERB|\NormalTok{remdups}| except that it is implemented using either
  \VERB|\NormalTok{foldRight}| or \VERB|\NormalTok{foldLeft}|.
\item
  Write a Scala function \VERB|\NormalTok{total}| that takes a
  nonnegative integer \VERB|\NormalTok{n}| and a function
  \VERB|\NormalTok{f}| of an appropriate type and returns
  \VERB|\FunctionTok{f}\NormalTok{(}\DecValTok{0}\NormalTok{) + }\FunctionTok{f}\NormalTok{(}\DecValTok{1}\NormalTok{) + ... }\FunctionTok{f}\NormalTok{(n)}|.
\item
  Write a Scala function \VERB|\NormalTok{flip}| that takes a function
  of polymorphic type \VERB|\NormalTok{(A,B) => C}| and returns a
  function of type \VERB|\NormalTok{(B,A) => C}| such that, for all
  \VERB|\NormalTok{x}| and \VERB|\NormalTok{y}|:

\begin{Shaded}
\begin{Highlighting}[]
    \FunctionTok{f}\NormalTok{(x,y) == }\FunctionTok{flip}\NormalTok{(f)(y,x)}
\end{Highlighting}
\end{Shaded}
\item
  Write the following Scala functions using tail recursive definitions:

  \begin{enumerate}
  \def\labelenumii{\alph{enumii}.}
  \tightlist
  \item
    \VERB|\NormalTok{sumT}| with same functionality as
    \VERB|\NormalTok{sum}|
  \item
    \VERB|\NormalTok{productT}| with the same functionality as
    \VERB|\NormalTok{product}|
  \end{enumerate}
\item
  Write a Scala function \VERB|\NormalTok{mean}| that takes a nonempty
  \VERB|\NormalTok{List}| of \VERB|\NormalTok{Double}| values and
  returns its mean (i.e.~average) value.
\item
  Write a Scala function \VERB|\NormalTok{adjPairs}| that takes a
  \VERB|\NormalTok{List}| of pairs (i.e.~two-tuples) and returns the
  list of all pairs of adjacent elements. For example,
  \VERB|\FunctionTok{adjPairs}\NormalTok{(List(}\DecValTok{2}\NormalTok{,}\DecValTok{1}\NormalTok{,}\DecValTok{11}\NormalTok{,}\DecValTok{4}\NormalTok{))}|
  returns
  \VERB|\NormalTok{List((}\DecValTok{2}\NormalTok{,}\DecValTok{1}\NormalTok{),(}\DecValTok{1}\NormalTok{,}\DecValTok{11}\NormalTok{),(}\DecValTok{11}\NormalTok{,}\DecValTok{4}\NormalTok{))}|.
\item
  Write a Scala function \VERB|\NormalTok{splitAt}| that takes a
  \VERB|\NormalTok{List}| of values and an integer \VERB|\NormalTok{n}|
  and returns a pair (i.e.~two tuple) of \VERB|\NormalTok{List}|s, where
  the first component consists of the first \VERB|\NormalTok{n}|
  elements of the input list (in order) and the second component
  consists of the remaining elements (in order).
\item
  Number base conversion.

  \begin{enumerate}
  \def\labelenumii{\alph{enumii}.}
  \item
    Write a Scala function \VERB|\NormalTok{natToBin}| that takes a
    natural number and returns its binary representation as a
    \VERB|\NormalTok{List}| of \VERB|\DecValTok{0}|'s and
    \VERB|\DecValTok{1}|'s with the most significant digit at the head.
    For example,
    \VERB|\FunctionTok{natToBin}\NormalTok{(}\DecValTok{23}\NormalTok{)}|
    returns
    \VERB|\NormalTok{List(}\DecValTok{1}\NormalTok{,}\DecValTok{0}\NormalTok{,}\DecValTok{1}\NormalTok{,}\DecValTok{1}\NormalTok{,}\DecValTok{1}\NormalTok{)}|.

    In computer science, we usually consider 0 as natural number along
    with the positive integers.
  \item
    Generalize \VERB|\NormalTok{natToBin}| to Scala function
    \VERB|\NormalTok{natToBase}| that takes base \VERB|\NormalTok{b}|
    (\VERB|\NormalTok{b >= }\DecValTok{2}|) as its first paramenter and
    the natural number as its second. The function should return the
    base \VERB|\NormalTok{b}| representation of the natural number as a
    list of integer digits with the most significant digit at the head.
    For example,
    \VERB|\FunctionTok{natToBase}\NormalTok{(}\DecValTok{5}\NormalTok{,}\DecValTok{42}\NormalTok{)}|
    returns
    \VERB|\NormalTok{List(}\DecValTok{1}\NormalTok{,}\DecValTok{3}\NormalTok{,}\DecValTok{2}\NormalTok{)}|.
  \item
    Write Scala function \VERB|\NormalTok{baseToNat}| that is the
    inverse of the \VERB|\NormalTok{natToBase}| function. For any base
    \VERB|\NormalTok{b}| (\VERB|\NormalTok{b >= }\DecValTok{2}|) and
    natural number \VERB|\NormalTok{n}|:

\begin{Shaded}
\begin{Highlighting}[]
    \FunctionTok{baseToNat}\NormalTok{(b,}\FunctionTok{natToBase}\NormalTok{(b,n)) == n}
\end{Highlighting}
\end{Shaded}
  \end{enumerate}
\item
  For each of the following specifications, write a Scala function that
  has the given arguments and result. Use the higher functions from the
  \VERB|\NormalTok{List}| algebraic data type from these notes, such as
  \VERB|\NormalTok{map}|, \VERB|\NormalTok{filter}|,
  \VERB|\NormalTok{foldRight}|, and \VERB|\NormalTok{foldLeft}|, as
  appropriate.

  \begin{enumerate}
  \def\labelenumii{\alph{enumii}.}
  \item
    Function \VERB|\NormalTok{numof}| takes a value and a list and
    returns the number of occurrences of the value in the list.
  \item
    Function \VERB|\NormalTok{ellen}| takes a list of lists and returns
    a list of the lengths of the corresponding lists.
  \item
    Function \VERB|\NormalTok{ssp}| takes a list of integers and returns
    the sum of the squares of the positive elements of the list.
  \end{enumerate}
\item
  Write a Scala function \VERB|\NormalTok{scalarProd}| with type

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    (List[Int],List[Int]):: Int}
\end{Highlighting}
\end{Shaded}

  to compute the scalar product of two lists of integers
  (e.g.~representing vectors).

  The \emph{scalar product} is the sum of the products of the elements
  in corresponding positions in the lists. That is, the scalar product
  of two lists \VERB|\NormalTok{xs}| and \VERB|\NormalTok{ys}|, of
  length \texttt{n}, is:

  \begin{quote}
  \(\sum\limits_{i=0}^{i=n}xs_i * ys_{i}\)
  \end{quote}

  For example,
  \VERB|\FunctionTok{scalarprod}\NormalTok{(List(}\DecValTok{1}\NormalTok{,}\DecValTok{2}\NormalTok{,}\DecValTok{3}\NormalTok{),List(}\DecValTok{3}\NormalTok{,}\DecValTok{3}\NormalTok{,}\DecValTok{3}\NormalTok{))}|
  yields \VERB|\DecValTok{18}|.
\item
  Write a Scala function \VERB|\NormalTok{mapper}| that takes a list of
  functions and a list of values and returns the list of results of
  applying each function in the first list to the corresponding value in
  the second list.
\item
  Write a Scala function \VERB|\NormalTok{removeFirst}| that takes a
  predicate (i.e.~Boolean function) and a list of values and returns the
  list with the first element that satisfies the predicate removed.
\item
  Define a Scala function \VERB|\NormalTok{removeLast}| that takes a
  predicate (i.e.~Boolean function) and a list of values and returns the
  list with the last element that satisfies the predicate removed.

  How could you define it using \VERB|\NormalTok{removeFirst}|?
\end{enumerate}

\hypertarget{general-tree-algebraic-data-type}{%
\subsection{General Tree Algebraic Data
Type}\label{general-tree-algebraic-data-type}}

A \emph{general tree} is a hierarchical data structure in which each
node of the tree has zero or more subtrees. We can define this as a
Scala algebraic data type as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{sealed} \KeywordTok{trait}\NormalTok{ GTree[+A]}
    \KeywordTok{case} \KeywordTok{class}\NormalTok{ Leaf[+A](value: A) }\KeywordTok{extends}\NormalTok{ GTree[A]}
    \KeywordTok{case} \KeywordTok{class}\NormalTok{ Gnode[+A](gnode: List[GTree[A]]) }\KeywordTok{extends}\NormalTok{ GTree[A]}
\end{Highlighting}
\end{Shaded}

An object of class \VERB|\FunctionTok{Leaf}\NormalTok{(x)}| represents a
\emph{leaf} of the tree holding some value \VERB|\NormalTok{x}| of
generic type \VERB|\NormalTok{A}|. A leaf does not have any subtrees. It
has height 1.

An object of type \VERB|\NormalTok{Gnode}| represents an \emph{internal}
(i.e.~non-leaf) node of the tree. It consists of a nonempty list of
subtrees, ordered left-to-right. A \VERB|\NormalTok{Gnode}| has a height
that is one more than the maximum height of its subtrees.

\hypertarget{exercise-set-b}{%
\subsection{Exercise Set B}\label{exercise-set-b}}

In the following exercises, write the Scala functions to operate on the
\VERB|\NormalTok{GTree}|s. You may use functions from the extended
\VERB|\NormalTok{List}| module as needed.

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Write Scala function \VERB|\NormalTok{numLeavesGT}| that takes a
  \VERB|\NormalTok{GTree}| and returns the count of its leaves.
\item
  Write Scala function \VERB|\NormalTok{heightGT}| that takes a
  \VERB|\NormalTok{GTree}| and returns its height (i.e.~the number of
  levels).
\item
  Write Scala function \VERB|\NormalTok{sumGT}| that takes a
  \VERB|\NormalTok{GTree}| of integers and returns the sum of the
  values.
\item
  Write Scala function \VERB|\NormalTok{findGT}| that takes a
  \VERB|\NormalTok{GTree}| and a value and returns
  \VERB|\KeywordTok{true}| if and only if the element appears in some
  leaf in the tree.
\item
  Write Scala function \VERB|\NormalTok{mapGT}| that takes a
  \VERB|\NormalTok{GTree}| and a function and returns a
  \VERB|\NormalTok{GTree}| with the structure but with the function
  applied to all the values in the tree.
\item
  Write Scala function \VERB|\NormalTok{flattenGT}| that takes a
  \VERB|\NormalTok{GTree}| and returns a \VERB|\NormalTok{List}| with
  the values from the tree leaves ordered according to a left-to-right
  traversal of the tree.
\end{enumerate}

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

In Spring 2016, I wrote this set of notes to accompany my lectures on
Chapter 3 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 adapted some text and examples from my
\emph{Notes on Functional Programming with Haskell} {[}Cunningham
2014{]}.

I expanded the discussion of algebraic data types, polymorphism, and
variance. For this expansion, I examined other materials including the
Wikipedia articles on Algebraic Data Type, Abstract Data Type,
Polymorphism, Ad Hoc Polymorphism, Parametric Polymorphism, Subtyping,
Liskov Substitution Principle, Function Overloading, and Covariance and
Contravariance {[}Wikipedia 2019{]}. I also examined the discussion of
variance in the textbook \emph{Programming Scala} {[}Wampler 2014{]}. I
adapted the sorting algorithms from \emph{Scala by Example} {[}Odersky
2014{]}.

In 2018 and 2019, I updated the format to be more compatible with
evolving document structures.

In Spring 2019, I also moved the discussion of the kinds of polymorphism
to the new notes on \emph{Type System Concepts}, expanded the discussion
of Variance, and added two exercise sets. Several items from Exercise
Set A were adapted from the list processing chapters of ELIFP
{[}Cunningham 2018{]}.

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[{[}Brady 2017{]}:]
Edwin Bradley. \emph{Type-Driven Development with Idris}, Manning, 2017.
\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 2014{]}:]
H. Conrad Cunningham.
\href{https://john.cs.olemiss.edu/~hcc/csci450/notes/haskell_notes.pdf}{\emph{Notes
on Functional Programming with Haskell}}, 1993-2014.
\item[{[}Cunningham 2018{]}:]
H. Conrad Cunningham. \emph{Exploring Languages with Interpreters and
Functional Programming}, 2018. Available at
\url{https://john.cs.olemiss.edu/~hcc/csci450/ELIFP/ExploringLanguages.html}.
\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[{[}Odersky 2014{]}:]
Martin Odersky. \emph{Scala by Example}, EPFL, 2014.
\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[{[}Wampler 2014{]}:]
Dean Wampler and Alex Payne. \emph{Programming Scala}, Second Edition,
O'Reilly, 2014.
\item[{[}Liskov 1987{]}:]
Barbara Liskov. Keynote Address---Data Abstraction and Hierarchy, In the
Addendum to the \emph{Proceedings on Object-Oriented Programming
Systems, Languages, and Applications (OOPSLA '87)}, Leigh Power and Zvi
Weiss, Editors, ACM, 1987.
{[}\href{../../localcopy/Liskov_Data_Abstraction_and_Hierarchy_1987.pdf}{local}{]}
\item[{[}Petricek 2012{]}:]
Tomas Petricek. \emph{Why Type-first Development Matters}, blog entry,
August 2012, Accessed 4 March 2019 at
\url{http://tomasp.net/blog/type-first-development.aspx/}.
\item[{[}Wikipedia 2019{]}:]
\emph{Wikipedia}. Articles on Algebraic Data Type, Abstract Data Type,
Polymorphism (computer science), Ad Hoc Polymorphism, Parametric
Polymorphism, Subtyping, Liskov Substitution Principle, Function
Overloading, and Covariance and Contravariance (computer science); last
accessed 15 February 2019.
\end{description}

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

TODO: Update

Function, pure function, referential transparency, side effects,
mutable, immutable, list data type (head, tail, empty), algebraic data
type (composite, sum, product, enumerated), abstract data type, ADT,
syntax, semantics, \VERB|\KeywordTok{trait}|,
\VERB|\KeywordTok{sealed} \KeywordTok{trait}|,
\VERB|\KeywordTok{case} \KeywordTok{class}|,
\VERB|\KeywordTok{case} \KeywordTok{object}|, singleton object,
polymorphism, subtyping, parametric polymorphism, generics, overloading,
type classes, variance (covariant, contravariant, invariant/nonvariant),
following types to implementations (type-driven or type-first
development).

\end{document}
