\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 Algebraic Data Types},
            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{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\\
Algebraic Data Types}
\author{H. Conrad Cunningham}
\date{10 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 8 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 Fall 2017, I added the discussion of the \texttt{Maybe} and
\texttt{Either} types. For this work, I examined the \texttt{Data.Maybe}
and \texttt{Data.Either} documentation and the Wikipedia article on
``Option Type''.

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
October 2017 is a recent version of Firefox from Mozilla.

\textbf{Code}: The Haskell module for this chapter is in file
\href{code08/Chap08.hs}{\texttt{Chap08.hs}}.

TODO:

\begin{itemize}
\tightlist
\item
  add chapter goals and outcomes
\item
  convert and test functions from Scala
\item
  clean and add exercises
\item
  clean up and document associated module
\end{itemize}

\setcounter{section}{7}

\section{Algebraic Data Types}\label{algebraic-data-types}

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

TODO

\subsection{Definition}\label{definition}

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

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

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

\subsection{Haskell Algebraic Data
Types}\label{haskell-algebraic-data-types}

\subsubsection{\texorpdfstring{Declaring \texttt{data}
types}{Declaring data types}}\label{declaring-data-types}

In addition to the built-in data types we have discussed, Haskell also
allows the definition of new data types using declarations of the form:

\begin{quote}
\texttt{data} \textbf{Datatype} \textbf{a\emph{1} a\emph{2} \(\cdots\)
a\emph{n}} \texttt{=} \textbf{Constr\emph{1}} \texttt{\textbar{}}
\textbf{Constr\emph{2}} \texttt{\textbar{}} \(\cdots\)
\texttt{\textbar{}} \textbf{Constr\emph{m}}
\end{quote}

where:

\begin{itemize}
\item
  \textbf{Datatype} is the name of a new type constructor of
  \emph{arity} \textbf{\emph{n}} \emph{(n \(\geq\) 0)}. As with the
  built-in types, the name of the data type must begin with an uppercase
  letter.
\item
  \textbf{a\emph{1}}, \textbf{a\emph{2}}, \(\cdots\) \textbf{a\emph{n}}
  are distinct type variables representing the \textbf{\emph{n}}
  parameters of the data type. These begin with lowercase letters (by
  convention at the beginning of the alphabet).
\item
  \textbf{Constr\emph{1}}, \textbf{Constr\emph{2}}, \(\cdots\),
  \textbf{Constr\emph{m}} are the \textbf{\emph{m}} \emph{(m \(\geq\)
  1)} data constructors that describe the ways in which the elements of
  the new data type are constructed. These begin with uppercase letters.
\end{itemize}

\subsubsection{\texorpdfstring{Example type
\texttt{Color}}{Example type Color}}\label{example-type-color}

For example, consider a new data type \texttt{Color} whose possible
values are the colors on the flag of the USA. The names of the data
constructors (the color constants in this case) must also begin with
capital letters.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{data} \DataTypeTok{Color} \FunctionTok{=} \DataTypeTok{Red} \FunctionTok{|} \DataTypeTok{White} \FunctionTok{|} \DataTypeTok{Blue} 
                 \KeywordTok{deriving}\NormalTok{ (}\DataTypeTok{Show}\NormalTok{, }\DataTypeTok{Eq}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

\texttt{Color} is an example of an \emph{enumerated type}, a \emph{sum}
type that consists of a finite sequence of \emph{nullary} (i.e., the
arity---number of parameters---is zero) data constructors.

We can use the type and data constructor names defined with
\texttt{data} in declarations, patterns, and expressions in the same way
that the built-in types can be used.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    isRed ::} \DataTypeTok{Color} \OtherTok{->} \DataTypeTok{Bool} 
\NormalTok{    isRed }\DataTypeTok{Red} \FunctionTok{=} \DataTypeTok{True}
\NormalTok{    isRed _   }\FunctionTok{=} \DataTypeTok{False}
\end{Highlighting}
\end{Shaded}

Data constructors can also have associated values. For example, the
constructor \texttt{Grayscale} below takes an integer value.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{data} \DataTypeTok{Color'} \FunctionTok{=} \DataTypeTok{Red'} \FunctionTok{|} \DataTypeTok{Blue'} \FunctionTok{|} \DataTypeTok{Grayscale} \DataTypeTok{Int}
                  \KeywordTok{deriving}\NormalTok{ (}\DataTypeTok{Show}\NormalTok{, }\DataTypeTok{Eq}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

Constructor \texttt{Grayscale} implicitly defines a constructor function
with the type.

\subsubsection{Deriving class instances}\label{deriving-class-instances}

The optional \texttt{deriving} clauses above are very useful. They
declare that these new types are automatically added as instances of the
classes listed. In the above cases, \texttt{Show} and \texttt{Eq} enable
objects of type \texttt{Color} to be converted to a \texttt{String} and
compared for equality, respectively.

The Haskell compiler derives the body of an instance syntactically from
the data type declaration. It can derive instances for classes
\texttt{Eq}, \texttt{Ord}, \texttt{Enum}, \texttt{Bounded},
\texttt{Read}, and \texttt{Show}.

The derived instances of \texttt{Eq} include the \texttt{(==)} and
\texttt{(/=)} methods. The derived instances of \texttt{Ord} also
include the \texttt{compare}, \texttt{(\textless{})},
\texttt{(\textless{}=)}, \texttt{(\textgreater{})},
\texttt{(\textgreater{}=)}, \texttt{max}, and \texttt{min} methods. The
ordered comparison operators use the order of the constructors given in
the \texttt{data} statement, from smallest to largest, left to right.
These comparison operators are strict in both arguments.

Similarly, the \texttt{Enum} instance assigns integers to the
constructors increasing from 0 at the left;\texttt{Bounded} assigns
\texttt{minBound} to the leftmost and \texttt{maxBound} to the
rightmost.

\texttt{Show} enables the function \texttt{show} to convert the data
type to a syntactically correct Haskell expression consisting of only
the constructor names, parentheses, and spaces. Similarly, \texttt{Read}
enables the function \texttt{read} to parse such a string into a value
of the data type.

For example, the data type \texttt{Bool} might be defined as:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{data} \DataTypeTok{Bool} \FunctionTok{=} \DataTypeTok{False} \FunctionTok{|} \DataTypeTok{True}
                \KeywordTok{deriving}\NormalTok{ (}\DataTypeTok{Ord}\NormalTok{, }\DataTypeTok{Show}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

Thus \texttt{False\ \textless{}\ True} evaluates to \texttt{True} and
\texttt{False\ \textgreater{}\ True} evaluates to \texttt{False}. If
\texttt{x\ ==\ False}, then \texttt{show\ x} yields the string
\texttt{False}.

\subsubsection{More example types}\label{more-example-types}

Consider a data type \texttt{Point} that has a type parameter. The
following defines a polymorphic type; both of the values associated with
the constructor \texttt{Pt} must be of type \texttt{a}. Constructor
\texttt{Pt} implicitly defines a constructor function of type
\texttt{a\ -\textgreater{}\ a\ -\textgreater{}\ Point\ a}.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{data} \DataTypeTok{Point}\NormalTok{ a }\FunctionTok{=} \DataTypeTok{Pt}\NormalTok{ a a}
                   \KeywordTok{deriving}\NormalTok{ (}\DataTypeTok{Show}\NormalTok{, }\DataTypeTok{Eq}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

As another example, consider a polymorphic set data type that represents
a set as a list of values as follows. Note that the name \texttt{Set} is
used both as the type constructor and a data constructor. In general, do
not use a symbol in multiple ways. It is acceptable to double use only
when the type has only one constructor.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{data} \DataTypeTok{Set}\NormalTok{ a }\FunctionTok{=} \DataTypeTok{Set}\NormalTok{ [a]}
                 \KeywordTok{deriving}\NormalTok{ (}\DataTypeTok{Show}\NormalTok{, }\DataTypeTok{Eq}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

Now we can write a function \texttt{makeSet} to transform a list into a
\texttt{Set}. This function uses the function \texttt{nub} from the
\texttt{Data.List} module to remove duplicates from a list.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    makeSet ::} \DataTypeTok{Eq}\NormalTok{ a }\OtherTok{=>}\NormalTok{ [a] }\OtherTok{->} \DataTypeTok{Set}\NormalTok{ a }
\NormalTok{    makeSet xs }\FunctionTok{=} \DataTypeTok{Set}\NormalTok{ (nub xs)}
\end{Highlighting}
\end{Shaded}

As we have seen previously, programmers can also define type synonyms.
As in user-defined types, synonyms may have parameters. For example, the
following might define a matrix of some polymorphic type as a list of
lists of that type.

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

We can also use special types to encode error conditions. For example,
suppose we want an integer division operation that returns an error
message if there is an attempt to divide by 0 and returns the quotient
otherwise. We can define and use a union type \texttt{Result} as
follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{data} \DataTypeTok{Result}\NormalTok{ a }\FunctionTok{=} \DataTypeTok{Ok}\NormalTok{ a }\FunctionTok{|} \DataTypeTok{Err} \DataTypeTok{String}
                    \KeywordTok{deriving}\NormalTok{ (}\DataTypeTok{Show}\NormalTok{, }\DataTypeTok{Eq}\NormalTok{)}

\OtherTok{    divide ::} \DataTypeTok{Int} \OtherTok{->} \DataTypeTok{Int} \OtherTok{->} \DataTypeTok{Result} \DataTypeTok{Int} 
\NormalTok{    divide _  }\DecValTok{0} \FunctionTok{=} \DataTypeTok{Err} \StringTok{"Divide by zero"} 
\NormalTok{    divide x  y }\FunctionTok{=} \DataTypeTok{Ok}\NormalTok{ (x }\OtherTok{`div`}\NormalTok{ y)}
\end{Highlighting}
\end{Shaded}

Then we can use this operation in the definition of another function
\texttt{f} that returns the maximum \texttt{Int} value \texttt{maxBound}
when a division by 0 occurs.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    f ::} \DataTypeTok{Int} \OtherTok{->} \DataTypeTok{Int} \OtherTok{->} \DataTypeTok{Int} 
\NormalTok{    f x y  }\FunctionTok{=}\NormalTok{ return (divide x y) }
             \KeywordTok{where}\NormalTok{ return (}\DataTypeTok{Ok}\NormalTok{ z)  }\FunctionTok{=}\NormalTok{ z }
\NormalTok{                   return (}\DataTypeTok{Err}\NormalTok{ s) }\FunctionTok{=}\NormalTok{ maxBound}
\end{Highlighting}
\end{Shaded}

The auxiliary function \texttt{return} can be avoided by using the
Haskell \texttt{case} expression as follows:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    f' x y }\FunctionTok{=} 
        \KeywordTok{case}\NormalTok{ divide x y }\KeywordTok{of} 
            \DataTypeTok{Ok}\NormalTok{ z  }\OtherTok{->}\NormalTok{ z }
            \DataTypeTok{Err}\NormalTok{ s }\OtherTok{->}\NormalTok{ maxBound}
\end{Highlighting}
\end{Shaded}

This case expression evaluates the expression \texttt{divide\ x\ y},
matches its result against the patterns of the alternatives, and returns
the right-hand-side of the first matching patter.

Later in this chapter we discuss the \texttt{Maybe} and \texttt{Either}
types, two polymorphic types for handling errors defined in the Prelude.

\subsubsection{Recursive types}\label{recursive-types}

Types can also be recursive.

For example, consider the user-defined type \texttt{BinTree}, which
defines a binary tree with values of a polymorphic type.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{data} \DataTypeTok{BinTree}\NormalTok{ a }\FunctionTok{=} \DataTypeTok{Empty} \FunctionTok{|} \DataTypeTok{Node}\NormalTok{ (}\DataTypeTok{BinTree}\NormalTok{ a) a (}\DataTypeTok{BinTree}\NormalTok{ a)}
                     \KeywordTok{deriving}\NormalTok{ (}\DataTypeTok{Show}\NormalTok{, }\DataTypeTok{Eq}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

This data type represents a binary tree with a value in each node. The
tree is either ``emptyD'' (denoted by \texttt{Empty}) or it is a
``node'' (denoted by \texttt{Node}) that consists of a value of type
\texttt{a} and ``left'' and ``right'' subtrees. Each of the subtrees
must themselves be objects of type \texttt{BinTree}.

Thus a binary tree is represented as a three-part ``record'' in which
the left and right subtrees are represented as nested binary trees.
There are no explicit ``pointers''.

\begin{figure}
\centering
\includegraphics{fig_08_01.png}
\caption{\textbf{Figure 8-1: Binary Tree \texttt{BinTree}}}
\end{figure}

Consider a function \texttt{flatten} to return the list of the values in
binary tree in the order corresponding to a left-to-right in-order
traversal. Thus expression

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    flatten (}\DataTypeTok{Node}\NormalTok{ (}\DataTypeTok{Node} \DataTypeTok{Empty} \DecValTok{3} \DataTypeTok{Empty}\NormalTok{) }\DecValTok{5}\NormalTok{ (}\DataTypeTok{Node}\NormalTok{ (}\DataTypeTok{Node} \DataTypeTok{Empty} \DecValTok{7} \DataTypeTok{Empty}\NormalTok{) }\DecValTok{1} \DataTypeTok{Empty}\NormalTok{))}
\end{Highlighting}
\end{Shaded}

yields \texttt{{[}3,5,7,1{]}}.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    flatten ::} \DataTypeTok{BinTree}\NormalTok{ a }\OtherTok{->}\NormalTok{ [a] }
\NormalTok{    flatten }\DataTypeTok{Empty}        \FunctionTok{=}\NormalTok{ [] }
\NormalTok{    flatten (}\DataTypeTok{Node}\NormalTok{ l v r) }\FunctionTok{=}\NormalTok{ flatten l }\FunctionTok{++}\NormalTok{ [v] }\FunctionTok{++}\NormalTok{ flatten r }
\end{Highlighting}
\end{Shaded}

The second leg of \texttt{flatten} requires two recursive calls.
However, as long as the input tree is finite, each recursive call
receives a tree that is simpler (e.g., shorter) than the input. Thus all
recursions eventually terminate when \texttt{flatten} is called with an
\texttt{Empty} tree.

Function \texttt{flatten} can be rendered more efficiently using an
accumulating parameter and cons as in the following:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    flatten' ::} \DataTypeTok{BinTree}\NormalTok{ a }\OtherTok{->}\NormalTok{ [a] }
\NormalTok{    flatten' t }\FunctionTok{=}\NormalTok{ inorder t [] }
                 \KeywordTok{where}\NormalTok{ inorder }\DataTypeTok{Empty}\NormalTok{ xs        }\FunctionTok{=}\NormalTok{ xs }
\NormalTok{                       inorder (}\DataTypeTok{Node}\NormalTok{ l v r) xs }\FunctionTok{=} 
\NormalTok{                           inorder l (v }\FunctionTok{:}\NormalTok{ inorder r xs)}
\end{Highlighting}
\end{Shaded}

Auxiliary function \texttt{inorder} builds up the list of values from
the right using cons.

To extend the example further, consider a function \texttt{treeFold}
that folds an associative operation \texttt{op} with identity element
\texttt{i} through a left-to-right in-order traversal of the tree.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    treeFold ::}\NormalTok{ (a }\OtherTok{->}\NormalTok{ a }\OtherTok{->}\NormalTok{ a) }\OtherTok{->}\NormalTok{ a }\OtherTok{->} \DataTypeTok{BinTree}\NormalTok{ a }\OtherTok{->}\NormalTok{ a }
\NormalTok{    treeFold op i }\DataTypeTok{Empty}        \FunctionTok{=}\NormalTok{ i }
\NormalTok{    treeFold op i (}\DataTypeTok{Node}\NormalTok{ l v r) }\FunctionTok{=}\NormalTok{ op (op (treeFold op i l) v) }
\NormalTok{                                    (treeFold op i r)}
\end{Highlighting}
\end{Shaded}

Now let's consider a slightly different formulation of a binary tree: a
tree in which values are only stored at the leaves.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{data} \DataTypeTok{Tree}\NormalTok{ a }\FunctionTok{=} \DataTypeTok{Leaf}\NormalTok{ a }\FunctionTok{|} \DataTypeTok{Tree}\NormalTok{ a }\FunctionTok{:^:} \DataTypeTok{Tree}\NormalTok{ a}
                  \KeywordTok{deriving}\NormalTok{ (}\DataTypeTok{Show}\NormalTok{, }\DataTypeTok{Eq}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

This definition introduces the constructor function name \texttt{Leaf}
as the constructor for leaves and the infix construction operator
``\texttt{:\^{}:}'' as the constructor for internal nodes of the tree.
(A constructor operator symbol must begin with a colon.)

These constructors allow such trees to be defined conveniently. For
example, the tree

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    ((}\DataTypeTok{Leaf} \DecValTok{1} \FunctionTok{:^:} \DataTypeTok{Leaf} \DecValTok{2}\NormalTok{) }\FunctionTok{:^:}\NormalTok{ (}\DataTypeTok{Leaf} \DecValTok{3} \FunctionTok{:^:} \DataTypeTok{Leaf} \DecValTok{4}\NormalTok{))}
\end{Highlighting}
\end{Shaded}

generates a complete binary tree with height 3 and the integers 1, 2, 3,
and 4 at the leaves.

Suppose we want a function \texttt{fringe}, similar to function
\texttt{flatten} above, that displays the leaves in a left-to-right
order. We can write this as:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    fringe ::} \DataTypeTok{Tree}\NormalTok{ a }\OtherTok{->}\NormalTok{ [a]  }
\NormalTok{    fringe (}\DataTypeTok{Leaf}\NormalTok{ v)  }\FunctionTok{=}\NormalTok{ [v] }
\NormalTok{    fringe (l }\FunctionTok{:^:}\NormalTok{ r) }\FunctionTok{=}\NormalTok{ fringe l }\FunctionTok{++}\NormalTok{ fringe r }
\end{Highlighting}
\end{Shaded}

As with \texttt{flatten} and \texttt{flatten’} above, function
\texttt{fringe} can also be rendered more efficiently using an
accumulating parameter as in the following:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    fringe' ::} \DataTypeTok{Tree}\NormalTok{ a }\OtherTok{->}\NormalTok{ [a] }
\NormalTok{    fringe' t }\FunctionTok{=}\NormalTok{ leaves t [] }
                \KeywordTok{where}\NormalTok{ leaves (}\DataTypeTok{Leaf}\NormalTok{ v)  }\FunctionTok{=}\NormalTok{ ((}\FunctionTok{:}\NormalTok{) v) }
\NormalTok{                      leaves (l }\FunctionTok{:^:}\NormalTok{ r) }\FunctionTok{=}\NormalTok{ leaves l }\FunctionTok{.}\NormalTok{ leaves r}
\end{Highlighting}
\end{Shaded}

Auxiliary function \texttt{leaves} builds up the list of leaves from the
right using cons.

\subsection{\texorpdfstring{Error-handling with \texttt{Maybe} and
\texttt{Either}}{Error-handling with Maybe and Either}}\label{error-handling-with-maybe-and-either}

Before we examine \texttt{Maybe} and \texttt{Either}, let's consider a
use case.

An \emph{association list} is a list of pairs in which the first
component is some \emph{key} (e.g., a string) and the second component
is the \emph{value} associated with that key. It is a simple form of a
\emph{map} or \emph{dictionary} data structure.

Suppose we have an association list that maps the name of a student (a
key) to the name of the student's academic advisor (a value). The
following function \texttt{lookup\textquotesingle{}} carries out the
search recursively.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    lookup' ::} \DataTypeTok{String} \OtherTok{->}\NormalTok{ [(}\DataTypeTok{String}\NormalTok{,}\DataTypeTok{String}\NormalTok{)] }\OtherTok{->} \DataTypeTok{String}
\NormalTok{    lookup' key ((x,y)}\FunctionTok{:}\NormalTok{xys)}
        \FunctionTok{|}\NormalTok{ key }\FunctionTok{==}\NormalTok{ x  }\FunctionTok{=}\NormalTok{  y}
        \FunctionTok{|}\NormalTok{ otherwise }\FunctionTok{=}\NormalTok{  lookup' key xys}
\end{Highlighting}
\end{Shaded}

But what do we do when the key is not in the list (e.g., the list is
empty)? How do we define a leg for
\texttt{lookup\textquotesingle{}\ key\ {[}{]}} ?

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Leave the function undefined for that pattern?

  In this case, evaluation will halt with a ``non-exhaustive pattern''
  error message.
\item
  Put in an explicit \texttt{error} call with a custom error message?
\item
  Return some default value of the advisor such as \texttt{"NONE"}?
\item
  Return a \emph{null reference}?
\end{enumerate}

The first two approaches either halt the entire program or require use
of the exception-handling mechanism. However, in any language, both
abnormal termination and exceptions should be avoided except in cases in
which the program is unable to continue. The lack of an assignment of a
student to an advisor is likely not such an extraordinary situation.

Exceptions break referential transparency and, hence, negate many of the
advantages of purely functional languages such as Haskell. In addition,
Haskell programs can only catch exceptions in the outer layers that
handle input/output.

The third approach only works when there is some value that is not
valid. This is not a very general approach.

The fourth approach, which is not available in Haskell, can be an
especially unsafe programming practice. British computing scientist Tony
Hoare, who introduced the null reference into the Algol type system in
the mid-1960s, calls that his ``billion dollar mistake'' because it
``has led to innumerable errors, vulnerabilities, and system crashes''.

What is a safer, more general approach than these?

Haskell includes the union type \texttt{Maybe} (from the Prelude and
\texttt{Data.Maybe}) which can be used to handle such cases.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{data} \DataTypeTok{Maybe}\NormalTok{ a }\FunctionTok{=} \DataTypeTok{Nothing} \FunctionTok{|} \DataTypeTok{Just}\NormalTok{ a}
                   \KeywordTok{deriving}\NormalTok{ (}\DataTypeTok{Eq}\NormalTok{, }\DataTypeTok{Ord}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

The \texttt{Maybe} algebraic data type encapsulates an optional value. A
value of type \texttt{Maybe\ a} either contains a value of type
\texttt{a} (represented by \texttt{Just\ a}) or it is empty (represented
by \texttt{Nothing}).

The\texttt{Maybe} type is a good way to handle errors or exceptional
cases without resorting to an \texttt{error} call.

Now we can define a general version of \texttt{lookup\textquotesingle{}}
using a \texttt{Maybe} return type. (This is essentially function
\texttt{lookup} from the Prelude.)

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    lookup'' ::}\NormalTok{ (}\DataTypeTok{Eq}\NormalTok{ a) }\OtherTok{=>}\NormalTok{ a }\OtherTok{->}\NormalTok{ [(a,b)] }\OtherTok{->} \DataTypeTok{Maybe}\NormalTok{ b}
\NormalTok{    lookup'' key [] }\FunctionTok{=}  \DataTypeTok{Nothing}
\NormalTok{    lookup'' key ((x,y)}\FunctionTok{:}\NormalTok{xys)}
       \FunctionTok{|}\NormalTok{ key }\FunctionTok{==}\NormalTok{ x   }\FunctionTok{=}  \DataTypeTok{Just}\NormalTok{ y}
       \FunctionTok{|}\NormalTok{ otherwise  }\FunctionTok{=}\NormalTok{  lookup'' key xys}
\end{Highlighting}
\end{Shaded}

Suppose \texttt{advisorList} is an association list pairing students
with their advisors and \texttt{defaultAdvisor} is the advisor the
student should consult if no advisor is officially assigned. We can look
up the advisor with a call to \texttt{lookup} and then pattern match on
the \texttt{Maybe} value returned. (Here we use a \texttt{case}
expression.)

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    whoIsAdvisor ::} \DataTypeTok{String} \OtherTok{->} \DataTypeTok{String}
\NormalTok{    whoIsAdvisor std }\FunctionTok{=}
        \KeywordTok{case}\NormalTok{ lookup std advisorList }\KeywordTok{of}
            \DataTypeTok{Nothing}   \OtherTok{->}\NormalTok{ defaultAdvisor}
            \DataTypeTok{Just}\NormalTok{ prof }\OtherTok{->}\NormalTok{ prof}
\end{Highlighting}
\end{Shaded}

The \texttt{whoIsAdvisor} function just returns a default value in place
of \texttt{Nothing}. The function

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    fromMaybe ::}\NormalTok{ a }\OtherTok{->} \DataTypeTok{Maybe}\NormalTok{ a }\OtherTok{->}\NormalTok{ a}
\end{Highlighting}
\end{Shaded}

supported by the \texttt{Data.Maybe} library has the same effect. Thus
we can rewrite \texttt{whoIsAdvisor} as follows:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    whoIsAdvisor' std }\FunctionTok{=} 
\NormalTok{        fromMaybe defaultAdvisor }\FunctionTok{$}\NormalTok{ lookup std advisorList }
\end{Highlighting}
\end{Shaded}

Alternatively, we could use \texttt{Data.Maybe} functions such as:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    isJust    ::} \DataTypeTok{Maybe}\NormalTok{ a }\OtherTok{->} \DataTypeTok{Bool}
\OtherTok{    isNothing ::} \DataTypeTok{Maybe}\NormalTok{ a }\OtherTok{->} \DataTypeTok{Bool}
\OtherTok{    fromJust  ::} \DataTypeTok{Maybe}\NormalTok{ a }\OtherTok{->}\NormalTok{ a   }\CommentTok{-- error if Nothing}
\end{Highlighting}
\end{Shaded}

This allows us to rewrite \texttt{whoIsAdvisor} as follows:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    whoIsAdvisor'' std }\FunctionTok{=}
        \KeywordTok{let}\NormalTok{ ad }\FunctionTok{=}\NormalTok{ lookup std advisorList}
        \KeywordTok{in} \KeywordTok{if}\NormalTok{ isJust ad }\KeywordTok{then}\NormalTok{ fromJust ad }\KeywordTok{else}\NormalTok{ defaultAdvisor}
\end{Highlighting}
\end{Shaded}

If we need more fine-grained error messages, then we can use the union
type \texttt{Either} defined as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{data} \DataTypeTok{Either}\NormalTok{ a b }\FunctionTok{=} \DataTypeTok{Left}\NormalTok{ a }\FunctionTok{|} \DataTypeTok{Right}\NormalTok{ b}
                      \KeywordTok{deriving}\NormalTok{ (}\DataTypeTok{Eq}\NormalTok{, }\DataTypeTok{Ord}\NormalTok{, }\DataTypeTok{Read}\NormalTok{, }\DataTypeTok{Show}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

The \texttt{Either\ a\ b} type represents values with two possibilities:
a \texttt{Left\ a} or \texttt{Right\ b}. By convention, a \texttt{Left}
constructor usually contains an error message and a \texttt{Right}
constructor a \emph{correct} value.

As with \texttt{fromMaybe}, we can use similar \texttt{fromRight} and
\texttt{fromLeft} functions from the \texttt{Data.Either}library to
extract the \texttt{Right} or \texttt{Left} values or to return a
default value when the value is represented by the other constructor.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    fromLeft  ::}\NormalTok{ a }\OtherTok{->} \DataTypeTok{Either}\NormalTok{ a b }\OtherTok{->}\NormalTok{ a}
\OtherTok{    fromRight ::}\NormalTok{ b }\OtherTok{->} \DataTypeTok{Either}\NormalTok{ a b }\OtherTok{->}\NormalTok{ b}
\end{Highlighting}
\end{Shaded}

Library module \texttt{Data.Either} also includes functions to query for
the presence of the two constructors.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    isLeft    ::} \DataTypeTok{Either}\NormalTok{ a b }\OtherTok{->} \DataTypeTok{Bool}
\OtherTok{    isRight   ::} \DataTypeTok{Either}\NormalTok{ a b }\OtherTok{->} \DataTypeTok{Bool}
\end{Highlighting}
\end{Shaded}

Most recently designed languages include a maybe or option type. For
example, Java 8 added the final class
\texttt{Optional\textless{}T\textgreater{}}. Scala supports the
\texttt{Option{[}T{]}} case class hierarchy, and Rust includes the
\texttt{Option\textless{}T\textgreater{}} enum (algebraic data type).
The functional languages Idris, Elm, and PureScript all have
Haskell-like \texttt{Maybe} algebraic data types.

When programming in an object-oriented language that does not provide an
option/maybe type, a programmer can often use the
\href{https://en.wikipedia.org/wiki/Null_object_pattern}{Null Object}
design pattern to achieve a similar result. Instead of returning a null
reference to denote the absence of a valid result, the function can
return an object that implements the expected interface but which ``does
nothing'' -- at least nothing harmful.

\subsection{Exercises}\label{exercises}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  For trees of type \texttt{Tree}, implement a tree-folding function
  similar to \texttt{treeFold}.
\item
  For trees of type \texttt{BinTree}, implement a version of
  \texttt{treeFold} that uses an accumulating parameter. (Hint:
  \texttt{foldl}.)
\item
  In a binary search tree all values in the left subtree of a node are
  less than the value at the node and all values in the right subtree
  are greater than the value at the node.

  Given binary search trees of type \texttt{BinTree}, implement the
  following Haskell functions:

  \begin{enumerate}
  \def\labelenumii{\alph{enumii}.}
  \item
    \texttt{makeTree} that takes a list and returns a perfectly balanced
    (i.e., minimal height) \texttt{BinTree} such that
    \texttt{flatten\ (makeTree\ xs)\ =\ sort\ xs}. Prelude function
    \texttt{sort} returns its argument rearranged into ascending order.
  \item
    \texttt{insertTree} that takes an element and a \texttt{BinTree} and
    returns the \texttt{BinTree} with the element inserted at an
    appropriate position.
  \item
    \texttt{elemTree} that takes an element and a \texttt{BinTree} and
    returns \texttt{True} if the element is in the tree and
    \texttt{False} otherwise.
  \item
    \texttt{heightTree} that takes a \texttt{BinTree} and returns its
    height. Assume that height means the number of levels in the tree.
    (A tree consisting of exactly one node has a height of 1.)
  \item
    \texttt{mirrorTree} that takes a \texttt{BinTree} and returns its
    mirror image. That is, it takes a tree and returns the tree with the
    left and right subtrees of every node swapped.
  \item
    \texttt{mapTree} that takes a function and a \texttt{BinTree} and
    returns the \texttt{BinTree} of the same shape except each node's
    value is computed by applying the function to the corresponding
    value in the input tree.
  \item
    \texttt{showTree} that takes a \texttt{BinTree} and displays the
    tree in a parenthesized, left-to-right, in-order traversal form.
    (That is, the traversal of a tree is enclosed in a pair of
    parentheses, with the traversal of the left subtree followed by the
    traversal of the right subtree.)
  \end{enumerate}

  Extend the package to support both insertion and deletion of elements.
  Keep the tree balanced using a technique such the AVL balancing
  algorithm.
\item
  Implement the package of functions described in the previous exercise
  for the data type \texttt{Tree}.
\item
  Each node of a general (i.e., multiway) tree consists of a label and a
  list of (zero or more) subtrees (each a general tree). We can define a
  general tree data type in Haskell as follows:

\begin{verbatim}
    data Gtree a = Node a [Gtree a]
\end{verbatim}

  For example, tree \texttt{(Node\ 0\ {[}\ {]})} consists of a single
  node with label 0; a more complex tree, , consists of root node with
  three single-node subtrees.

  Implement a ``map'' function for general trees, i.e., write Haskell
  function

\begin{verbatim}
    mapGtree :: (a -> b) -> Gtree a -> Gtree b 
\end{verbatim}

  that takes a function and a \texttt{Gtree} and returns the
  \texttt{Gtree} of the same shape such that each label is generated by
  applying the function to the corresponding label in the input tree.
\item
  We can introduce a new Haskell type for the natural numbers (i.e.,
  nonnegative integers) with the statement

\begin{verbatim}
    data Nat = Zero | Succ Nat 
\end{verbatim}

  where the constructor \texttt{Zero} represents the value 0 and
  constructor \texttt{Succ} represents the ``successor function'' from
  mathematics. Thus \texttt{(Succ\ Zero)} denotes 1,
  \texttt{(Succ\ (Succ\ Zero))} denotes 2, and so forth. Implement the
  following Haskell functions.

  \begin{enumerate}
  \def\labelenumii{\alph{enumii}.}
  \item
    \texttt{intToNat} that takes a nonnegative \texttt{Int} and returns
    the equivalent \texttt{Nat}, for example,~ returns .
  \item
    \texttt{natToInt} that takes a \texttt{Nat} and returns the
    equivalent value of type \texttt{Int}, for example,~ returns 1.
  \item
    \texttt{addNat} that takes two \texttt{Nat}s and returns their sum
    as a \texttt{Nat}. This function cannot use integer addition.
  \item
    \texttt{mulNat} that takes two \texttt{Nat}s and returns their
    product as a \texttt{Nat}. This function cannot use integer
    multiplication or addition.
  \item
    \texttt{compNat} that takes two \texttt{Nat}s and returns the value
    \texttt{-1} if the first is less than the second, \texttt{0} if they
    are equal, and \texttt{1} if the first is greater than the second.
    This function cannot use the integer comparison operators.
  \end{enumerate}
\item
  Consider the following Haskell data type for representing sequences
  (i.e., lists):

\begin{verbatim}
    data Seq a = Nil | Att (Seq a) a 
\end{verbatim}

  \texttt{Nil} represents the empty sequence. \texttt{Att\ xz\ y}
  represents the sequence in which \emph{last element} \texttt{y} is
  ``attached'' at the right end of the \emph{initial sequence}
  \texttt{xz}.

  Note that \texttt{Att} is similar to the ordinary ``cons''
  (\texttt{:}) for Haskell lists except that elements are attached at
  the opposite end of the sequences.
  \texttt{(Att\ (Att\ (Att\ Nil\ 1)\ 2)\ 3)} represents the same
  sequence as the ordinary list \texttt{(1:(2:(3:{[}{]})))}.

  Implement Haskell functions for the following operations on type
  \texttt{Seq}. The operations are analogous to the similarly named
  operations on the built-in Haskell lists.

  \begin{enumerate}
  \def\labelenumii{\alph{enumii}.}
  \item
    \texttt{lastSeq} takes a nonempty \texttt{Seq} and returns its last
    (i.e., rightmost) element.
  \item
    \texttt{initialSeq} takes a nonempty \texttt{Seq} and returns its
    initial sequence (i.e., sequence remaining after the last element
    removed).
  \item
    \texttt{lenSeq} takes a \texttt{Seq} and returns the number of
    elements that it contains.
  \item
    \texttt{headSeq} takes a nonempty \texttt{Seq} and returns its head
    (i.e., leftmost) element.
  \item
    \texttt{tailSeq} takes a nonempty \texttt{Seq} and returns the
    \texttt{Seq} remaining after the head element is removed.
  \item
    \texttt{conSeq} that takes an element and a \texttt{Seq} and returns
    a \texttt{Seq} with the argument element as its head and the
    \texttt{Seq} argument as its tail.
  \item
    \texttt{appSeq} takes two arguments of type \texttt{Seq} and returns
    a \texttt{Seq} with the second argument appended after the first.
  \item
    \texttt{revSeq} takes a \texttt{Seq} and returns the \texttt{Seq}
    with the same elements in reverse order.
  \item
    \texttt{mapSeq} takes a function and a \texttt{Seq} and returns the
    \texttt{Seq} resulting from applying the function to each element of
    the sequence in turn.
  \item
    \texttt{filterSeq} that takes a predicate and a \texttt{Seq} and
    returns the \texttt{Seq} containing only those elements that satisfy
    the predicate.
  \item
    \texttt{listToSeq} takes an ordinary Haskell list and returns the
    \texttt{Seq} with the same values in the same order (e.g.,
    \texttt{headSeq\ (listToSeq\ xs)\ =\ head\ xs} for nonempty
    \texttt{xs}.)
  \item
    \texttt{seqToList} takes a \texttt{Seq} and returns the ordinary
    Haskell list with the same values in the same order (e.g.,
    \texttt{head\ (seqToList\ xz)\ =\ headSeq\ xz} for nonempty
    \texttt{xz}.)
  \end{enumerate}
\item
  Consider the following Haskell data type for representing sequences
  (i.e., lists):

\begin{verbatim}
    data Seq a = Nil | Unit a | Cat (Seq a) (Seq a)
\end{verbatim}

  The constructor \texttt{Nil} represents the empty sequence;
  \texttt{Unit} represents a single-element sequence; and \texttt{Cat}
  represents the ``concatenation'' (i.e., append) of its two arguments,
  the second argument appended after the first.

  Implement Haskell functions for the following operations on type
  \texttt{Seq}. The operations are analogous to the similarly named
  operations on the built-in Haskell lists. (Do not convert back and
  forth to lists.)

  \begin{enumerate}
  \def\labelenumii{\alph{enumii}.}
  \item
    \texttt{toSeq} that takes a list and returns a corresponding
    \texttt{Seq} that is balanced.
  \item
    \texttt{fromSeq} that takes a \texttt{Seq} and returns the
    corresponding list.
  \item
    \texttt{appSeq} that takes two arguments of type \texttt{Seq} and
    returns a \texttt{Seq} with the second argument appended after the
    first.
  \item
    \texttt{conSeq} that takes an element and a \texttt{Seq} and returns
    a \texttt{Seq} with the argument element as its head and the
    \texttt{Seq} argument as its tail.
  \item
    \texttt{lenSeq} that takes a \texttt{Seq} and returns the number of
    elements that it contains.
  \item
    \texttt{revSeq} that takes a \texttt{Seq} and returns a \texttt{Seq}
    with the same elements in reverse order.
  \item
    \texttt{headSeq} that takes a nonempty \texttt{Seq} and returns its
    head (i.e., leftmost or front) element. (Be careful!)
  \item
    \texttt{tailSeq} that takes a nonempty \texttt{Seq} and returns the
    \texttt{Seq} remaining after the head is removed.
  \item
    \texttt{normSeq} that takes a \texttt{Seq} and returns a
    \texttt{Seq} with unnecessary embedded \texttt{Nil}s removed. (For
    example, \texttt{normSeq\ (Cat\ (Cat\ Nil\ (Unit\ 1))\ Nil)} returns
    \texttt{(Unit\ 1)}.)
  \item
    \texttt{eqSeq} that takes two \texttt{Seq}s and returns
    \texttt{True} if the sequences of values are equal and returns
    \texttt{False} otherwise. Note that two \texttt{Seq} ``trees'' may
    be structurally different yet represent the same sequence of values.

    For example, \texttt{(Cat\ Nil\ (Unit\ 1))} and
    \texttt{(Cat\ (Unit\ 1)\ Nil)} have the same sequence of values
    (i.e., \texttt{{[}1{]}}). But \texttt{(Cat\ (Unit\ 1)\ (Unit\ 2))}
    and \texttt{(Cat\ (Unit\ 2)\ (Unit\ 1))} do not represent the same
    sequence of values (i.e., \texttt{{[}1,2{]}} and \texttt{{[}2,1{]}},
    respectively).

    Also \texttt{(Cat\ (Cat\ (Unit\ 1)\ (Unit\ 2))\ (Unit\ 3))} has the
    same sequence of values as
    \texttt{(Cat\ (Cat\ (Unit\ 1)\ (Unit\ 2))\ (Unit\ 3))} (i.e.,
    \texttt{{[}1,2,3{]}}).
  \end{enumerate}

  In general what are the advantages and disadvantages of representing
  lists this way?
\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[{[}Wikipedia 2017{]}]
Wikipedia articles on ``Algebraic Data Type'' and ``Abstract Data
Type''.
\end{description}

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

Types, algebraic data types (composite), sum (tagged, disjoint union,
variant, enumerated), product (tuple, record), nullary,recursive types,
algebraic data types versus abstract data types, pattern matching, safe
error handling, \texttt{Maybe} and \texttt{Either} ``option'' types

\end{document}
