\documentclass[]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
\else % if luatex or xelatex
  \ifxetex
    \usepackage{mathspec}
  \else
    \usepackage{fontspec}
  \fi
  \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
}{}
\PassOptionsToPackage{hyphens}{url} % url is loaded by hyperref
\usepackage[unicode=true]{hyperref}
\hypersetup{
            pdftitle={CSci 450: Org. of Programming Languages List Programming},
            pdfauthor={H. Conrad Cunningham},
            pdfborder={0 0 0},
            breaklinks=true}
\urlstyle{same}  % don't use monospace font for urls
\usepackage{color}
\usepackage{fancyvrb}
\newcommand{\VerbBar}{|}
\newcommand{\VERB}{\Verb[commandchars=\\\{\}]}
\DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}}
% Add ',fontsize=\small' for more characters per line
\newenvironment{Shaded}{}{}
\newcommand{\KeywordTok}[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{\BaseNTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\FloatTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.53,0.00,0.00}{#1}}
\newcommand{\CharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\StringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.73,0.40,0.53}{#1}}
\newcommand{\ImportTok}[1]{#1}
\newcommand{\CommentTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textit{#1}}}
\newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.73,0.13,0.13}{\textit{#1}}}
\newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\OtherTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{#1}}
\newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.02,0.16,0.49}{#1}}
\newcommand{\VariableTok}[1]{\textcolor[rgb]{0.10,0.09,0.49}{#1}}
\newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
\newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.40,0.40,0.40}{#1}}
\newcommand{\BuiltInTok}[1]{#1}
\newcommand{\ExtensionTok}[1]{#1}
\newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.74,0.48,0.00}{#1}}
\newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.49,0.56,0.16}{#1}}
\newcommand{\RegionMarkerTok}[1]{#1}
\newcommand{\InformationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\WarningTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\AlertTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
\newcommand{\ErrorTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
\newcommand{\NormalTok}[1]{#1}
\usepackage{longtable,booktabs}
% Fix footnotes in tables (requires footnote package)
\IfFileExists{footnote.sty}{\usepackage{footnote}\makesavenoteenv{long table}}{}
\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}
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
}
\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}

\title{CSci 450: Org. of Programming Languages\\
List Programming}
\author{H. Conrad Cunningham}
\date{18 October 2017}

\begin{document}
\maketitle

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

\textbf{Acknowledgements:} In Summer 2016, I adapted and revised this
chapter from chapter 5 of my \emph{Notes on Functional Programming with
Haskell} and from my notes on \emph{Functional Data Structures} from the
Spring 2016 Scala variant of CSci 555. The latter was based, in part, on
chapter 3 of the book \emph{Functional Programming in Scala} by Paul
Chiusano and Runar Bjarnason (Manning, 2015).

In 2017, I continue to develop this chapter.

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.

\textbf{Advisory}: The HTML version of this document may require use of
a browser that supports the display of MathML. A good choice as of
September 2017 is a recent version of Firefox from Mozilla.

TODO:

\begin{itemize}
\tightlist
\item
  Consider other examples--small and large
\item
  Consider discussion of testing
\item
  Consider integrating more discussion of abstract data types
\item
  Mention other Prelude or library functions not discussed
\item
  Edit and add more exercises (e.g., Candy Bowl, Cookie Jar)
\end{itemize}

\setcounter{section}{3}

\section{List Programming}\label{list-programming}

\subsection{Chapter Introduction}\label{chapter-introduction}

This chapter introduces the list data type and develops the fundamental
programming concepts and techniques for first-order polymorphic
functions to process lists.

The goals of the chapter are for the students to be able to:

\begin{itemize}
\item
  develop correct Haskell functional programs consisting of first-order
  polymorphic functions that solve problems by processing lists
\item
  develop Haskell list-processing programs that terminate and are
  efficient and elegant.
\end{itemize}

Upon successful completion of this chapter, students should be able to:

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  describe the basic syntax and semantics of first-order, polymorphic,
  Haskell functions for processing lists and strings
\item
  describe the Haskell list and string data types
\item
  develop first-order Haskell functional programs using lists, strings,
  pattern matching, polymorphism, and infix operators
\item
  apply the follow-types-to-implementations (form of algorithm follows
  the form of the data) and other techniques to develop Haskell programs
\item
  compare different implementations of the same functionality for
  termination and efficiency
\item
  use the appropriate programming techniques to develop Haskell
  list-processing programs that terminate and execute efficiently
\item
  appreciate the mathematical characteristics of Haskell functions
  (e.g., to state properties of functions and operators)
\end{enumerate}

The Haskell module for this chapter is in
\href{code04/Mod04Lists.hs}{\texttt{Mod04Lists.hs}}.

\subsection{Polymorphic List Data
Type}\label{polymorphic-list-data-type}

As we have seen, 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.

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 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 purely functional programs must be
\emph{immutable}, not subject to change as the program executes.

Functional programming languages often have a number of immutable data
structures. However, the most salient one is the list.

We mentioned the Haskell list and string data types in a previous
chapter. In this chapter, we look at lists in depth. Strings are just
special cases of lists.

S\#\#\# List: \texttt{{[}t{]}}

The primary built-in data structure in Haskell is the list, a sequence
of values. All the elements in a list must have the same type. Thus we
declare lists with the notation \texttt{{[}t{]}} to denote a list of
zero or more elements of type \texttt{t}.

A \emph{list} is is 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 \emph{list} of elements.

The Haskell list is an example of an \emph{algebraic data type}. We
discuss that concept in a later section.

A matching pair of empty square brackets (\texttt{{[}{]}}), pronounced
``nil'', represents the empty list.

A colon (\texttt{:}), pronounced ``cons'', represents the \emph{list
constructor} operation between a \emph{head} element on the left and a
\emph{tail} list on the right.

Example lists include:

\begin{verbatim}
    []
    2:[]
    3:(2:[])
\end{verbatim}

The Haskell language adds a bit of \emph{syntactic sugar} to make
expressing lists easier. (By syntactic sugar, we mean notation that
simplifies expression of a concept but that adds no new functionality to
the language. The new notation can be defined in terms of other notation
within the language.)

The cons operations binds from the right. Thus

\begin{verbatim}
    5:(3:(2:[]))
\end{verbatim}

can be written as:

\begin{verbatim}
    5:3:2:[]
\end{verbatim}

We can write this as a comma-separated sequence enclosed in brackets as
follows:

\begin{verbatim}
    [5,3,2]
\end{verbatim}

Haskell supports two list selector functions, \texttt{head} and
\texttt{tail}, such that

\begin{quote}
\texttt{head\ (h:t)} \(\Longrightarrow\) \texttt{h}
\end{quote}

where \texttt{h} is the head element of list, and

\begin{quote}
\texttt{tail\ (h:t)} \(\Longrightarrow\) \texttt{t}
\end{quote}

where \texttt{t} is the tail list.

Aside: Instead of \texttt{head}, Lisp uses \texttt{car} and other
languages use \texttt{hd}, \texttt{first}, etc. Instead of
\texttt{tail}, Lisp uses \texttt{cdr} and other languages use
\texttt{tl}, \texttt{rest}, etc.

The Prelude library supports a number of other useful functions on
lists. For example, \texttt{length} takes a list and returns its length.

Note that lists are defined inductively. That is, they are defined in
terms of a base element \texttt{{[}{]}} and the list constructor
operation cons (\texttt{:}). As you would expect, a form of mathematical
induction can be used to prove that list-manipulating functions satisfy
various properties. We will discuss in a later chapter.

\subsubsection{\texorpdfstring{String:
\texttt{String}}{String: String}}\label{string-string}

In Haskell, a \emph{string} is treated as a list of characters. Thus the
data type \texttt{String} is defined as a \emph{type synonym}:

\begin{verbatim}
    type String = [Char]
\end{verbatim}

In addition to the standard list syntax, a \texttt{String} literal can
be given by a sequence of characters enclosed in double quotes. For
example, \texttt{"oxford"} is shorthand for
\texttt{{[}’o’,’x’,’f’,’o’,’r’,’d’{]}}.

Strings can contain any graphic character or any special character given
as escape code sequence (using backslash). The special escape code
\texttt{\textbackslash{}\&} is used to separate any character sequences
that are otherwise ambiguous.

Example: \texttt{"Hello\textbackslash{}nworld!\textbackslash{}n"} is a
string that has two newline characters embedded.

Example: \texttt{"\textbackslash{}12\textbackslash{}\&3"} represents the
list
\texttt{{[}\textquotesingle{}\textbackslash{}12\textquotesingle{},\textquotesingle{}3\textquotesingle{}{]}}.

Because strings are represented as lists, all of the Prelude functions
for manipulating lists also apply to strings.

Consider a function to compute the length of a string:

\begin{verbatim}
    len :: String -> Int
    len s  =  if s == [] then 0 else 1 + len (tail s)
\end{verbatim}

Note that the argument string for the recursive application of
\texttt{len} is simpler (i.e., shorter) than the original argument. Thus
\texttt{len} will eventually be applied to a \texttt{{[}{]}} argument
and, hence, \texttt{len}'s evaluation will terminate.

How efficient is this function (i.e., its time and space complexity)?

Consider the evaluation of the expression \texttt{len\ "five"}.

\begin{longtable}[]{@{}ll@{}}
\toprule
& \texttt{len\ "five"}\tabularnewline
\(\Longrightarrow\) &
\texttt{if\ "five"\ ==\ {[}{]}\ then\ 0\ else\ 1\ +\ len\ (tail\ "five")}\tabularnewline
\(\Longrightarrow\) &
\texttt{if\ False\ then\ 0\ else\ 1\ +\ len\ (tail\ "five")}\tabularnewline
\(\Longrightarrow\) & \texttt{1\ +\ len\ (tail\ "five")}\tabularnewline
\(\Longrightarrow\) & \texttt{1\ +\ len\ "ive"}\tabularnewline
\(\Longrightarrow\) &
\texttt{1\ +\ (if\ "ive"\ ==\ {[}{]}\ then\ 0\ else\ 1\ +\ len\ (tail\ "ive"))}\tabularnewline
\(\Longrightarrow\) &
\texttt{1\ +\ (if\ False\ then\ 0\ else\ 1\ +\ len\ (tail\ "ive"))}\tabularnewline
\(\Longrightarrow\) &
\texttt{1\ +\ (1\ +\ len\ (tail\ "ive"))}\tabularnewline
\(\Longrightarrow\) & \texttt{1\ +\ (1\ +\ len\ "ve")}\tabularnewline
\(\Longrightarrow\) &
\texttt{1\ +\ (1\ +\ (if\ "ve"\ ==\ {[}{]}\ then\ 0\ else\ 1\ +\ len\ (tail\ "ve")))}\tabularnewline
\(\Longrightarrow\) &
\texttt{1\ +\ (1\ +\ (if\ False\ then\ 0\ else\ 1\ +\ len\ (tail\ "ve")))}\tabularnewline
\(\Longrightarrow\) &
\texttt{1\ +\ (1\ +\ (1\ +\ len\ (tail\ "ve")))}\tabularnewline
\(\Longrightarrow\) &
\texttt{1\ +\ (1\ +\ (1\ +\ len\ "e"))}\tabularnewline
\(\Longrightarrow\) &
\texttt{1\ +\ (1\ +\ (1\ +\ (if\ "e"\ ==\ {[}{]}\ then\ 0\ else\ 1\ +\ len\ (tail\ "e"))))}\tabularnewline
\(\Longrightarrow\) &
\texttt{1\ +\ (1\ +\ (1\ +\ (if\ False\ then\ 0\ else\ 1\ +\ len\ (tail\ "e"))))}\tabularnewline
\(\Longrightarrow\) &
\texttt{1\ +\ (1\ +\ (1\ +\ (1\ +\ len\ (tail\ "e"))))}\tabularnewline
\(\Longrightarrow\) &
\texttt{1\ +\ (1\ +\ (1\ +\ (1\ +\ len\ "")))}\tabularnewline
\(\Longrightarrow\) &
\texttt{1\ +\ (1\ +\ (1\ +\ (1\ +\ 0)))}\tabularnewline
\(\Longrightarrow\) & \texttt{1\ +\ (1\ +\ (1\ +\ 1))}\tabularnewline
\(\Longrightarrow\) & \texttt{1\ +\ (1\ +\ 2)}\tabularnewline
\(\Longrightarrow\) & \texttt{1\ +\ 3}\tabularnewline
\(\Longrightarrow\) & \texttt{4}\tabularnewline
\bottomrule
\end{longtable}

The number of reduction steps in proportional to the length of the input
list. Similarly, the amount of space required (given lazy evaluation) is
also proportional to the length of the input list.

\subsubsection{Polymorphic lists}\label{polymorphic-lists}

The above definition of \texttt{len} only works for strings. How can we
make it work for a list of integers or other elements?

For an arbitrary type \texttt{a}, we want \texttt{len} to take objects
of type \texttt{{[}a{]}} and return an \texttt{Int} value. Thus its type
signature could be:

\begin{verbatim}
    len :: [a] -> Int
\end{verbatim}

If \texttt{a} is a variable name (i.e., it begins with a lowercase
letter) that does not already have a value, then the type expression
\texttt{a} used as above is a \emph{type variable}; it can represent an
arbitrary type. All occurrences of a type variable appearing in a type
signature must, of course, represent the same type.

An object whose type includes one or more type variables can be thought
of having many different types and is thus described as having a
\emph{polymorphic type}. (The next subsection gives more detail on
polymorphism in general.)

Polymorphism and first-class functions are powerful abstraction
mechanisms: they allow irrelevant detail to be hidden.

Other examples of polymorphic list functions from the Prelude library
include:

\begin{verbatim}
    head :: [a] -> a
    tail :: [a] -> [a]
    (:)  :: a -> [a] -> [a]
\end{verbatim}

\subsubsection{Kinds of polymorphism}\label{kinds-of-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}.

    Consider the language Java. It 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.

    Haskell's \emph{type class} mechanism, which we examine in a later
    chapter, implements overloading polymorphism in Haskell.
  \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}. This the polymorphism associated with the class
    structure in Java.

    Haskell does not support subtyping. Its type classes do support
    \emph{class extension}, which enables one class to inherit the
    properties of another. However, Haskell's classes are not types.
  \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 (e.g., Java) community often calls
  this type of polymorphism \emph{generics} or \emph{generic
  programming}.

  The functional programming (e.g., Haskell) community often calls this
  simply \emph{polymorphism}.
\end{enumerate}

\subsection{Programming with List
Patterns}\label{programming-with-list-patterns}

In the factorial examples in an earlier chapter, we used integer
patterns and guards to break out various cases of a function definition
into separate equations. Lists and other data types may also be used in
patterns.

Pattern matching helps enable the \emph{form of the algorithm} to match
the \emph{form of the data structure}. Or, as others may say, 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 that is needed for a task.

In general, lists have two cases that need to be handled: the empty list
and the nonempty list. Breaking a definition for a list-processing
function into these two cases is usually a good place to begin.

\subsubsection{\texorpdfstring{Summing a list of integers:
\texttt{sum\textquotesingle{}}}{Summing a list of integers: sum'}}\label{summing-a-list-of-integers-sum}

Consider a function \texttt{sum\textquotesingle{}} to sum all the
elements in a list of integers. That is, if the list is

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

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 (that is,
\((x + y) + z = x + (y + z)\) for any integers \(x\), \(y\), and \(z\)),
the above additions can be computed in any order.

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. Since \(0 + x = x = x + 0\) for all integers \(x\),
zero is the identity element for addition.

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 Haskell defines lists recursively as a 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\textquotesingle{}} in Haskell as follows. This is similar to
the Prelude function \texttt{sum}.

\begin{verbatim}
    {- Function sum' sums a list of integers. It is similar to 
       function sum in the Prelude.
    -}
    sum' :: [Int] -> Int 
    sum' []     = 0           -- nil list 
    sum' (x:xs) = x + sum' xs -- non-nil list 
\end{verbatim}

\begin{itemize}
\item
  As noted previously, all of the text between the symbol
  ``\texttt{-\/-}'' and the end of the line represents a \emph{comment};
  it is ignored by the Haskell interpreter.

  The text enclosed by the \texttt{\{-} and \texttt{-\}} is a block
  comment, that can extend over multiple lines.
\item
  This definition uses two \emph{legs}. The equation in the first leg is
  used for nil list arguments, the second for non-nil arguments.
\item
  Note the \texttt{(x:xs)} pattern in the second leg. The ``\texttt{:}''
  denotes the list constructor operation \emph{cons}.

  If this pattern succeeds, then the head element of the list argument
  is bound to the variable \texttt{x} and the tail of the list argument
  is bound to the variable \texttt{xs}. These bindings hold for the
  right-hand side of the equation.
\item
  The use of the cons in the pattern simplifies the expression of the
  case. Otherwise the second leg would have to be stated using the
  \texttt{head} and \texttt{tail} selectors as follows:

\begin{verbatim}
sum' xs = head xs + sum' (tail xs)
\end{verbatim}
\item
  We use the simple name \texttt{x} to represent items of some type and
  the name \texttt{xs}, the same name with an \texttt{s} (for sequence)
  appended, to represent a list of that same type. This is a useful
  convention (adopted from the classic Bird and Wadler textbook
  {[}Bird-Wadler 1998{]}) that helps make a definition easier to
  understand.
\item
  Remember that patterns (and guards) are tested in the order of
  occurrence (i.e., left to right, top to bottom). Thus, in most
  situations, the cases should be listed from the most specific (e.g.,
  nil) to the most general (e.g., non-nil).
\item
  The length of a non-nil argument decreases by one for each successive
  recursive application. Thus \texttt{sum\textquotesingle{}} will
  eventually be applied to a \texttt{{[}{]}} argument and terminate.
\end{itemize}

For a list consisting of elements 2, 4, 6, and 8, that is,
\texttt{2:4:6:8:{[}{]}}, function \texttt{sum\textquotesingle{}}
computes

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

giving the integer result 20.

Function \texttt{sum\textquotesingle{}} 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) but \(O(1)\) in space.

\subsubsection{\texorpdfstring{Multiplying a list of numbers:
\texttt{product\textquotesingle{}}}{Multiplying a list of numbers: product'}}\label{multiplying-a-list-of-numbers-product}

Now consider a function \texttt{product\textquotesingle{}} to multiply
together a list of integers.

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\textquotesingle{}} with two base
cases and one recursive case, as follows. This is similar to the Prelude
function \texttt{product}.

\begin{verbatim}
    product' :: [Integer] -> Integer
    product' []     = 1 
    product' (0:_)  = 0
    product' (x:xs) = x * product' xs 
\end{verbatim}

Note the use of the wildcard pattern underscore ``\texttt{\_}'' in the
second leg above. This represents a ``don't care'' value. In this
pattern it matches the tail, but no value is bound; the right-hand side
of the equation does not need the actual value.

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

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

For a list consisting of elements 2, 4, 6, and 8, that is,
\texttt{2:4:6:8:{[}{]}}, function \texttt{product\textquotesingle{}}
computes:

\begin{verbatim}
    2 * (4 * (6 * (8 * 1))) 
    
\end{verbatim}

which yields the integer result 384.

For a list consisting of elements 2, 0, 6, and 8, function
\texttt{product\textquotesingle{}} ``short circuits'' the computation
as:

\begin{verbatim}
    2 * 0
\end{verbatim}

Like \texttt{sum\textquotesingle{}}, function
\texttt{product\textquotesingle{}} 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 the first base case.

As with \texttt{sum\textquotesingle{}}, we could redefine this to use a
tail-recursive auxiliary function, which could evaluate in \(O(1)\)
space with tail call optimization.

Note that \texttt{sum\textquotesingle{}} and
\texttt{product\textquotesingle{}} have similar computational patterns.
In a later chapter, we look at how to capture the commonality in a
single higher-order function.

\subsubsection{\texorpdfstring{Length of a list:
\texttt{length\textquotesingle{}}}{Length of a list: length'}}\label{length-of-a-list-length}

As another example, consider the function for the length of a list that
we discussed earlier (as \texttt{len}). Using list patterns we can
define \texttt{length’} as follows:

\begin{verbatim}
    length' :: [a] -> Int
    length' []     = 0              -- nil list
    length' (_:xs) = 1 + length' xs -- non-nil list
\end{verbatim}

Note the use of the wildcard pattern underscore ``\texttt{\_}''. In this
pattern it matches the head, but no value is bound; the right-hand side
of the equation does not need the actual value.

Given a finite list for its argument, does this function terminate? What
are its time and space complexities?

This definition is similar to the definition for \texttt{length} in the
Prelude.

\subsubsection{\texorpdfstring{Remove duplicate elements:
\texttt{remdups}}{Remove duplicate elements: remdups}}\label{remove-duplicate-elements-remdups}

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.

If we restrict the function to lists of integers, we can define Haskell
function \texttt{remdups} as follows:

\begin{verbatim}
    remdups :: [Int] -> [Int]
    remdups (x:y:xs)
      | x == y = remdups (y:xs)
      | x /= y = x : remdups (y:xs)
    remdups xs = xs
\end{verbatim}

\begin{itemize}
\item
  Note the use of the pattern \texttt{(x:y:xs)}. This pattern match
  succeeds if the argument list has at least two elements: the head
  element is bound to \texttt{x}, the second element to \texttt{y}, and
  the tail list to \texttt{xs}.
\item
  Note the use of guards to distinguish between the cases where the two
  elements are equal (\texttt{==}) and where they are not equal
  (\texttt{/=}).
\item
  In this definition the case patterns overlap, that is, a list with at
  least two elements satisfies both patterns. But since the cases are
  evaluated top to bottom, the list only matches the first pattern. Thus
  the second pattern just matches lists with fewer than two elements.
\end{itemize}

What if we wanted to make the list type polymorphic instead of just
integers?

At first glance, it would seem to be sufficient to give \texttt{remdups}
the polymorphic type \texttt{{[}a{]}\ -\textgreater{}\ {[}a{]}}. But the
guards complicate the situation a bit.

Evaluation of the guards requires that Haskell be able to compare
elements of the polymorphic type \texttt{a} for equality (\texttt{==})
and inequality (\texttt{/=}). For some types these comparisons may not
be supported. (For example, suppose the elements are functions.) Thus we
need to restrict the polymorphism to types in which the comparisons are
supported.

We can restrict the range of types by using a \emph{context} predicate.
The following type signature restricts the polymorphism of type variable
\texttt{a} to the built-in \emph{type class} \texttt{Eq}, the group of
types for which both equality (\texttt{==}) and inequality (\texttt{/=})
comparisons have been defined:

\begin{verbatim}
    remdups :: Eq a => [a] -> [a]
\end{verbatim}

Another useful context is the class \texttt{Ord}, which is an
\emph{extension} of class \texttt{Eq}. \texttt{Ord} denotes the class of
objects for which the relational operators \texttt{\textless{}},
\texttt{\textless{}=}, \texttt{\textgreater{}}, and
\texttt{\textgreater{}=} have been defined in addition to \texttt{==}
and \texttt{/=}.

In most situations the type signature can be left off the declaration of
a function. Haskell then attempts to infer an appropriate type. For
\texttt{remdups}, the type inference mechanism would assign the type
\texttt{Eq\ {[}a{]}\ =\textgreater{}\ {[}a{]}\ -\textgreater{}\ {[}a{]}}
. However, in general, it is good practice to give explicit type
signatures.

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.

\subsubsection{More list patterns}\label{more-list-patterns}

The following table shows Haskell parameter patterns, corresponding
arguments, and the result of the attempted match.

\begin{longtable}[]{@{}llll@{}}
\toprule
\textbf{Pattern} & \textbf{Argument} & \textbf{Succeeds?} &
\textbf{Bindings}\tabularnewline
\texttt{1} & \texttt{1} & yes & none\tabularnewline
\texttt{x} & \texttt{1} & yes & \texttt{x} \(\leftarrow\)
\texttt{1}\tabularnewline
\texttt{(x:y)} & \texttt{{[}1,2{]}} & yes & \texttt{x} \(\leftarrow\)
\texttt{1}, \texttt{y} \(\leftarrow\) \texttt{{[}2{]}}\tabularnewline
\texttt{(x:y)} & \texttt{{[}{[}1,2{]}{]}} & yes & \texttt{x}
\(\leftarrow\) \texttt{{[}1,2{]}}, \texttt{y} \(\leftarrow\)
\texttt{{[}{]}}\tabularnewline
\texttt{(x:y)} & \texttt{{[}"olemiss"{]}} & yes & \texttt{x}
\(\leftarrow\) \texttt{"olemiss"}, \texttt{y} \(\leftarrow\)
\texttt{{[}{]}}\tabularnewline
\texttt{(x:y)} & \texttt{"olemiss"} & yes & \texttt{x} \(\leftarrow\)
\texttt{’o’}, \texttt{y} \(\leftarrow\) \texttt{"lemiss"}\tabularnewline
\texttt{(1:x)} & \texttt{{[}1,2{]}} & yes & \texttt{x} \(\leftarrow\)
\texttt{{[}2{]}}\tabularnewline
\texttt{(1:x)} & \texttt{{[}2,2{]}} & no & none\tabularnewline
\texttt{(x:\_:\_:y)} & \texttt{{[}1,2,3,4,5,6{]}} & yes & \texttt{x}
\(\leftarrow\) \texttt{1}, \texttt{y} \(\leftarrow\)
\texttt{{[}4,5,6{]}}\tabularnewline
\texttt{{[}{]}} & \texttt{{[}{]}} & yes & none\tabularnewline
\texttt{{[}x{]}} & \texttt{{[}"Cy"{]}} & yes & \texttt{x} \(\leftarrow\)
\texttt{"Cy"}\tabularnewline
\texttt{{[}1,x{]}} & \texttt{{[}1,2{]}} & yes & \texttt{x}
\(\leftarrow\) \texttt{2}\tabularnewline
\texttt{{[}x,y{]}} & \texttt{{[}1{]}} & no & none\tabularnewline
\texttt{(x,y)} & \texttt{(1,2)} & yes & \texttt{x} \(\leftarrow\)
\texttt{1}, \texttt{y} \(\leftarrow\) \texttt{2}\tabularnewline
\bottomrule
\end{longtable}

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

Suppose we have the declaration:

\begin{verbatim}
    xs = [1,2,3]
\end{verbatim}

As we learned in the data structures course, we can implement this list
as a singly 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_04_01.png}
\caption{\textbf{Figure 4-1: Data sharing in lists}}
\end{figure}

Consider the following declarations

\begin{verbatim}
    ys = 0:xs 
    zs = tail xs 
\end{verbatim}

where

\begin{itemize}
\item
  \texttt{0:xs} returns a list that has a new cell containing \texttt{0}
  in front of the previous list
\item
  \texttt{tail\ xs} 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.

Consider evaluation of the expression \texttt{head\ xs}. It must create
a copy of the head element (in this case \texttt{1}). The result does
not share data with the input list.

Similarly, the list returned by function \texttt{remdups} (defined
above) does not share data with its input list.

\subsubsection{\texorpdfstring{Preconditions for \texttt{head} and
\texttt{tail}}{Preconditions for head and tail}}\label{preconditions-for-head-and-tail}

What should \texttt{tail} return if the list is nil?

One choice is to return a nil list \texttt{{[}{]}}. However, it seems
illogical for an empty list to have a tail.

Consider a typical usage of the \texttt{tail} function. It is normally
an error for a program to attempt to get the tail of an empty list.
Moreover, a program can efficiently check whether a list is empty or
not. So, in this case, it is better to consider \texttt{tail} a partial
function.

Thus, Haskell defines both \texttt{tail} and \texttt{head} to have the
precondition that their parameters are non-nil lists. If we call either
with a nil list, then it will terminate execution with a standard error
message.

\subsubsection{Dropping elements from beginning of
list}\label{dropping-elements-from-beginning-of-list}

We can generalize \texttt{tail} to a function
\texttt{drop\textquotesingle{}} that removes the first \texttt{n}
elements of a list as follows, (This function is called \texttt{drop} in
the Prelude.)

\begin{verbatim}
    drop' :: Int -> [a] -> [a]
    drop' n xs | n <= 0 = xs 
    drop' _ []          = []
    drop' n (_:xs)      = drop' (n-1) xs 
\end{verbatim}

Example:

\begin{quote}
\texttt{drop\ 2\ "oxford"} \(\Longrightarrow \cdots\) \texttt{"ford"}
\end{quote}

This function takes a different approach to the ``empty list'' issue
than \texttt{tail} does. Although it is 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\textquotesingle{}} 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 instead that \texttt{drop\textquotesingle{}} would trigger an
error 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. Thus the choice for \texttt{drop\textquotesingle{}} to
return a nil is also pragmatic.

The \texttt{drop\textquotesingle{}} function is tail recursive. The
result list shares space with the input list.

The \texttt{drop\textquotesingle{}} function terminates when either the
list argument is empty or the integer argument is 0 or negative. The
function eventually terminates because each recursive call both shortens
the list and decrements the integer.

What is the time complexity of \texttt{drop\textquotesingle{}}?

There are two base cases. For the first leg, the function must terminate
in \(O(max(1,\)\texttt{n}\())\) steps. For the second leg, the function
must terminate within \(O(\)\texttt{length\ xs}\()\) steps. So the
function must terminate within
\(O(min(max(1,\)\texttt{n}\(),\)\texttt{length\ xs}\())\) steps.

What is the space complexity of \texttt{drop\textquotesingle{}}?

This tail recursive function evaluates in constant space when optimized.

\subsubsection{Taking elements from the beginning of a
list}\label{taking-elements-from-the-beginning-of-a-list}

Similarly, we can generalize \texttt{head\textquotesingle{}} to a
function \texttt{take} that takes a number \texttt{n} and a list and
returns the first \texttt{n} elements of the list.

\begin{verbatim}
    take' :: Int -> [a] -> [a]
    take' n _ | n <= 0 = []
    take' _ []         = []
    take' n (x:xs)     = x : take' (n-1) xs
\end{verbatim}

Consider the following questions for this function?

\begin{itemize}
\tightlist
\item
  What is returned when the list argument is nil?
\item
  Does evaluation of this function terminate?
\item
  Does the result share data with the input?
\item
  Is the function tail recursive?
\item
  What are its time and space complexities?
\end{itemize}

Example:

\begin{quote}
\texttt{take\ 2\ "oxford"} \(\Longrightarrow \cdots\) \texttt{"ox"}
\end{quote}

\subsection{Using Infix Operations}\label{using-infix-operations}

In Haskell, a \emph{binary operation} is a function of type
\texttt{t1\ -\textgreater{}\ t2\ -\textgreater{}\ t3} for some types
\texttt{t1}, \texttt{t2}, and \texttt{t3}.

We usually prefer to use \emph{infix} syntax rather than prefix syntax
to express the application of a binary operation. Infix operators
usually make expressions easier to read; they also make statement of
mathematical properties more convenient.

Often we use several infix operators in an expression. To ensure that
the expression is not ambiguous (i.e., the operations are done in the
desired order), we must either use parentheses to give the order
explicitly (e.g., \texttt{((y\ *\ (z+2))\ +\ x)}) or use syntactic
conventions to give the order implicitly.

Typically the application order for adjacent operators of different
kinds is determined by the relative \emph{precedence} of the operators.
For example, the multiplication (\texttt{*}) operation has a higher
precedence (i.e., binding power) than addition (\texttt{+}), so, in the
absence of parentheses, a multiplication will be done before an adjacent
addition. That is, \texttt{x\ +\ y\ *\ z} is taken as equivalent to
\texttt{(x\ +\ (y\ *\ z))}.

In addition, the application order for adjacent operators of the same
binding power is determined by a \emph{binding} (or \emph{association})
order. For example, the addition (\texttt{+}) and subtraction \texttt{-}
operations have the same precedence. By convention, they bind more
strongly to the \emph{left} in arithmetic expressions. That is,
\texttt{x\ +\ y\ -\ z} is taken as equivalent to
\texttt{((x\ +\ y)\ -\ z)}.

By convention, operators such as exponentiation (denoted by
\texttt{\^{}}) and cons bind more strongly to the \emph{right.} Some
other operations (e.g., division and the relational comparison
operators) have no default binding order--they are said to have
\emph{free} binding.

Accordingly, Haskell provides the statements \texttt{infix},
\texttt{infixl}, and \texttt{infixr} for declaring a symbol to be an
infix operator with free, left, and right binding, respectively. The
first argument of these statements give the precedence level as an
integer in the range 0 to 9, with 9 being the strongest binding. Normal
function application has a precedence of 10.

The operator precedence table for a few of the common operations from
the Prelude is shown below. We introduce the \texttt{++} operator in the
next subsection.

\begin{verbatim}
    infixr 8 ^                     -- exponentiation
    infixl 7 *                     -- multiplication
    infix  7 /                     -- division
    infixl 6 +, -                  -- addition, subtraction
    infixr 5 :                     -- cons
    infix  4 ==, /=, <, <=, >=, >  -- relational comparisons
    infixr 3 &&                    -- Boolean AND
    infixr 2 ||                    -- Boolean OR 
\end{verbatim}

\subsubsection{\texorpdfstring{Appending two lists:
\texttt{++}}{Appending two lists: ++}}\label{appending-two-lists}

Suppose we want a function that takes two lists and returns their
concatenation, that is, \emph{appends} the second list after the first.
This function is a binary operation on lists much like \texttt{+} is a
binary operation on integers.

Further suppose we want to introduce the infix operator symbol
\texttt{++} for the append function. Since we want to evaluate lists
lazily from their heads, we choose right binding for both cons and
\texttt{++}. Since append is, in a sense, an extension of cons
(\texttt{:}), we give them the same precedence:

\begin{verbatim}
    infixr 5 ++
\end{verbatim}

Consider the definition of the append function. We must define the
\texttt{++} operation in terms of application of already defined list
operations and recursive applications of itself. The only applicable
simpler operation is cons.

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

The cons operator 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, \texttt{++} 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 cons, it seems reasonable that an algorithm for
\texttt{++} 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 nil, then the function can just return the
  right operand.
\item
  If the left operand is a 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{++} as follows:

\begin{verbatim}
    infixr 5 ++
    
    (++) :: [a] -> [a] -> [a]
    [] ++ xs     = xs           -- nil left operand 
    (x:xs) ++ ys = x:(xs ++ ys) -- non-nil left operand 
\end{verbatim}

Above we use infix patterns on the left-hand sides of the defining
equations.

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

Consider the evaluation of the expression
\texttt{{[}1,2,3{]}\ ++\ {[}3,2,1{]}}.

\begin{longtable}[]{@{}ll@{}}
\toprule
& \texttt{{[}1,2,3{]}\ ++\ {[}3,2,1{]}}\tabularnewline
\(\Longrightarrow\) &
\texttt{1:({[}2,3{]}\ ++\ {[}3,2,1{]})}\tabularnewline
\(\Longrightarrow\) &
\texttt{1:(2:({[}3{]}\ ++\ {[}3,2,1{]}))}\tabularnewline
\(\Longrightarrow\) &
\texttt{1:(2:(3:({[}{]}\ ++\ {[}3,2,1{]})))}\tabularnewline
\(\Longrightarrow\) & \texttt{1:(2:(3:{[}3,2,1{]}))}\tabularnewline
\(=\) & \texttt{{[}1,2,3,3,2,1{]}}\tabularnewline
\bottomrule
\end{longtable}

The number of steps needed to evaluate \texttt{xs\ ++\ ys} is
proportional to the length of \texttt{xs}, the left operand. That is,
the time complexity is \(O(n)\), where \(n\) is the length \texttt{xs}.

Moreover, \texttt{xs\ ++\ ys} only needs to copy the list \texttt{xs}.
The list \texttt{ys} 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!

Consider the following questions:

\begin{itemize}
\tightlist
\item
  Is \texttt{++} tail recursive?
\item
  What is the space complexity of \texttt{++}?
\end{itemize}

\subsubsection{Properties of operations}\label{properties-of-operations}

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

\emph{Associativity of} \texttt{++}: For any finite lists \texttt{xs},
\texttt{ys}, and \texttt{zs},
\texttt{xs\ ++\ (ys\ ++\ zs)\ ==\ (xs\ ++\ ys)\ ++\ zs}.

\emph{Identity for} \texttt{++}: For any finite list \texttt{xs},
\texttt{{[}{]}\ ++\ xs\ =\ xs\ =\ xs\ ++\ {[}{]}}.

We will prove these and other properties in a later chapter.

Mathematically, the list data type and the binary operation \texttt{++}
form a kind of abstract algebra called a \emph{monoid}. Function
\texttt{++} is closed (i.e., it takes two lists and gives a list back),
is associative, and has an identity element. ` Similarly, we can state
properties of combinations of functions. We can prove these using
techniques we study in a later chapter. For example, consider the
functions defined above in this chapter.

\begin{itemize}
\item
  For all finite lists \texttt{xs}, we have the following distribution
  properties:

\begin{verbatim}
    sum' (xs ++ ys)     = sum' xs + sum' ys 
    product' (xs ++ ys) = product' xs * product' ys 
    length' (xs ++ ys)  = length' xs + length' ys 
\end{verbatim}
\item
  For all natural numbers \texttt{n} and finite lists \texttt{xs},

\begin{verbatim}
    take n xs ++ drop n xs = xs
\end{verbatim}
\end{itemize}

\subsubsection{\texorpdfstring{Element selection:
\texttt{!!}}{Element selection: !!}}\label{element-selection}

As another example of an infix operation, consider the list selection
operator \texttt{!!}. The expression \texttt{xs!!n} selects element
\texttt{n} of list \texttt{xs} where the head is in position 0. It is
defined in the Prelude similar to the way \texttt{!!} is defined below:

\begin{verbatim}
    infixl 9 !!

    (!!) :: [a] -> Int -> a 
    xs     !! n | n < 0 = error "!! negative index"
    []     !! _         = error "!! index too large"
    (x:_)  !! 0         = x 
    (_:xs) !! n         = xs !! (n-1) 
\end{verbatim}

Consider the following questions concerning the element selection
operator:

\begin{itemize}
\tightlist
\item
  What is the precondition for element selection?
\item
  Does evaluation terminate?
\item
  Is the operator tail recursive?
\item
  Does the result share any data with the input list?
\item
  What are its time and space complexities?
\end{itemize}

\subsubsection{\texorpdfstring{Reversing a list:
\texttt{rev}}{Reversing a list: rev}}\label{reversing-a-list-rev}

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 nil, then the function returns nil. If
the argument is non-nil, then the function can append the head element
at the back of the reversed tail.

\begin{verbatim}
    rev :: [a] -> [a]
    rev []     = []            -- nil argument
    rev (x:xs) = rev xs ++ [x] -- non-nil argument
\end{verbatim}

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

How efficient is this function?

Consider the evaluation of the expression \texttt{rev\ "bat"}.

\begin{longtable}[]{@{}ll@{}}
\toprule
& \texttt{rev\ "bat"}\tabularnewline
\(\Longrightarrow\) & \texttt{(rev\ "at")\ ++\ "b"}\tabularnewline
\(\Longrightarrow\) &
\texttt{((rev\ "t")\ ++\ "a")\ ++\ "b"}\tabularnewline
\(\Longrightarrow\) &
\texttt{(((rev\ "")\ ++\ "t")\ ++\ "a")\ ++\ "b"}\tabularnewline
\(\Longrightarrow\) &
\texttt{((""\ ++\ "t")\ ++\ "a")\ ++\ "b"}\tabularnewline
\(\Longrightarrow\) & \texttt{("t"\ ++\ "a")\ ++\ "b"}\tabularnewline
\(\Longrightarrow\) &
\texttt{(\textquotesingle{}t\textquotesingle{}:(""\ ++\ "a"))\ ++\ "b"}\tabularnewline
\(\Longrightarrow\) & \texttt{"ta"\ ++\ "b"}\tabularnewline
\(\Longrightarrow\) &
\texttt{\textquotesingle{}t\textquotesingle{}:("a"\ ++\ "b")}\tabularnewline
\(\Longrightarrow\) &
\texttt{\textquotesingle{}t\textquotesingle{}:(\textquotesingle{}a\textquotesingle{}:(""\ ++\ "b"))}\tabularnewline
\(\Longrightarrow\) &
\texttt{\textquotesingle{}t\textquotesingle{}:(\textquotesingle{}a\textquotesingle{}:"b")}\tabularnewline
\(=\) & \texttt{"tab"}\tabularnewline
\bottomrule
\end{longtable}

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{++}.

The initial list and its reverse do not share data.

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

\emph{Distribution}: For any finite lists \texttt{xs} and \texttt{ys},
\texttt{rev\ (xs\ ++\ ys)\ =\ rev\ ys\ ++\ rev\ xs}.

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

Also, for any finite lists \texttt{xs} and \texttt{ys} and natural
numbers \texttt{n}, we can state properties such as:

\begin{verbatim}
    rev (xs ++ ys) = rev ys ++ rev xs
    take n (rev xs)  = rev (drop (length xs - n) xs)
\end{verbatim}

\subsubsection{\texorpdfstring{Tail recursive
\texttt{reverse}}{Tail recursive reverse}}\label{tail-recursive-reverse}

Most of the list function definitions examined so far are \emph{backward
recursive}. That is, for each case the recursive applications are
embedded within another expression. Operationally, significant work is
done after the recursive call returns.

Now let's look at the problem of reversing a list again to see whether
we can devise a more efficient \emph{tail recursive} solution.

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

\begin{verbatim}
    rev' [] ys     = ys
    rev' (x:xs) ys = rev' xs (x:ys) 
\end{verbatim}

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

We note that \texttt{rev\ xs} is equivalent to
\texttt{rev’\ xs\ {[}{]}}. (We can prove this using the techniques in a
later chapter.)

To define a single-argument replacement for \texttt{rev}, we can embed
the definition of \texttt{rev’} as an \emph{auxiliary} function within
the definition of a new function \texttt{reverse’}. (This is similar to
function \texttt{reverse} in the Prelude.)

\begin{verbatim}
    reverse' :: [a] -> [a]
    reverse' xs = rev xs []
                  where rev []     ys = ys
                        rev (x:xs) ys = rev xs (x:ys)
\end{verbatim}

The \texttt{where} clause introduces the \emph{local definition}
\texttt{rev’} that is only known within the right-hand side of the
defining equation for the function \texttt{reverse’}.

What is the time complexity of 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{rev’}
for each element; \texttt{rev’} requires a single cons operation in the
accumulating parameter.

Where did the increase in efficiency come from?

Each application of \texttt{rev} applies \texttt{++}, a linear time
(i.e., \(O(n)\)) function. In \texttt{rev’}, we replaced the
applications of \texttt{++} by applications of 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.

\subsection{More Useful List
Functions}\label{more-useful-list-functions}

\subsubsection{\texorpdfstring{Another list-breaking function:
\texttt{splitAt}}{Another list-breaking function: splitAt}}\label{another-list-breaking-function-splitat}

Above we defined list-breaking functions \texttt{take\textquotesingle{}}
and \texttt{drop\textquotesingle{}}. It is sometimes useful to have a
single function that breaks a list into two parts.

The function \texttt{splitAt} (shown below as
\texttt{splitAt\textquotesingle{}}) takes an integer \texttt{n} and a
list and returns a pair whose first component is the first \texttt{n}
elements of the list and second component is the list remaining after
the first \texttt{n} elements are removed.

\begin{verbatim}
    splitAt' :: Int -> [a] -> ([a],[a]) 
    splitAt' n xs =  (take' n xs, drop' n xs) 
\end{verbatim}

Can we write an alternative definition that makes only one pass over
argument \texttt{xs}? (That is, it does not call
\texttt{take\textquotesingle{}} and \texttt{drop\textquotesingle{}}.)

\subsubsection{\texorpdfstring{List-combining operations: \texttt{zip}
and
\texttt{unzip}}{List-combining operations: zip and unzip}}\label{list-combining-operations-zip-and-unzip}

Another useful function in the Prelude is \texttt{zip} (shown below as
\texttt{zip’}) which takes two lists and returns a list of pairs of the
corresponding elements. That is, the function fastens the lists together
like a zipper. It's definition is similar to \texttt{zip’} given below:

\begin{verbatim}
    zip' :: [a] -> [b] -> [(a,b)]
    zip' (x:xs) (y:ys) = (x,y) : zip' xs ys -- zip.1
    zip' _      _      = []                 -- zip.1
\end{verbatim}

Function \texttt{zip} applies a \emph{tuple-forming} operation to the
corresponding elements of two lists. It stops the recursion when either
list argument becomes nil. Putting the recursive case first enabled the
two bases cases to be combined into one leg.

Example: \texttt{zip\ {[}1,2,3{]}\ "oxford"} \(\Longrightarrow \cdots\)
\texttt{{[}(1,’o’),(2,’x’),(3,’f’){]}}

Similarly, function \texttt{unzip} in the Prelude takes a list of pairs
and returns a pair of lists. It's definition is similar to
\texttt{unzip\textquotesingle{}} below.

\begin{verbatim}
    unzip' :: [(a,b)] -> ([a],[b])
    unzip' []         = ([],[])
    unzip' ((x,y):ps) = (x:xs, y:ys)
                        where (xs,ys) = unzip' ps
\end{verbatim}

The Prelude includes versions of \texttt{zip} and \texttt{unzip} that
handle the tuple-formation for up to seven input lists: \texttt{zip3}
\(\cdots\) \texttt{zip7} and \texttt{unzip3} \(\cdots\) \texttt{unzip7}.

\subsection{Local Definitions}\label{local-definitions}

The \texttt{let} expression is useful whenever a nested set of
definitions is required. It has the following syntax:

\begin{quote}
\texttt{let} \emph{local\_definitions} \texttt{in} \emph{expression}
\end{quote}

A \texttt{let} may be used anywhere that an expression my appear in a
Haskell program.

For example, consider a function \texttt{f} that takes a list of
integers and returns a list of their squares incremented by one:

\begin{verbatim}
    f :: [Int] -> [Int]
    f [] = []
    f xs = let square a = a * a 
               one      = 1 
               (y:ys)   = xs 
           in (square y + one) : f ys 
\end{verbatim}

\begin{itemize}
\item
  \texttt{square} represents a function of one variable.
\item
  \texttt{one} represents a constant, that is, a function of zero
  variables.
\item
  \texttt{(y:ys)} represents a pattern match binding against argument
  \texttt{xs} of \texttt{f}.
\item
  Reference to \texttt{y} or \texttt{ys} when argument \texttt{xs} of
  \texttt{f} is nil results in an error.
\item
  Local definitions \texttt{square}, \texttt{one}, \texttt{y}, and
  \texttt{ys} all come into scope simultaneously; their scope is the
  expression following the \texttt{in} keyword.
\item
  Local definitions may access identifiers in outer scopes (e.g.,
  \texttt{xs} in definition of \texttt{(y:ys)}) and have definitions
  nested within themselves.
\item
  Local definitions may be recursive and call each other.
\end{itemize}

The \texttt{let} clause introduces symbols in a bottom-up manner: it
introduces symbols before they are used.

The \texttt{where} clause is similar semantically, but it introduces
symbols in a top-down manner: the symbols are used and then defined in a
\texttt{where} that follows.

The \texttt{where} clause is more versatile than the \texttt{let}. It
allows the scope of local definitions to span over several guarded
equations while a \texttt{let}'s scope is restricted to the right-hand
side of one equation.

For example, consider the definition:

\begin{verbatim}
    g :: Int -> Int
    g n | check3 == x = x
        | check3 == y = y
        | check3 == z = z * z
                      where check3 = n `mod` 3
                            x = 0
                            y = 1
                            z = 2
                            
\end{verbatim}

\begin{itemize}
\item
  The scope of this \texttt{where} clause is over \emph{all three
  guards} and their respective right-hand sides. (Note that the
  \texttt{where} begins in the same column as the \texttt{=} rather than
  to the right as in \texttt{rev’}.)
\item
  Note the use of the modulo function \texttt{mod} as an infix operator.
  The backquotes (\texttt{‘}) around a function name denotes the infix
  use of the function.
\end{itemize}

In addition to making definitions easier to understand, local
definitions can increase execution efficiency in some cases. A local
definition may introduce a component into the expression graph that is
shared among multiple branches. Haskell uses graph reduction, so any
shared component is evaluated once and then replaced by its value for
subsequent accesses.

The local variable \texttt{check3} introduces a component shared among
all three legs. It is evaluated once for each call of \texttt{g}.

\subsection{Insertion Sort}\label{insertion-sort}

Consider a function to sort the elements of a list into ascending order.

A list is \emph{ascending} if every element is \texttt{\textless{}=} all
of its successors in the list. Successor means an element that occurs
later in the list (i.e., away from the head). A list is
\emph{increasing} if every element is \texttt{\textless{}} its
successors. Similarly, a list is \emph{descending} or \emph{decreasing}
if every element is \texttt{\textgreater{}=} or \texttt{\textgreater{}},
respectively, its successors.

A simple algorithm to do this is \emph{insertion sort}. To sort a
non-empty list with head \texttt{x} and tail \texttt{xs}, sort the tail
\texttt{xs} and then insert the element \texttt{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
Haskell functions:

\begin{verbatim}
    isort :: [Int] -> [Int]
    isort []     = []
    isort (x:xs) = insert x (isort xs)  

    insert :: Int -> [Int] -> [Int]
    insert x []     = [x]
    insert x xs@(y:ys)  
        | x <= y    = (x:xs)  
        | otherwise = 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. Not all Haskell types can be
compared on a \emph{total ordering} (\texttt{\textless{}},
\texttt{\textless{}=}, \texttt{\textgreater{}}, and
\texttt{\textgreater{}=} as well).

We need to constrain the polymorphism to types in class \texttt{Ord}, as
follows:

\begin{verbatim}
    isort' :: Ord a => [a] -> [a]
    isort' []     = []
    isort' (x:xs) = insert' x (isort' xs)

    insert' :: Ord a => a -> [a] -> [a]
    insert' x []    = [x]
    insert' x xs@(y:ys)
        | x <= y    = (x:xs)
        | otherwise = y : (insert' x ys)
\end{verbatim}

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

Consider the following questions:

\begin{itemize}
\tightlist
\item
  How do we know \texttt{insert\textquotesingle{}} terminates?
\item
  What are the time and space complexities of
  \texttt{insert\textquotesingle{}}?
\item
  How do we know \texttt{isort\textquotesingle{}} terminates?
\item
  What are the time and space complexities of
  \texttt{isort\textquotesingle{}}?
\end{itemize}

\subsection{Exercises}\label{exercises}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Write a Haskell function to compute the maximum value in a nonempty
  list of integers. Generalize the function by making it polymorphic,
  accepting a value from any ordered type.
\item
  Write a Haskell function \texttt{adjpairs} that takes a list and
  returns the list of all pairs of adjacent elements. For example,
  \texttt{adjpairs\ {[}2,1,11,4{]}} returns
  \texttt{{[}(2,1),\ (1,11),\ (11,4){]}}.
\item
  Write a Haskell function \texttt{mean} that takes a list of integers
  and returns the mean (i.e., average) value for the list.
\item
  Write tail recursive versions of the Haskell functions
  \texttt{sum\textquotesingle{}} and \texttt{product\textquotesingle{}}.
\item
  Answer the following questions for the \texttt{take\textquotesingle{}}
  function defined in this chapter:

  \begin{itemize}
  \tightlist
  \item
    What is returned when the list argument is nil?
  \item
    Does evaluation of the function terminate?
  \item
    Does the result share data with the input?
  \item
    Is the function tail recursive?
  \item
    What are its time and space complexities?
  \end{itemize}
\item
  Answer the following question for the \texttt{++} operator developed
  in this chapter.

  \begin{itemize}
  \tightlist
  \item
    Is \texttt{++} tail recursive?
  \item
    What is the space complexity of \texttt{++}?
  \end{itemize}
\item
  Answer the following questions concerning the element selection
  operator defined in this chapter.

  \begin{itemize}
  \tightlist
  \item
    What is the precondition for element selection?
  \item
    Does evaluation terminate?
  \item
    Is the operator tail recursive?
  \item
    Does the result share any data with the input list?
  \item
    What are its time and space complexities?
  \end{itemize}
\item
  Write a version of function \texttt{splitAt\textquotesingle{}} that
  makes only one pass over the input list (that is, does not call
  \texttt{take\textquotesingle{}} and \texttt{drop\textquotesingle{}}).
\item
  Answer the following questions for the
  \texttt{isort\textquotesingle{}} and \texttt{insert\textquotesingle{}}
  functions.

  \begin{itemize}
  \tightlist
  \item
    How do we know \texttt{insert\textquotesingle{}} terminates?
  \item
    What are the time and space complexities of
    \texttt{insert\textquotesingle{}}?
  \item
    How do we know \texttt{isort\textquotesingle{}} terminates?
  \item
    What are the time and space complexities of
    \texttt{isort\textquotesingle{}}?
  \end{itemize}
\item
  Hailstone functions.

  \begin{enumerate}
  \def\labelenumii{\alph{enumii}.}
  \item
    (This part is repeated from a previous chapter.) Develop a function
    \texttt{hailstone} to implement the following function:

    \begin{longtable}[]{@{}llll@{}}
    \toprule
    \(hailstone(n)\) & \(=\) & \(1\), & if \(n = 1\)\tabularnewline
    \(hailstone(n)\) & \(=\) & \(hailstone(n/2)\), & if \(n > 1\), even
    \(n\)\tabularnewline
    \(hailstone(n)\) & \(=\) & \(hailstone(3*n+1)\), & if \(n > 1\), odd
    \(n\)\tabularnewline
    \bottomrule
    \end{longtable}

    Note that an application of the \texttt{hailstone} function to the
    argument \texttt{3} would result in the following ``sequence'' of
    ``calls'' and would ultimately return the result \texttt{1}.

\begin{verbatim}
    hailstone 3
      hailstone 10
        hailstone 5
          hailstone 16
            hailstone 8
              hailstone 4
                hailstone 2
                  hailstone 1
\end{verbatim}

    For further thought: What is the domain of the \emph{hailstone}
    function?

    \begin{enumerate}
    \def\labelenumiii{\alph{enumiii}.}
    \setcounter{enumiii}{1}
    \item
      Write a Haskell function that computes the results of the
      \texttt{hailstone} function for each element of a list of positive
      integers. The value returned by the \texttt{hailstone} function
      for each element of the list should be displayed.
    \item
      Modify the \texttt{hailstone} function to return the function's
      ``path.'' That is, each application of this path function should
      return a list of integers instead of a single integer. The list
      returned should consist of the arguments of the successive calls
      to the \texttt{hailstone} function necessary to compute the
      result. For example, the \texttt{hailstone\ 3} example above
      should return \texttt{{[}3,10,5,16,8,4,2,1{]}}.
    \end{enumerate}
  \end{enumerate}
\item
  Number base conversion.

  \begin{enumerate}
  \def\labelenumii{\alph{enumii}.}
  \item
    Write a Haskell function \texttt{natToBin} that takes a natural
    number and returns its binary representation as a list of
    \texttt{0}'s and \texttt{1}'s with the most significant digit at the
    head. For example, \texttt{natToBin\ 23} returns
    \texttt{{[}1,0,1,1,1{]}}. (Note: Prelude function \texttt{rem}
    returns the remainder from dividing its first argument by its
    second. Enclosing the function name in backquotes as in
    \texttt{‘rem‘} allows a two-argument function to be applied in an
    infix form.)
  \item
    Generalize \texttt{natToBin} to function \texttt{natToBase} that
    takes a base \texttt{b} (\texttt{b\ \textbackslash{}geq\ 2}) and a
    natural number and returns the base \texttt{b} representation of the
    natural number as a list of integer digits with the most significant
    digit at the head. For example, \texttt{natToBase\ 5\ 42} returns
    \texttt{{[}1,3,2{]}}.
  \item
    Write Haskell function \texttt{baseToNat}, the inverse of the
    \texttt{natToBase} function. For any base \texttt{b}
    (\texttt{b\ \textbackslash{}geq\ 2}) and natural number \texttt{n}:

\begin{verbatim}
    baseToNat b (natToBase b n) = n
\end{verbatim}
  \end{enumerate}
\item
  Write a Haskell function \texttt{merge} that takes two increasing
  lists of integers and merges them into a single increasing list
  (without any duplicate values). A list is \emph{increasing} if every
  element is less than (\texttt{\textless{}}) its successors. Successor
  means an element that occurs later in the list, i.e., away from the
  head. Generalize the function by making it polymorphic.
\item
  Design a module of set operations. Choose a Haskell representation for
  sets. Implement functions to make sets from lists and vice versa, to
  insert and delete elements from sets, to do set union, intersection,
  and difference, to test for equality and subset relationships, to
  determine cardinality, and so forth.
\item
  Bag module.

  Mathematically, a \emph{bag} (or \emph{multiset}) is a function from
  some arbitrary set of elements (the domain) to the set of nonnegative
  integers (the range). We interpret the nonnegative integer as the
  number of occurrences of the element in the bag. Zero means the
  element does not occur.

  From another perspective, a bag is an unordered collection of
  elements. Each element may occur one or more times in the bag. (It is
  like a set except values can occur multiple times.)

  For example,
  \texttt{\{\textbar{}\ "time\textquotesingle{},\ "time",\ "and",\ "time",\ "again"\ \textbar{}\}}
  is a bag containing 5 strings. There are 3 occurrences of string
  \texttt{"time"} and 1 occurrence each of strings \texttt{"and"} and
  \texttt{"again"}.

  \texttt{\{\textbar{}\ 11,\ 2,\ 3,\ 7,\ 5\ \textbar{}\}} is a bag of
  prime numbers. It is also a set because each element occurs exactly
  once.

  We can represent a bag in many ways in Haskell. Using lists, we could
  represent a bag with a simple (unordered) list of elements, an ordered
  list of elements, an unordered or an ordered list of tuples which pair
  an element with the (nonzero) number of times it occurs, etc. A bag
  could also be represented with other data structures such as a
  \texttt{Map} from library \texttt{Data.Map}.

  Choose some representation for polymorphic bags. You may assume that
  the elements in the domain are totally ordered (i.e., are from a type
  that is an instance of class \texttt{Ord}), but otherwise the elements
  can be of any type.

  For example, if you use a list representation, you might define the
  type synonym:

\begin{Shaded}
\begin{Highlighting}[]
\KeywordTok{type} \DataTypeTok{Bag}\NormalTok{ a }\FunctionTok{=}\NormalTok{ [a]}
\end{Highlighting}
\end{Shaded}

  Develop a data abstraction (information-hiding) module that
  encapsulates the representation of the data structure used to store
  the elements inside the module.

  The module should include the following public functions. This
  interface should be the same even if you change the representation of
  the data internally.

  \begin{enumerate}
  \def\labelenumii{\alph{enumii}.}
  \item
    \texttt{newBag} returns a new bag with no elements (i.e., empty).
  \item
    \texttt{listToBag} takes a list of elements and returns a bag
    containing exactly those elements. The number of occurrences of an
    element in the list and in the resulting bag is the same.
  \item
    \texttt{bagToList} takes a bag and returns a list containing exactly
    the elements occurring in the bag. The number of occurrences of an
    element in the bag and in the resulting list is the same.

    Note: It is not required that
    \texttt{bagToList\ (listToBag\ xs)\ ==\ xs}. But it is required that
    both sides have the same numbers of the same elements.
  \item
    \texttt{isEmpty} takes a bag and returns \texttt{True} if the bag
    has no elements and returns \texttt{False} otherwise.
  \item
    \texttt{isElem} takes an element and a bag and returns \texttt{True}
    if the element occurs in the bag and returns \texttt{False}
    otherwise.
  \item
    \texttt{size} takes a bag and returns its cardinality (i.e., the
    total number of occurrences of all elements).
  \item
    \texttt{occursBag} takes an element and a bag and returns the number
    of occurrences of the element in the bag.
  \item
    \texttt{insertElem} takes an element and a bag and returns the bag
    with the element inserted. Bag insertion either adds a single
    occurrence of a new element to the bag or increases the number of
    occurrences of an existing element by one.
  \item
    \texttt{deleteElem} takes an element and a bag and returns the bag
    with the element deleted. Bag deletion removes a single occurrence
    of an element from the bag, decreases the number of occurrences of
    an existing element by one, or does not change the bag if the
    element does not occur.
  \item
    \texttt{eqBag} takes two bags and returns \texttt{True} if the two
    bags are equal (i.e., the same elements and same number of
    occurrences of each) and returns \texttt{False} otherwise.

    Note: If \texttt{bagToList\ xs\ ==\ bagToList\ ys}, then
    \texttt{eqBag\ xs\ ys}. However, if \texttt{eqBag\ xs\ ys}, it is
    not required that \texttt{bagToList\ xs\ ==\ bagToList\ ys}.
  \item
    \texttt{unionBag} takes two bags and returns their bag union. The
    union of bags X and Y contains all elements that occur in either X
    or Y; the number of occurrences of an element in the union is the
    number in X or in Y, whichever is greater.
  \item
    \texttt{intersectBag} takes two bags and returns their bag
    intersection. The intersection of bags X and Y contains all elements
    that occur in both X and Y; the number of occurrences of an element
    in the intersection is the number in X or in Y, whichever is lesser.
  \item
    \texttt{sumBag} takes two bags and returns their bag sum. The sum of
    bags X and Y contains all elements that occur in X or Y; the number
    of occurrences of an element is the sum of the number of occurrences
    in X and Y.
  \item
    \texttt{diffBag} takes two bags and returns the bag difference,
    first argument minus the second. The difference of bags X and Y
    contains all elements of X that occur in Y fewer times; the number
    of occurrences of an element in the difference is the number of
    occurrences in X minus the number in Y.
  \item
    \texttt{subBag} takes two bags and returns \texttt{True} if the
    first is a subbag of the second and \texttt{False} otherwise. X is a
    subbag of Y if every element of X occurs in Y at least as many times
    as it does in X.
  \item
    \texttt{bagToSet} takes a bag and returns a list containing exactly
    the \emph{set} of elements contained in the bag. Each element
    occurring one or more times in the bag will occur exactly once in
    the list returned.
  \end{enumerate}
\item
  Develop a bag module as described in the previous exercise, but use a
  different internal representation than you used in the previous
  exercise. The new module should have the same public interface as the
  previous module.
\item
  Unbounded precision arithmetic module for natural numbers (i.e.,
  nonnegative integers). Do not use the builtin \texttt{Integer} type.

  \begin{enumerate}
  \def\labelenumii{\alph{enumii}.}
  \item
    Define a type synonym \texttt{BigNat} to represent these unbounded
    precision natural numbers as lists of \texttt{Int}. Let each element
    of the list denote a decimal digit of the ``big natural'' number
    represented, with the \emph{least} significant digit at the head of
    the list and the remaining digits given in order of
    \emph{increasing} significance. For example, the integer value
    22345678901 is represented as \texttt{{[}1,0,9,8,7,6,5,4,3,2,2{]}}.
    Use the following ``canonical'' representation: the value \texttt{0}
    is represented by the list \texttt{{[}0{]}} and positive numbers by
    a list without ``leading'' \texttt{0} digits (i.e., \texttt{126} is
    \texttt{{[}6,2,1{]}} not \texttt{{[}6,2,1,0,0{]}}). You may use the
    nil list \texttt{{[}\ {]}} to denote an error value.

    Define a Haskell module with basic arithmetic operations, including
    the following functions. Make sure that \texttt{BigNat} values
    returned by these functions are in canonical form.

    \begin{itemize}
    \item
      \texttt{intToBig} takes a nonnegative \texttt{Int} and returns the
      \texttt{BigNat} with the same value.
    \item
      \texttt{strToBig} takes a \texttt{String} containing the value of
      the number in the ``usual'' format (i.e., decimal digits, left to
      right in order of \emph{decreasing} significance with zero or more
      leading spaces, but with no spaces or punctuation embedded within
      the number) and returns the \texttt{BigNat} with the same value.
    \item
      \texttt{bigToStr} takes a \texttt{BigNat} and returns a
      \texttt{String} containing the value of the number in the
      ``usual'' format (i.e., left to right in order of
      \emph{decreasing} significance with no spaces or punctuation).
    \item
      \texttt{bigComp} takes two \texttt{BigNat}s and returns the
      \texttt{Int} value \texttt{-1} if the value of the first is less
      than the value of the second, the value \texttt{0} if they are
      equal, and the value \texttt{1} if the first is greater than the
      second.
    \item
      \texttt{bigAdd} takes two \texttt{BigNat}s and returns their sum
      as a \texttt{BigNat}.
    \item
      \texttt{bigSub} takes two \texttt{BigNat}s and returns their
      difference as a \texttt{BigNat}, first argument minus the second.
    \item
      \texttt{bigMult} takes two \texttt{BigNat}s and returns their
      product as a \texttt{BigNat}.
    \end{itemize}
  \item
    Use the package to generate a table of factorials for the naturals 0
    through 25. Print the values from the table in two
    \emph{right-justified} columns, with the number on the left and its
    factorial on the right. (Allow about 30 columns for \texttt{25!}.)
  \item
    Use the package to generate a table of Fibonacci numbers for the
    naturals 0 through 50.
  \item
    Generalize the package to handle signed integers. Add the following
    new function:

    \begin{itemize}
    \tightlist
    \item
      \texttt{bigNeg} returns the negation of its \texttt{BigNat}
      argument.
    \end{itemize}
  \item
    Add the following functions to the package:

    \begin{itemize}
    \item
      \texttt{bigDiv} takes two \texttt{BigNat}s and returns, as a
      \texttt{BigNat}, the quotient from dividing the first argument by
      the second.
    \item
      \texttt{bigRem} takes two \texttt{BigNat}s and returns, as a
      \texttt{BigNat}, the remainder from dividing the first argument by
      the second.
    \end{itemize}
  \end{enumerate}
\item
  Define the following set of text-justification functions. You may want
  to use Prelude functions like \texttt{take}, \texttt{drop}, and
  \texttt{length}.

  \begin{itemize}
  \item
    \texttt{spaces’\ n} returns a string of length \texttt{n} containing
    only space characters (i.e., the character \texttt{’\ ’}).
  \item
    \texttt{left’\ n\ xs} returns a string of length \texttt{n} in which
    the string \texttt{xs} begins at the head (i.e., left end).

    Examples: \texttt{left’\ 3\ "ab"}
    yields\texttt{\textasciigrave{}"ab\ "}; \texttt{left’\ 3\ "abcd"}
    yields \texttt{"abc"}.
  \item
    \texttt{right’\ n\ xs} returns a string of length \texttt{n} in
    which the string \texttt{xs} ends at the tail (i.e., right end).

    Examples: \texttt{right’\ 3\ bc} yields \texttt{bc};
    \texttt{right’\ 3\ abcd} yields \texttt{bcd}.
  \item
    \texttt{center’\ n\ xs} returns a string of length \texttt{n} in
    which the string \texttt{xs} is approximately centered.

    Example: \texttt{center’\ 4\ "bc"} yields \texttt{"\ bc\ "}.
  \end{itemize}
\item
  Consider simple mathematical expressions consisting of integer
  constants, variable names, parentheses, and the binary operators
  \texttt{+}, \texttt{-}, \texttt{*}, and \texttt{/}. For the purposes
  of this exercise, an \emph{expression} is a string that satisfies the
  following (extended) BNF grammar and lexical conventions:

  \begin{itemize}
  \item
    The characters in an input string are examined left to right to form
    ``lexical tokens''. The tokens of the expression ``language''
    consist of \emph{addOp}s, \emph{mulOp}s,\emph{identifier}s,
    \emph{number}s, and left and right parentheses.
  \item
    An expression may contain space characters at any position except
    within a lexical token.
  \item
    An \emph{addOp} token is either a ``\texttt{+}'' or a
    ``\texttt{-}''; a \emph{mulOp} token is either a ``\texttt{*}'' or a
    ``\texttt{/}''.
  \item
    An \emph{identifier} \texttt{q} is a string of one or more
    contiguous characters such that the leftmost character is a letter
    and the remaining characters are either letters, digits, or
    underscore characters.

    Examples: ``\texttt{Hi1}'', ``\texttt{lo23\_1}'',
    ``\texttt{this\_is\_2\_long}''
  \item
    A \emph{number} is a string of one or more contiguous characters
    such that all (including the leftmost) are digits.

    Examples: ``\texttt{1}'', ``\texttt{23456711}''
  \item
    All \emph{identifier} and \emph{number} tokens extend as far to the
    right as possible. For example, consider the string
    ``\texttt{A123\ \ 12B3+2\ )}''. (Note the space and right
    parenthesis characters). This string consists of the six tokens
    ``\texttt{A123}'', ``\texttt{12}'', ``\texttt{B3}'', ``\texttt{+}'',
    ``\texttt{2}'', and ``\texttt{)}''.
  \end{itemize}

  Define a Haskell function \texttt{valid} that takes a \texttt{String}
  and returns \texttt{True} if the string is an \emph{expression} as
  described above and returns \texttt{False} otherwise.

  Hints:

  \begin{itemize}
  \item
    If you need to return more than one value from a function, you can
    do so by returning a tuple of those values. This tuple can be
    decomposed by Prelude functions such as \texttt{fst} and
    \texttt{snd}.
  \item
    Use of the \texttt{where} or \texttt{let} features can simplify many
    functions. You may find Prelude functions such as \texttt{span},
    \texttt{isSpace}, \texttt{isDigit}, \texttt{isAlpha}, and
    \texttt{isAlphanum} useful.
  \item
    You may want to consider organizing your program as a simple
    \emph{recursive descent} recognizer for the expression language.
  \end{itemize}
\item
  Extend the mathematical expression recognizer of the previous exercise
  to \emph{evaluate} integer expressions with the given syntax. The four
  binary operations have their usual meanings.

  Define a function \texttt{eval\ e\ st} that evaluates expression
  \texttt{e} using symbol table \texttt{st}. If the expression
  \texttt{e} is syntactically valid, \texttt{eval} returns a pair
  \texttt{(True,val)} where \texttt{val} is the value of \texttt{e}. If
  \texttt{e} is not valid, \texttt{eval} returns \texttt{(False,0)}.

  The symbol table consists of a list of pairs, in which the first
  component of a pair is the variable name (a string) and the second is
  the variable's value (an integer).

  Example: \texttt{eval\ "(2+x)\ *\ y"\ {[}("y",3),("a",10),("x",8){]}}
  yields \texttt{(True,30)}.
\end{enumerate}

\subsection{References}\label{references}

\begin{description}
\tightlist
\item[{[}Bird-Wadler 1998{]}]
Richard Bird and Philip Wadler. \emph{Introduction to Functional
Programming}, Second Edition, Addison Wesley, 1998.
{[}\href{https://usi-pl.github.io/lc/sp-2015/doc/Bird_Wadler.\%20Introduction\%20to\%20Functional\%20Programming.1ed.pdf}{First
Edition, 1988}{]}
\item[{[}Chiusano-Bjarnason 2015{]}{]}]
Paul Chiusano and Runar Bjarnason, \emph{Functional Programming in
Scala}, Manning, 2015.
\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}}, 1994-2014.
\item[{[}Thompson 2011{]}]
Simon Thompon. \emph{Haskell: The Craft of Programming, Third Edition},
Pearson, 2011.
\end{description}

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

Polymorphism (ad hoc, overloading, subtyping, parametric), lists
(polymorphic, immutable, persistent, data sharing, empty, nonempty),
list and string operations (cons, head, tail, pattern matching),
syntactic sugar, type synonym, type variable, follow the types to
implementations, let the form of the data guide the form of the
algorithm, infix operation, properties of operators (associative,
identity, zero, inverse, distribution), precedence (left, right, free
binding), context predicates (type classes \texttt{Eq}, \texttt{Ord}),
insertion sort

\end{document}
