\PassOptionsToPackage{unicode=true}{hyperref} % options for packages loaded elsewhere
\PassOptionsToPackage{hyphens}{url}
%
\documentclass[]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
  \usepackage{textcomp} % provides euro and other symbols
\else % if luatex or xelatex
  \usepackage{unicode-math}
  \defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{%
\usepackage[]{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
}
\usepackage{hyperref}
\hypersetup{
            pdftitle={CSci 555, Functional Programming, Spring 2016 Functional Programming in Scala Functional Data Structures},
            pdfauthor={H. Conrad Cunningham},
            pdfborder={0 0 0},
            breaklinks=true}
\urlstyle{same}  % don't use monospace font for urls
\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}{0}
% Redefines (sub)paragraphs to behave more like sections
\ifx\paragraph\undefined\else
\let\oldparagraph\paragraph
\renewcommand{\paragraph}[1]{\oldparagraph{#1}\mbox{}}
\fi
\ifx\subparagraph\undefined\else
\let\oldsubparagraph\subparagraph
\renewcommand{\subparagraph}[1]{\oldsubparagraph{#1}\mbox{}}
\fi

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

\usepackage{caption}
\DeclareCaptionLabelFormat{nolabel}{}
\captionsetup{labelformat=nolabel}

\title{CSci 555, Functional Programming, Spring 2016\\
Functional Programming in Scala\\
Functional Data Structures}
\author{\textbf{H. Conrad Cunningham}}
\date{\textbf{19 April 2016 (minor edit 4 February 2018}}

\begin{document}
\maketitle

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

\textbf{Acknowledgements}: This is a set of notes written to accompany
my lectures on Chapter 3 of the book \emph{Functional Programming in
Scala} by Paul Chiusano and Runar Bjarnason (Manning, 2015). 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}.

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,
Function Overloading, and Covariance and Contravariance. I also examined
the discussion of variance in the textbook \emph{Programming Scala},
Second Edition, by Dean Wampler and Alex Payne (O'Reilly, 2014). I
adapted the sorting algorithms from Martin Odersky's \emph{Scala by
Example}.

\textbf{Prerequisite}: This discussion assumes the reader is familiar
with the programming concepts and Scala features covered in my
\emph{Notes on Scala for Java Programmers} (adapted from a tutorial on
the Scala website) and \emph{Recursion Concepts and Terminology}.

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

\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
mutable data structures are used, no changes to the structures must be
detectable outside the function.)

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

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

Although sometimes the acronym ADT is used for both, an \emph{algebraic
data type} is a different concept from an \emph{abstract data type}. We
specify an algebraic data type with its \emph{syntax} (i.e.,
structure)--with rules on how to compose and decompose them. 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.

Perhaps to add to the confusion, in functional programming we sometimes
use an algebraic data type to help define an abstract data type. (See
the ``functional module style'' implementation of the Natural number
example, for instance.)

\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 \texttt{List} as an abstract type using a Scala
\texttt{trait}. (We could also use an \texttt{abstract\ class} instead
of a \texttt{trait}.) We define the \emph{constructors} for the
algebraic data type using the Scala \texttt{case\ class} and
\texttt{case\ object} features.

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

Thus \texttt{List} is a sum type with two alternatives:

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

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

The \texttt{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 \texttt{case\ class} and
\texttt{case\ object}, the Scala compiler generates:

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

In addition, the \texttt{case\ 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.

\texttt{List} is a polymorphic type. What does polymorphic mean?

\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 (and operator symbols) are associated
with implementations of the functions.

In general, two primary kinds of polymorphism exist in programming
languages:

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  \emph{Ad hoc polymorphism}, in which the same function name (or
  operator symbol) can denote different implementations depending upon
  how it is used in an expression. That is, the implementation invoked
  depends upon the types of function's arguments and return value.

  There are two subkinds of ad hoc polymorphism.

  \begin{enumerate}
  \def\labelenumii{\alph{enumii}.}
  \item
    \emph{Overloading} refers to ad hoc polymorphism in which the
    language's compiler or interpreter determines the appropriate
    implementation to invoke using information from the context. In
    statically typed languages, overloaded names and symbols can usually
    be bound to the intended implementation at compile time based on the
    declared types of the entities. They exhibit \emph{early binding}.

    Java overloads a few operator symbols, such as using the \texttt{+}
    symbol for both addition of numbers and concatenation of strings.
    Java also overloads calls of functions defined with the same name
    but different signatures (patterns of parameter types and return
    value). Java does not support user-defined operator overloading; C++
    does.
  \item
    \emph{Subtyping} (also known as \emph{subtype polymorphism} or
    \emph{inclusion polymorphism}) refers to ad hoc polymorphism in
    which the appropriate implementation is determined by searching a
    hierarchy of types. The function may be defined in a supertype and
    redefined (overridden) in subtypes. Beginning with the actual types
    of the data involved, the program searches up the type hierarchy to
    find the appropriate implementation to invoke. This usually occurs
    at runtime, so this exhibits \emph{late binding}.

    The object-oriented programming community often refers to
    inheritance-based subtype polymorphism as simply
    \emph{polymorphism}.
  \end{enumerate}
\item
  \emph{Parametric polymorphism}, in which the same implementation can
  be used for many different types. In most cases, the function (or
  class) implementation is stated in terms of one or more type
  parameters. In statically typed languages, this binding can usually be
  done at compile time (i.e., exhibiting early binding).

  The object oriented programming community often calls this type of
  polymorphism \emph{generics} or \emph{generic programming}. The
  functional programming community often calls this simply
  \emph{polymorphism}.
\end{enumerate}

Scala is a hybrid, object-functional language. Its type system supports
all three types of polymorphism: subtyping by extending classes and
traits, parametric polymorphism by using generic type parameters, and
overloading through both the Java-like mechanisms described above and
Haskell-like ``type classes''.

Scala's \emph{type class} pattern builds on the languages's
\texttt{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 \texttt{String} class (which is \texttt{final}
and thus cannot be subclassed) with new features from the
\texttt{RichString} wrapper class. The Scala \texttt{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 \texttt{List} data type defined above is polymorphic; it exhibits
both subtyping and parametric polymorphism. \texttt{Nil} and
\texttt{Cons} are subtypes of \texttt{List}. The generic type parameter
\texttt{A} denotes the type of the elements that occur in the list. For
example, \texttt{List{[}Double{]}} denotes a list of double-precision
floating point numbers.

What does the \texttt{+} annotation mean in the definition
\texttt{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}.

Suppose we have a supertype \texttt{Fish} with a subtype \texttt{Bass}.
For generic data type \texttt{List{[}A{]}} as defined above, consider
\texttt{List{[}Fish{]}} and \texttt{List{[}Bass{]}}.

If \texttt{List{[}Bass{]}} is a subtype of \texttt{List{[}Fish{]}},
preserving the subtyping order, then the relationship is
\emph{covariant}.

If \texttt{List{[}Fish{]}} is a subtype of \texttt{List{[}Bass{]}},
reversing the subtyping order, then the relationship is
\emph{contravariant}.

If there is no subtype relationship between \texttt{List{[}Fish{]}} and
\texttt{List{[}Bass{]}}, the the relationship is \emph{invariant}
(sometimes called \emph{nonvariant}).

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

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

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

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

\hypertarget{defining-functions-in-the-companion-object}{%
\subsubsection{Defining functions in the companion
object}\label{defining-functions-in-the-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
\texttt{List} trait is a convenient place to define functions for
manipulating the lists.

Because \texttt{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}.

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 \texttt{Nil}) and the nonempty list (represented by
\texttt{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 \texttt{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
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 \texttt{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
\texttt{sum} in Scala using pattern matching as follows:

\begin{verbatim}
    def sum(ints: List[Int]): Int = ints match {
      case Nil        => 0 
      case Cons(x,xs) => x + sum(xs)
    }
\end{verbatim}

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

For a list consisting of elements 2, 4, 6, and 8, that is,
\texttt{Cons(2,Cons(4,Cons(6,Cons(8,Nil))))}), function \texttt{sum}
computes:

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

Function \texttt{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 \texttt{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 \texttt{product} with two bases cases and one
recursive case, as follows:

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

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{verbatim}
    Cons(2.0,Cons(4.0,Cons(6.0,Cons(8.0,Nil))))
\end{verbatim}

function \texttt{product} computes:

\begin{verbatim}
    2.0 * (4.0 * (6.0 * (8.0 * 1.0))) 
\end{verbatim}

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

\begin{verbatim}
    2.0 * 0.0
\end{verbatim}

Like \texttt{sum}, function \texttt{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 \texttt{remdups} as follows:

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

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

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

Like the previous functions, \texttt{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{Variadic function apply}\label{variadic-function-apply}}

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

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

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

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

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

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

Suppose we have the declaration

\begin{verbatim}
    val xs = Cons(1,Cons(2,Cons(3,Nil)))
\end{verbatim}

or the more concise equivalent using the \texttt{apply} method:

\begin{verbatim}
    val xs = List(1,2,3)
\end{verbatim}

As we learned in the data structures course, we can implement this list
as a linked list \texttt{xs} with three cells with the values
\texttt{1}, \texttt{2}, and \texttt{3}, as shown in the figure below.

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

Consider the following declarations

\begin{verbatim}
    val ys = Cons(0,xs)
    val zs = xs.tail
\end{verbatim}

where

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

If the linked list \texttt{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 \texttt{0}, links it
  to the first cell in list \texttt{xs}, and initializes \texttt{ys}
  with a reference to the new cell.
\item
  The second just returns a reference to the second cell in list
  \texttt{xs} and initializes \texttt{zs} with this reference.
\item
  The original list \texttt{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 \texttt{List} and returns its tail
\texttt{List}. (This is different from the \texttt{tail} accessor method
on \texttt{Cons}.)

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

There are several possibilities:

\begin{itemize}
\tightlist
\item
  return \texttt{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 \texttt{tail} so that it explicitly throws an
exception. It can be defined in the companion object for \texttt{List}
as follows:

\begin{verbatim}
    def tail[A](ls: List[A]): List[A] = ls match {
      case Nil        => sys.error("tail of empty list")
      case Cons(_,xs) => xs
    }
\end{verbatim}

Above, the value of the \texttt{head} field of the \texttt{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 \texttt{\_} to indicate that the value is not needed.

Function \texttt{tail} 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 \texttt{tail} to a function \texttt{drop} that removes
the first \texttt{n} elements of a list, as follows:

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

The \texttt{drop} function terminates when either the list argument is
\texttt{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
\texttt{tail} does. Although it seems illogical to take the
\texttt{tail} of an empty list, dropping the first element from an empty
list seems subtly different. Given that we often use \texttt{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 \texttt{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 \texttt{append} function in terms of the
constructors \texttt{Nil} and \texttt{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 \texttt{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 \texttt{Cons}, it seems reasonable that an
algorithm for \texttt{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 \texttt{Nil}, then the function can just return
  the right operand.
\item
  If the left operand is a \texttt{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 \texttt{append} as follows:

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

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

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

Moreover, \texttt{append(as,bs)} only needs to copy the list
\texttt{as}. The list \texttt{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.

\begin{quote}
Associativity: For any finite lists \texttt{xs}, \texttt{ys}, and
\texttt{zs},
\texttt{append(xs,append(ys,zs))\ =\ append(append(xs,ys),zs)}.
\end{quote}

\begin{quote}
Identity: For any finite list \texttt{xs},
\texttt{append(Nil,xs)\ =\ append(xs,Nil)\ =\ xs}.
\end{quote}

Scala's builtin \texttt{List} type uses the infix operator \texttt{++}
for the ``append'' operation. For this operator, associativity can be
stated conveniently with the equation:
\texttt{xs\ ++\ (ys\ ++\ zs)\ =\ (xs\ ++\ ys)\ ++\ zs}

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

\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{verbatim}
    def rev[A](ls: List[A]): List[A] = ls match {
      case Nil        => Nil
      case Cons(x,xs) => append(rev(xs),List(x))
    }
\end{verbatim}

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

How efficient is this function?

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

The initial list and its reverse do not share data.

Function \texttt{rev} has a number of useful properties, for example the
following:

\begin{quote}
Distribution: For any finite lists \texttt{xs} and \texttt{ys},
\texttt{rev(append(xs,ys))\ =\ append(rev(ys),\ rev(xs))}.
\end{quote}

\begin{quote}
Inverse: For any finite list \texttt{xs}, \texttt{rev(rev(xs))\ =\ xs}.
\end{quote}

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 \texttt{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{verbatim}
    def revAux[A](ls: List[A], as: List[A]): List[A] = ls match {
      case Nil        => as
      case Cons(x,xs) => revAux(xs,Cons(x,as))
    }
\end{verbatim}

In this definition parameter \texttt{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 \texttt{revAux} terminates because, for each recursive
application, the length of the first argument decreases toward the base
case of \texttt{Nil}.

We note that \texttt{rev(xs)} is equivalent to \texttt{revAux(xs,Nil)}.

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

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

Function \texttt{reverse(xs)} returns the value from
\texttt{revAux(xs,Nil)}.

How efficient is this function?

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

Where did the increase in efficiency come from?

Each application of \texttt{rev} applies \texttt{append}, a linear time
(i.e., O(\(n\))) function. In \texttt{revAux}, we replaced the
applications of \texttt{append} by applications of \texttt{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 \texttt{dropWhile} that removes elements from the
front of a \texttt{List} while its predicate argument (a Boolean
function) holds.

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

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 \texttt{p} is O(1), then function
\texttt{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 \texttt{dropwhile}, which has the signature:

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

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

\begin{verbatim}
    val xs: List[Int] = List(1,2,3,4,5)
    val ex1 = dropWhile(xs, (x: Int) => x < 4)
\end{verbatim}

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

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

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

Function \texttt{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 \texttt{dropWhile2} to just the first argument, we get a
function. We call this a \emph{partial application} of
\texttt{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
\texttt{dropWhile2}, the first argument group binds type variable
\texttt{A} to \texttt{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 \texttt{sum} and \texttt{product} functions we defined
above, ignoring the short-cut handling of the zero element in
\texttt{product}.

\begin{verbatim}
    def sum(ints: List[Int]): Int = ints match {
      case Nil        => 0 
      case Cons(x,xs) => x + sum(xs)
    }

    def product(ds: List[Double]): Double = ds match {
      case Nil          => 1.0
      case Cons(x,xs)   => x * product(xs)
    }
\end{verbatim}

What do \texttt{sum} and \texttt{product} have in common?

Both functions exhibit the same \emph{pattern of computation}. They both
take a list of elements and insert a binary operator between all the
consecutive elements of the list in order to reduce the list to a single
value. The operations are grouped from the right to the left. Function
\texttt{sum} takes a list of integers and applies addition;
\texttt{product} takes a list of double-precision floating point numbers
and applies multiplication.

In addition, \texttt{sum} returns integer 0 when its argument is nil; if
this is a recursive call, the return value is added to the right of the
previous results. Similarly, \texttt{product} returns 1.0 when its
argument is nil. The values 0 and 1.0 are the identity elements for
addition and multiplication, respectively. Function \texttt{sum}
processes a list of integers and returns an integer; \texttt{product}
processes a list of double-precision floating point numbers and returns
a double-precision floating point number.

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

\begin{itemize}
\item
  Pull the parts that differ into the generalized function's parameter
  list.
\item
  Leave the parts that are the same in the generalized function's body.
\item
  If a part moved to the generalized function's parameter list accesses
  local variables, then make that part a function with a parameter for
  each local variable accessed.
\item
  If data types differ at some points, then add type parameters to the
  generalized function.
\item
  If the same data type appears in multiple roles, then consider adding
  a distinct type parameter for each.
\end{itemize}

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

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

This function:

\begin{itemize}
\item
  passes in the binary operation \texttt{f} that combines the list
  elements
\item
  passes in the element \texttt{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 \texttt{A} and \texttt{B}--one for the type
  of elements in the list and one for the type of the result
\end{itemize}

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

Function \texttt{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 \texttt{foldRight} to have the same functionality as
\texttt{sum} and \texttt{product}.

\begin{verbatim}
    def sum2(ns: List[Int]) =
      foldRight(ns, 0)((x,y) => x + y)

    def product2(ns: List[Double]) =
      foldRight(ns, 1.0)(_ * _)
\end{verbatim}

The expression \texttt{(\_\ *\ \_)} in \texttt{product2} is a concise
notation for the anonymous function
\texttt{(x,y)\ =\textgreater{}\ 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.

We can construct a recursive function to compute the length of a
polymorphic list. However, we can also express this computation using
\texttt{foldRight}, as follows:

\begin{verbatim}
    def length[A](ls: List[A]): Int =
      foldRight(ls, 0)((_,acc) => acc + 1)
\end{verbatim}

We use the \texttt{z} parameter to accumulate the count, starting it at
0. Higher order argument \texttt{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,
\texttt{z} is not the identity element for \texttt{f} by a convenient
beginning value for the counter.

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

\begin{verbatim}
    def append2[A](ls: List[A], rs: List[A]): List[A] =
      foldRight(ls, rs)(Cons(_,_))
\end{verbatim}

Here the the list that \texttt{foldRight} operates on the first argument
of the append. The \texttt{z} parameter is the entire second argument
and the combining function is just \texttt{Cons}. So the effect is to
replace the \texttt{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 \texttt{concat} function in terms of
\texttt{foldRight}, as follows:

\begin{verbatim}
    def concat[A](ls: List[List[A]]): List[A] =
      foldRight(ls, Nil: List[A])(append) 
\end{verbatim}

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

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

In \texttt{concat}, for which Scala can infer the types of
\texttt{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{verbatim}
    append _
\end{verbatim}

or an explicit function literal such as

\begin{verbatim}
    (xs: List[A], ys: List[A]) => append(xs,ys)
\end{verbatim}

to enable the compiler to infer the types.

Above we defined function \texttt{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 \texttt{foldRight} as
a powerful list operator that reduces the element of the list into a
single value. We can combine \texttt{foldRight} with other operators to
conveniently construct list processing programs.

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

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

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

As noted:

\begin{verbatim}
    foldRight(List(1,2,3),z)(f) == f(1,f(2,f(3,z)))
\end{verbatim}

Consider a function \texttt{foldLeft} such that:

\begin{verbatim}
    foldLeft(List(1,2,3),z)(f) == (((f(z,1),2),3)))
\end{verbatim}

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

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

In the first line above, we \emph{annotate} function \texttt{foldLeft}
as tail recursive using \texttt{@annotation.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
\texttt{foldLeft}, similar to what we did with \texttt{foldRight}.

\begin{verbatim}
    def sum3(ns: List[Int]) =
      foldLeft(ns, 0)(_ + _)
    
    def product3(ns: List[Double]) =
      foldLeft(ns, 1.0)(_ * _)
\end{verbatim}

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

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

\begin{verbatim}
    def length2[A](ls: List[A]): Int =
      foldLeft(ls, 0)((acc,_) => acc + 1)
\end{verbatim}

We can also implement list reversal using \texttt{foldLeft} as follows:

\begin{verbatim}
    def reverse2[A](ls: List[A]): List[A] =
      foldLeft(ls, List[A]())((acc,x) => Cons(x,acc))
\end{verbatim}

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

Because \texttt{foldLeft} is tail recursive and \texttt{foldRight} is
not, \texttt{foldLeft} is usually safer and more efficient to use in
than \texttt{foldRight}. (If the list argument is lazily evaluated or
the function argument \texttt{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 \texttt{foldRight}, we can
first apply \texttt{reverse} to the list argument and then apply
\texttt{foldLeft} as follows:

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

The combining function in the call to \texttt{foldLeft} is the same as
the one passed to \texttt{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, \texttt{squareAll}, takes a list of integers and returns the
corresponding list of squares of the integers.

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

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

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

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 \texttt{squareAll}
and \texttt{lengthAll} as the (broadly useful) function \texttt{map},
defined as follows:

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

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

Thus we can redefine \texttt{squareAll} and \texttt{lengthAll} using
\texttt{map} as follows:

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

We can implement \texttt{map} itself using \texttt{foldRight} as
follows:

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

The folding function \texttt{(x,xs)\ =\textgreater{}\ Cons(f(x),xs)}
applies the mapping function \texttt{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 \texttt{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
\texttt{map1} uses \texttt{foldRight}, which has similar
characteristics. So we need to use these functions with care. However,
we can use the reversal technique illustrated in \texttt{foldRight2} if
necessary.

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

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

      @annotation.tailrec
      def go(ls: List[A]): Unit = ls match {
        case Nil        => ()
        case Cons(x,xs) => buf += f(x); go(xs)
      }

      go(ls)
      List(buf.toList: _*) 
    }
\end{verbatim}

A \texttt{ListBuffer} is a mutable list data structure from the Scala
library. The operation \texttt{+=} appends a single element to the end
of the buffer in constant time. The method \texttt{toList} converts the
\texttt{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, \texttt{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{verbatim}
    def getEven(ns: List[Int]): List[Int] = ns match {
      case Nil        => Nil
      case Cons(x,xs) =>
        if (x % 2 == 0)  // divisible evenly by 2
          Cons(x,getEven(xs))
        else
          getEven(xs)
    }
\end{verbatim}

The second, \texttt{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{verbatim}
    def doublePos(ns: List[Int]): List[Int]  = ns match {
      case Nil        => Nil
      case Cons(x,xs) =>
        if (0 < x)
          Cons(2*x, doublePos(xs))
        else
          doublePos(xs)
    }           
\end{verbatim}

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

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

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

Therefore, we can redefine \texttt{getEven} and \texttt{doublePos} as
follows:

\begin{verbatim}
    def getEven2(ns: List[Int]): List[Int] =
      filter(ns)(x => x % 2 == 0)

    def doublePos2(ns: List[Int]): List[Int] =
      map(filter(ns)(x => 0 < x))(y => 2 * y)
\end{verbatim}

Function \texttt{doublePos2} exhibits both the \texttt{filter} and the
\texttt{map} patterns of computation.

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

We can implement \texttt{filter} in terms of \texttt{foldRight} as
follows:

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

Above, the folding function
\texttt{(x,xs)\ =\textgreater{}\ if\ (p(x))\ Cons(x,xs)\ else\ xs}
applies the filter predicate \texttt{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 \texttt{map} applies its function argument
\texttt{f} to every element of a list and returns the list of results.
If the function argument \texttt{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 \texttt{concat} defined in a previous section.

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

\begin{verbatim}
    def flatMap[A,B](ls: List[A])(f: A => List[B]): List[B] =
      concat(map(ls)(f))
\end{verbatim}

or by combining \texttt{map} and \texttt{concat} into one
\texttt{foldRight} as:

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

Above, the function argument to \texttt{foldRight} applies the
\texttt{flatMap} function argument \texttt{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 \texttt{filter} in terms of \texttt{flatMap} as
follows:

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

The function argument to \texttt{flatMap} generates a one-element list
if the filter predicate \texttt{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 x and tail xs, sort the tail xs and insert the
element 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{verbatim}
    def isort(ls: List[Int]): List[Int] = ls match {
      case Nil        => Nil
      case Cons(x,xs) => insert(x,isort(xs))
    }

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

Insertion sort has a (worst and average case) time complexity of
O(\(n^{2}\)) where \(n\) is the length of the input list. (Function
\texttt{isort} requires \(n\) consecutive recursive calls; each call
uses function \texttt{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 \texttt{A} and
substitute it for \texttt{Int} everywhere. Although all Scala data types
support equality and inequality comparison, not all types can be
compared on a \emph{total ordering} (\texttt{\textless{}},
\texttt{\textless{}=}, \texttt{\textgreater{}}, and
\texttt{\textgreater{}=} as well).

Fortunately, the Scala library provides a trait \texttt{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{verbatim}
    trait Ordered[A] {
      def compare(that: A): Int
      def < (that: A): Boolean = (this compare that) <  0
      def > (that: A): Boolean = (this compare that) >  0
      def <=(that: A): Boolean = (this compare that) <= 0
      def >=(that: A): Boolean = (this compare that) >= 0
      define compareTo(that: a) = compare(that)
    }
\end{verbatim}

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

\begin{verbatim}
    def isort[A <: Ordered[A]](ls: List[A]): List[A]
\end{verbatim}

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

By using the upper bound constraint, we can sort data from any type that
extends \texttt{Ordered}. However, the primitive types inherited from
Java do not extend \texttt{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 \texttt{\textless{}\%} instead
of \texttt{\textless{}:}. This \texttt{A} to be any type that is a
subtype of or convertible to \texttt{Ordered{[}A{]}}.

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

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

We could define \texttt{insert} inside \texttt{isort} and avoid the
separate type parameterization. But \texttt{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{verbatim}
   def isort2[A](ls: List[A])(leq: (A,A) => Boolean): List[A] =
      ls match {
        case Nil        => Nil
        case Cons(x,xs) => insert2(x,isort2(xs)(leq))(leq)
      }

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

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
\texttt{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{verbatim}
    def msort[A](less: (A, A) => Boolean)(ls: List[A]): List [A] = {

      def merge(as: List[A], bs: List[A]): List[A] = (as,bs) match {
        case (Nil,_)                 => bs
        case (_,Nil)                 => as
        case (Cons(x,xs),Cons(y,ys)) =>
          if (less(x,y))
            Cons(x,merge(xs,bs))
          else
            Cons(y,merge(as,ys))
      }

      val n = length(ls)/2
      if (n == 0)
        ls
      else
        merge(msort(less)(take(ls,n)), msort(less)(drop(ls,n)))
    }
\end{verbatim}

The \texttt{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{verbatim}
    def take[A](ls: List[A], n: Int): List[A]
\end{verbatim}

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

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

The average case time complexity of \texttt{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 \texttt{msort} for lists longer than one results in two
  recursive calls of \texttt{msort}.
\item
  But each successive call of \texttt{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 \texttt{msort} as follows:

\begin{verbatim}
    msort((x: Int, y: Int) => x < y)(List(5, 7, 1, 3))
\end{verbatim}

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

\begin{verbatim}
    val intSort     = msort((x: Int, y: Int) => x < y) _
    val descendSort = msort((x: Int, y: Int) => x > y) _
\end{verbatim}

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}), we developed several functions for a simple \texttt{List}
module. Our module is related to the builtin Scala \texttt{List} module
(from \texttt{scala.collection.immutable}), but it differs in several
ways.

Our \texttt{List} module is standalone module; the Scala \texttt{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.11.7
\texttt{List} is defined as follows:

\begin{verbatim}
    sealed abstract class List[+A] extends AbstractSeq[A]
      with LinearSeq[A]
      with Product
      with GenericTraversableTemplate[A, List]
      with LinearSeqOptimized[A, List[A]]
      with java.io.Serializable 
\end{verbatim}

Our \texttt{List} module consists of functions in which all arguments
must be given explicitly; the Scala \texttt{List} consists of methods on
the \texttt{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 \texttt{\textless{}} 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 \texttt{Cons(x,xs)} is written as \texttt{x\ ::\ xs} using the
standard Scala library. The \texttt{::} 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 \texttt{:} is right associative.
Thus method \texttt{x\ ::\ xs} represents the method call
\texttt{xs.::(x)}, which in turn calls the data constructor. We can
write \texttt{x\ ::\ y\ ::\ z\ ::\ zs} without parentheses to mean
\texttt{x\ ::\ (y\ ::\ (z\ ::\ zs))}.

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

\begin{verbatim}
    case Cons(x, Cons(y,ys))
\end{verbatim}

in the \texttt{remdups} function, we can write the pattern:

\begin{verbatim}
    case x :: y :: ys
\end{verbatim}

Our \texttt{append} function is normally written with the infix operator
\texttt{++} 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 \texttt{sum}, \texttt{product}, \texttt{tail}, \texttt{reverse},
and \texttt{length}. There is also a \texttt{head} function to retrieve
the head element of a nonempty list.

Our \texttt{concat} function is parameterless method \texttt{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 \texttt{drop},
\texttt{dropWhile}, \texttt{map}, \texttt{filter}, and \texttt{flatMap}.
There are also analogous functions \texttt{take} and \texttt{takeWhile}.

Our functions \texttt{foldRight} and \texttt{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 \texttt{head}, \texttt{take}, \texttt{takeWhile}, and the
appending and folding methods mentioned above, the Scala List library
has other useful methods such as \texttt{forall}, \texttt{exists},
\texttt{scanLeft}, \texttt{scanRight}, \texttt{zip}, and
\texttt{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}
\tightlist
\item
  \url{List2.scala}
\end{itemize}

\end{document}