\PassOptionsToPackage{unicode=true}{hyperref} % options for packages loaded elsewhere
\PassOptionsToPackage{hyphens}{url}
%
\documentclass[english,]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
  \usepackage{textcomp} % provides euro and other symbols
\else % if luatex or xelatex
  \usepackage{unicode-math}
  \defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{%
\usepackage[]{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
}
\usepackage{hyperref}
\hypersetup{
            pdftitle={CSci 555: Functional Programming Recursion Styles, Correctness, and Efficiency --- Scala Version ---},
            pdfauthor={H. Conrad Cunningham},
            pdfborder={0 0 0},
            breaklinks=true}
\urlstyle{same}  % don't use monospace font for urls
\usepackage{color}
\usepackage{fancyvrb}
\newcommand{\VerbBar}{|}
\newcommand{\VERB}{\Verb[commandchars=\\\{\}]}
\DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}}
% Add ',fontsize=\small' for more characters per line
\newenvironment{Shaded}{}{}
\newcommand{\AlertTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
\newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.49,0.56,0.16}{#1}}
\newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\BuiltInTok}[1]{#1}
\newcommand{\CharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\CommentTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textit{#1}}}
\newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.53,0.00,0.00}{#1}}
\newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
\newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.56,0.13,0.00}{#1}}
\newcommand{\DecValTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.73,0.13,0.13}{\textit{#1}}}
\newcommand{\ErrorTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
\newcommand{\ExtensionTok}[1]{#1}
\newcommand{\FloatTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.02,0.16,0.49}{#1}}
\newcommand{\ImportTok}[1]{#1}
\newcommand{\InformationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
\newcommand{\NormalTok}[1]{#1}
\newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.40,0.40,0.40}{#1}}
\newcommand{\OtherTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{#1}}
\newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.74,0.48,0.00}{#1}}
\newcommand{\RegionMarkerTok}[1]{#1}
\newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.73,0.40,0.53}{#1}}
\newcommand{\StringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\VariableTok}[1]{\textcolor[rgb]{0.10,0.09,0.49}{#1}}
\newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\WarningTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\usepackage{longtable,booktabs}
% Fix footnotes in tables (requires footnote package)
\IfFileExists{footnote.sty}{\usepackage{footnote}\makesavenoteenv{longtable}}{}
\setlength{\emergencystretch}{3em}  % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{0}
% Redefines (sub)paragraphs to behave more like sections
\ifx\paragraph\undefined\else
\let\oldparagraph\paragraph
\renewcommand{\paragraph}[1]{\oldparagraph{#1}\mbox{}}
\fi
\ifx\subparagraph\undefined\else
\let\oldsubparagraph\subparagraph
\renewcommand{\subparagraph}[1]{\oldsubparagraph{#1}\mbox{}}
\fi

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

\usepackage{caption}
\DeclareCaptionLabelFormat{nolabel}{}
\captionsetup{labelformat=nolabel}
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[shorthands=off,main=english]{babel}
\else
  % load polyglossia as late as possible as it *could* call bidi if RTL lang (e.g. Hebrew or Arabic)
  \usepackage{polyglossia}
  \setmainlanguage[]{english}
\fi

\title{CSci 555: Functional Programming\\
Recursion Styles, Correctness, and Efficiency\\
--- Scala Version ---}
\author{\textbf{H. Conrad Cunningham}}
\date{\textbf{7 February 2019}}

\begin{document}
\maketitle

{
\setcounter{tocdepth}{4}
\tableofcontents
}
Copyright (C) 2016, 2019, \href{http://www.cs.olemiss.edu/~hcc}{H.
Conrad Cunningham}\\
Professor of \href{https://www.cs.olemiss.edu}{Computer and Information
Science}\\
\href{http://www.olemiss.edu}{University of Mississippi}\\
211 Weir Hall\\
P.O. Box 1848\\
University, MS 38677\\
(662) 915-5358

\textbf{Browser Advisory:} The HTML version of this textbook requires a
browser that supports the display of MathML. A good choice as of
February 2019 is a recent version of Firefox from Mozilla.

\newpage

\hypertarget{recursion-styles-correctness-and-efficiency}{%
\section{Recursion Styles, Correctness, and
Efficiency}\label{recursion-styles-correctness-and-efficiency}}

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

This set of notes introduces basic recursive programming styles and
examines issues of termination, correctness, and efficiency.

The goals of the chapter are to:

\begin{itemize}
\item
  explore several recursive programming styles---linear and nonlinear,
  backward and forward, tail, and logarithmic---and their implementation
  using Scala
\item
  examine how to analyze Scala functions to determine under what
  conditions they terminate with the correct result and how efficient
  they are
\item
  explore methods for developing recursive Scala programs that terminate
  with the correct result and are efficient in both time and space usage
\end{itemize}

Note: The source code for the functions in these notes are in the Scala
file
\href{RecursionStyles.scala}{\VERB|\ExtensionTok{RecursionStyles.scala}|}.

\hypertarget{linear-and-nonlinear-recursion}{%
\subsection{Linear and Nonlinear
Recursion}\label{linear-and-nonlinear-recursion}}

In this section, we examine the concepts of linear and nonlinear
recursion. The following two sections examine other styles.

\hypertarget{linear-recursion}{%
\subsubsection{Linear recursion}\label{linear-recursion}}

A function definition is \emph{linear recursive} if at most one
recursive application of the function occurs in a leg of the definition
(i.e. along a path from an entry to a return). The various function
clauses and branches of conditional expressions
(e.g.~\VERB|\KeywordTok{if}| and \VERB|\KeywordTok{match}|) introduce
paths.

The definition of the function \VERB|\NormalTok{factorial}| below is
linear recursive because the expression in the second leg of the
definition
(i.e.~\VERB|\NormalTok{n * }\FunctionTok{factorial}\NormalTok{(n}\DecValTok{-1}\NormalTok{)}|)
involves a single recursive application. The other leg is nonrecursive;
it is the base case of the recursive definition.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{factorial}\NormalTok{(n: Int): Int = n }\KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case} \DecValTok{0}\NormalTok{          => }\DecValTok{1}
        \KeywordTok{case}\NormalTok{ m }\KeywordTok{if}\NormalTok{ m > }\DecValTok{0}\NormalTok{ => m * }\FunctionTok{factorial}\NormalTok{(m}\DecValTok{-1}\NormalTok{)  }\CommentTok{// linear rec.}
        \KeywordTok{case}\NormalTok{ _          =>}
\NormalTok{            sys.}\FunctionTok{error}\NormalTok{(s}\StringTok{"Factorial undefined for $n"}\NormalTok{)}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

Scala checks for pattern matches for the clauses in the order given in
the function definition. It executes the leg corresponding to the first
successful match. If no pattern matches, then the function aborts and
displays an error message.

\hypertarget{termination-of-recursion}{%
\subsubsection{Termination of
recursion}\label{termination-of-recursion}}

How do we know that function \VERB|\NormalTok{factorial}| terminates?

To show that evaluation of a recursive function terminates, we must show
that each recursive application \emph{always} gets closer to a normal
termination condition represented by a base case.

For a call \VERB|\FunctionTok{factorial}\NormalTok{(n)}| with
\VERB|\NormalTok{n > }\DecValTok{0}|, the argument of the recursive
application always decreases to \VERB|\NormalTok{n - }\DecValTok{1}|.
Because the argument always decreases in integer steps, it must
eventually reach 0 and, hence, terminate in the first leg of the
definition.

\hypertarget{preconditions-and-postconditions}{%
\subsubsection{Preconditions and
postconditions}\label{preconditions-and-postconditions}}

The \emph{precondition} of a function is what the caller (i.e.~the
client of the function) must ensure holds when calling the function. A
precondition may specify the valid combinations of values of the
arguments. It may also record any constraints on the values of
``global'' data structures that the function accesses or modifies. (By
``global'' we mean any entity that is not a parameter or local variable
of the function.)

If the precondition holds, the supplier (i.e.~developer) of the function
must ensure that the function terminates with the \emph{postcondition}
satisfied. That is, the function returns the required values and/or
alters the ``global'' data structures in the required manner.

The precondition of the \VERB|\NormalTok{factorial}| function requires
that argument \VERB|\NormalTok{n}| be a nonnegative integer value. We
could use Scala's predefined \VERB|\KeywordTok{requires}| method to
ensure this precondition holds, but, in this version, if all pattern
matches fail, the function call aborts with a standard error message.

The postcondition of \VERB|\NormalTok{factorial}| is that the result
returned is the correct mathematical value of \VERB|\NormalTok{n}|
factorial. The function \VERB|\NormalTok{factorial}| neither accesses
nor modifies any global data structures.

\hypertarget{time-and-space-complexity}{%
\subsubsection{Time and space
complexity}\label{time-and-space-complexity}}

How efficient is function \VERB|\NormalTok{factorial}|?

Function \VERB|\NormalTok{factorial}| recurses to a depth of
\VERB|\NormalTok{n}|. It thus has \emph{time complexity}
O(\VERB|\NormalTok{n}|), if we count either the recursive calls or the
multiplication at each level.

The \emph{space complexity} is also O(\VERB|\NormalTok{n}|) because a
new runtime stack frame is needed for each recursive call.

\hypertarget{nonlinear-recursion}{%
\subsubsection{Nonlinear recursion}\label{nonlinear-recursion}}

A \emph{nonlinear recursion} is a recursive function in which the
evaluation of some leg requires more than one recursive application.

For example, the naive Fibonacci number function \VERB|\NormalTok{fib}|
shown below has two recursive applications in its third leg. When we
apply this function to a nonnegative integer argument greater than 1, we
generate a pattern of recursive applications that has the ``shape'' of a
binary tree. Some call this a \emph{tree recursion}.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{fib}\NormalTok{(n: Int): Int = n }\KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case} \DecValTok{0}\NormalTok{           => }\DecValTok{0}
        \KeywordTok{case} \DecValTok{1}\NormalTok{           => }\DecValTok{1}
        \KeywordTok{case}\NormalTok{ m }\KeywordTok{if}\NormalTok{ m >= }\DecValTok{2}\NormalTok{ => }\FunctionTok{fib}\NormalTok{(m}\DecValTok{-1}\NormalTok{) + }\FunctionTok{fib}\NormalTok{(m}\DecValTok{-2}\NormalTok{) }\CommentTok{// double rec.}
        \KeywordTok{case}\NormalTok{ _           =>}
\NormalTok{            sys.}\FunctionTok{error}\NormalTok{(s}\StringTok{"Fibonacci undefined for $n"}\NormalTok{)}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

What are the precondition and postcondition for
\VERB|\FunctionTok{fib}\NormalTok{(n)}|?

For \VERB|\FunctionTok{fib}\NormalTok{(n)}|, the precondition
\VERB|\NormalTok{n >= }\DecValTok{0}| ensures that the function is
defined. When called with the precondition satisfied, the postcondition
is:

\begin{quote}
\VERB|\FunctionTok{fib}\NormalTok{(n)}| \emph{= Fibonacci}\texttt{(n)}
\end{quote}

How do we know that \VERB|\NormalTok{fib}| terminates?

For the recursive case n \textgreater{}= 2, the two recursive calls have
arguments that are 1 or 2 less than \VERB|\NormalTok{n}|. Thus every
call gets closer to one of the two base cases.

What are the time and space complexities of function
\VERB|\NormalTok{fib}|?

Function \VERB|\NormalTok{fib}| is combinatorially explosive, having a
time complexity O(\VERB|\FunctionTok{fib}\NormalTok{(n)}|).

The space complexity is O(\VERB|\NormalTok{n}|) because a new runtime
stack frame is needed for each recursive call and the calls recurse to a
depth of \VERB|\NormalTok{n}|.

An advantage of a linear recursion over a nonlinear one is that a linear
recursion can be compiled into a \emph{loop} in a straightforward
manner. Converting a nonlinear recursion to a loop is, in general,
difficult.

\hypertarget{backward-and-forward-recursion}{%
\subsection{Backward and Forward
Recursion}\label{backward-and-forward-recursion}}

In this section, we examine the concepts of backward and forward
recursion.

\hypertarget{backward-recursion}{%
\subsubsection{Backward recursion}\label{backward-recursion}}

A function definition is \emph{backward recursive} if the recursive
application is \emph{embedded within another expression}. During
execution, the program must complete the evaluation of the expression
after the recursive call returns. Thus, the program must preserve
sufficient information from the outer call's environment to complete the
evaluation.

The definition for the function \VERB|\NormalTok{factorial}| above is
backward recursive because the recursive application
\VERB|\FunctionTok{factorial}\NormalTok{(n}\DecValTok{-1}\NormalTok{)}|
in the second leg is embedded within the expression
\VERB|\NormalTok{n * }\FunctionTok{factorial}\NormalTok{(n}\DecValTok{-1}\NormalTok{)}|.
During execution, the multiplication must be done after return. The
program must ``remember'' (at least) the value of parameter
\VERB|\NormalTok{n}| for that call.

A compiler can translate a backward linear recursion into a loop, but
the translation may require the use of a stack to store the program's
\emph{state} (i.e.~the values of the variables and execution location)
needed to complete the evaluation of the expression.

Often when we design an algorithm, the first functions we come up with
are backward recursive. They often correspond directly to a convenient
recurrence relation. It is often useful to convert the function into an
equivalent one that evaluates more efficiently.

\hypertarget{forward-recursion}{%
\subsubsection{Forward recursion}\label{forward-recursion}}

A function definition is \emph{forward recursive} if the recursive
application is \emph{not embedded within another expression}. That is,
the \emph{outermost expression is the recursive application} and any
other subexpressions appear in the argument lists. During execution,
significant work is done as the recursive calls are made (e.g.~in the
argument list of the recursive call).

The definition for the auxiliary function \VERB|\NormalTok{factIter}|
within the \VERB|\NormalTok{factorial2}| definition below is forward
recursive. The recursive application
\VERB|\FunctionTok{factIter}\NormalTok{(m}\DecValTok{-1}\NormalTok{,m*r)}|
in the second leg is on the outside of the expression evaluated for
return. The other legs are nonrecursive.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{factorial2}\NormalTok{(n: Int): Int = \{}

        \KeywordTok{def} \FunctionTok{factIter}\NormalTok{(n: Int, r: Int): Int = n }\KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case} \DecValTok{0}\NormalTok{          => r}
            \KeywordTok{case}\NormalTok{ m }\KeywordTok{if}\NormalTok{ m > }\DecValTok{0}\NormalTok{ => }\FunctionTok{factIter}\NormalTok{(m}\DecValTok{-1}\NormalTok{,m*r)}
\NormalTok{        \}}

        \KeywordTok{if}\NormalTok{ (n >= }\DecValTok{0}\NormalTok{)}
            \FunctionTok{factIter}\NormalTok{(n,}\DecValTok{1}\NormalTok{)}
        \KeywordTok{else}
\NormalTok{            sys.}\FunctionTok{error}\NormalTok{(s}\StringTok{"Factorial undefined for $n"}\NormalTok{)}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

What are the precondition and postcondition for
\VERB|\FunctionTok{factIter}\NormalTok{(n,r)}|?

To avoid termination, \VERB|\FunctionTok{factIter}\NormalTok{(n,r)}|
requires \VERB|\NormalTok{n >= }\DecValTok{0}|. Its postcondition is
that:

\begin{quote}
\VERB|\FunctionTok{factIter}\NormalTok{(n,r) = r *}|
\emph{fact}\VERB|\NormalTok{(n)}|
\end{quote}

How do we know that \VERB|\NormalTok{factIter}| terminates?

Argument \VERB|\NormalTok{n}| of the recursive call is at least 1 and
decreases by 1 on each recursive call; it eventually reaches the base
case.

What is the time complexity of function \VERB|\NormalTok{factorial2}|?

Function \VERB|\FunctionTok{factIter}\NormalTok{(n,r)}| has a time
complexity of O(\VERB|\NormalTok{n}|). But, because, tail call
optimization converts the \VERB|\NormalTok{factIter}| recursion to a
loop, the time complexity's constant factor should be smaller than that
of \VERB|\FunctionTok{factorial}\NormalTok{(n)}|.

As shown, \VERB|\FunctionTok{factIter}\NormalTok{(n,r)}| seems to have a
space complexity of O(\VERB|\NormalTok{n}|). But tail call optimization
converts the recursion to a loop. Thus the space complexity of
\VERB|\FunctionTok{factIter}\NormalTok{(n,r)}| becomes O(1).

\hypertarget{tail-recursion}{%
\subsubsection{Tail Recursion}\label{tail-recursion}}

A function definition is \emph{tail recursive} if it is \emph{both
forward recursive and linear recursive}. In a tail recursion, the last
action performed before the return is a recursive call.

The definition of the function \VERB|\NormalTok{factIter}| above is tail
recursive because it is both forward recursive and linear recursive.

Tail recursive definitions are easy to compile into efficient loops.
There is no need to save the states of unevaluated expressions for
higher level calls; the result of a recursive call can be returned
directly as the caller's result. This is sometimes called \emph{tail
call optimization} (or ``tail call elimination'' or ``proper tail
calls'').

In converting the backward recursive function
\VERB|\NormalTok{factorial}| to a tail recursive auxiliary function, we
added the parameter \VERB|\NormalTok{r}| to \VERB|\NormalTok{factIter}|.
This parameter is sometimes called an \emph{accumulating parameter} (or
just an \emph{accumulator}).

We typically use an accumulating parameter to ``accumulate'' the result
of the computation incrementally for return when the recursion
terminates. In \VERB|\NormalTok{factIter}|, this ``state'' passed from
one ``iteration'' to the next enables us to convert a backward recursive
function to an ``equivalent'' tail recursive one.

Function \VERB|\FunctionTok{factIter}\NormalTok{(n,r)}| defines a more
general function than \VERB|\NormalTok{factorial}|. It computes a
factorial when we initialize the accumulator to 1, but it can compute
some multiple of the factorial if we initialize the accumulator to
another value. However, the application of \VERB|\NormalTok{factIter}|
in \VERB|\NormalTok{factorial2}| gives the initial value of 1 needed for
factorial.

Consider auxiliary function \VERB|\NormalTok{fibIter}| used by function
\VERB|\NormalTok{fib2}| below. This function adds two ``accumulating
parameters'' to the backward nonlinear recursive function
\VERB|\NormalTok{fib}| to convert the nonlinear (tree) recursion into a
tail recursion. This technique works for Fibonacci numbers, but the same
technique will not work in all cases.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{fib2}\NormalTok{(n: Int): Int = \{}

        \KeywordTok{def} \FunctionTok{fibIter}\NormalTok{(n: Int, p: Int, q: Int): Int = n }\KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case} \DecValTok{0}\NormalTok{ => p}
            \KeywordTok{case}\NormalTok{ m => }\FunctionTok{fibIter}\NormalTok{(m}\DecValTok{-1}\NormalTok{,q,p+q)}
\NormalTok{        \}}

        \KeywordTok{if}\NormalTok{ (n >= }\DecValTok{0}\NormalTok{)}
            \FunctionTok{fibIter}\NormalTok{(n,}\DecValTok{0}\NormalTok{,}\DecValTok{1}\NormalTok{)}
        \KeywordTok{else}
\NormalTok{            sys.}\FunctionTok{error}\NormalTok{(s}\StringTok{"Fibonacci undefined for $n"}\NormalTok{)}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

What are the precondition and postcondition for
\VERB|\FunctionTok{fibIter}\NormalTok{(n,p,q)}|?

To avoid abnormal termination,
\VERB|\FunctionTok{fibIter}\NormalTok{(n,p,q)}| requires
\VERB|\NormalTok{n >= }\DecValTok{0}|. When the precondition holds, its
postcondition is:

\begin{quote}
\VERB|\FunctionTok{fibIter}\NormalTok{(n,p,q) =}|
\emph{Fibonacci}\VERB|\NormalTok{(n) + (p + q - }\DecValTok{1}\NormalTok{)}|
\end{quote}

How do we know that \VERB|\NormalTok{fibIter}| terminates?

The recursive leg of \VERB|\FunctionTok{fibIter}\NormalTok{(n,p,q)}| is
only evaluated when \VERB|\NormalTok{n1 > }\DecValTok{0}|. On the
recursive call, that argument decreases by 1. So eventually the
computation reaches the base case.

What are the time and space complexities of \VERB|\NormalTok{fibIter}|?

Function \VERB|\NormalTok{fibIter}| has a time complexity of
O(\VERB|\NormalTok{n}|) in contrast to
O(\VERB|\FunctionTok{fib}\NormalTok{(n)}|) for \VERB|\NormalTok{fib}|.
This algorithmic speedup results from the replacement of the very
expensive operation
\VERB|\FunctionTok{fib}\NormalTok{(n}\DecValTok{-1}\NormalTok{) + }\FunctionTok{fib}\NormalTok{(n}\DecValTok{-2}\NormalTok{)}|
at each level in \VERB|\NormalTok{fib}| by the inexpensive operation
\VERB|\NormalTok{p + q}| (i.e.~addition of two numbers) in
\VERB|\NormalTok{fib2}|.

Without tail call optimization,
\VERB|\FunctionTok{fibIter}\NormalTok{(n,p,q)}| has space complexity of
O(\VERB|\NormalTok{n}|). However, tail call optimization can convert the
recursion to a loop, giving O(1) space complexity.

When combined with tail-call optimization, a tail recursive function may
be more efficient than the equivalent backward recursive function.
However, the backward recursive function is often easier to understand
and to reason about.

\hypertarget{logarithmic-recursive}{%
\subsection{Logarithmic Recursive}\label{logarithmic-recursive}}

We can define the exponentiation operator \VERB|\NormalTok{^}| in terms
of multiplication as follows for integers \VERB|\NormalTok{b}| and
\VERB|\NormalTok{n >= }\DecValTok{0}|:

\begin{quote}
\texttt{b\^{}n\ =} \(\prod_{i=1}^{i=n} b\)
\end{quote}

The backward recursive exponentiation function \VERB|\NormalTok{expt1}|
below raises a number to a nonnegative integer power. It has time
complexity O(\VERB|\NormalTok{n}|) and space complexity
O(\VERB|\NormalTok{n}|).

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{expt1}\NormalTok{(b: Double, n: Int): Double = n }\KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case} \DecValTok{0}\NormalTok{          => }\DecValTok{1}
        \KeywordTok{case}\NormalTok{ m }\KeywordTok{if}\NormalTok{ m > }\DecValTok{0}\NormalTok{ => b * }\FunctionTok{expt1}\NormalTok{(b,m}\DecValTok{-1}\NormalTok{)}
        \KeywordTok{case}\NormalTok{ _          =>}
\NormalTok{            sys.}\FunctionTok{error}\NormalTok{(s}\StringTok{"Cannot raise to a negative power $n"}\NormalTok{)}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

Consider the following questions relative to
\VERB|\FunctionTok{expt1}\NormalTok{(b,n)}|.

\begin{itemize}
\item
  What are the precondition and postcondition for
  \VERB|\FunctionTok{expt1}\NormalTok{(b,n)}|?
\item
  How do we know that \VERB|\FunctionTok{expt1}\NormalTok{(b,n)}|
  terminates?
\item
  What are the time and space complexities for
  \VERB|\FunctionTok{expt1}\NormalTok{(b,n)}|?
\end{itemize}

We can define a tail recursive auxiliary function
\VERB|\NormalTok{exptIter}| by adding a new parameter
\VERB|\NormalTok{p}| to accumulate the value of the exponentiation
incrementally. We can define \VERB|\NormalTok{exptIter}| within a
function \VERB|\NormalTok{expt2}|, taking advantage of the fact that the
base \VERB|\NormalTok{b}| does not change. This is shown below.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{expt2}\NormalTok{(b: Double, n: Int): Double = \{}
    
        \KeywordTok{def} \FunctionTok{exptIter}\NormalTok{(n: Int, p: Double): Double = }
\NormalTok{            n }\KeywordTok{match}\NormalTok{ \{}
                \KeywordTok{case} \DecValTok{0}\NormalTok{ => p}
                \KeywordTok{case}\NormalTok{ m => }\FunctionTok{exptIter}\NormalTok{(m}\DecValTok{-1}\NormalTok{,b*p)}
\NormalTok{            \}}
            
        \KeywordTok{if}\NormalTok{ (n >= }\DecValTok{0}\NormalTok{)}
            \FunctionTok{exptIter}\NormalTok{(n,}\DecValTok{1}\NormalTok{)}
        \KeywordTok{else}
\NormalTok{            sys.}\FunctionTok{error}\NormalTok{(s}\StringTok{"Cannot raise to negative power $n"}\NormalTok{)}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

Consider the following questions relative to
\VERB|\FunctionTok{expt1}\NormalTok{(b,n)}|.

\begin{itemize}
\item
  What are the precondition and postcondition for
  \VERB|\FunctionTok{exptIter}\NormalTok{(n,p)}|?
\item
  How do we know that \VERB|\FunctionTok{exptIter}\NormalTok{(n,p)}|
  terminates?
\item
  What are the time and space complexities for
  \VERB|\FunctionTok{exptIter}\NormalTok{(n,p)}|?
\end{itemize}

The exponentiation function can be made computationally more efficient
by squaring the intermediate values instead of iteratively multiplying.
We observe that:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    b^n = b^(n/}\DecValTok{2}\NormalTok{)^}\DecValTok{2}   \KeywordTok{if}\NormalTok{ n is even}
\NormalTok{    b^n = b * b^(n}\DecValTok{-1}\NormalTok{) }\KeywordTok{if}\NormalTok{ n is odd}
\end{Highlighting}
\end{Shaded}

Function \VERB|\NormalTok{expt3}| below incorporates this observation in
an improved algorithm. Its time complexity is
O(\VERB|\FunctionTok{log}\NormalTok{(n)}|) and space complexity is
O(\VERB|\FunctionTok{log}\NormalTok{(n)}|).

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{expt3}\NormalTok{(b: Double, n: Int): Double = \{}

        \KeywordTok{def} \FunctionTok{exptAux}\NormalTok{(n: Int): Double = n }\KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case} \DecValTok{0}\NormalTok{                 => }\DecValTok{1}
            \KeywordTok{case}\NormalTok{ m }\KeywordTok{if}\NormalTok{ (m % }\DecValTok{2}\NormalTok{ == }\DecValTok{0}\NormalTok{) => }\CommentTok{// i.e. even}
                \KeywordTok{val}\NormalTok{ exp = }\FunctionTok{exptAux}\NormalTok{(m/}\DecValTok{2}\NormalTok{)}
\NormalTok{                exp * exp             }\CommentTok{// backward recursion}
            \KeywordTok{case}\NormalTok{ m                 => }\CommentTok{// i.e. odd}
\NormalTok{                b * }\FunctionTok{exptAux}\NormalTok{(m}\DecValTok{-1}\NormalTok{)      }\CommentTok{// backward recursion}
\NormalTok{        \}}

        \KeywordTok{if}\NormalTok{ (n >= }\DecValTok{0}\NormalTok{)}
            \FunctionTok{exptAux}\NormalTok{(n)}
        \KeywordTok{else}
\NormalTok{            sys.}\FunctionTok{error}\NormalTok{(s}\StringTok{"Cannot raise to negative power $n"}\NormalTok{)}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

Consider the following questions relative to \VERB|\NormalTok{expt3}|.

\begin{itemize}
\item
  What are the precondition and postcondition of
  \VERB|\FunctionTok{expt3}\NormalTok{(b,n)}|?
\item
  How do we know that \VERB|\FunctionTok{exptAux}\NormalTok{(n)}|
  terminates?
\item
  What are the time and space complexities of
  \VERB|\FunctionTok{exptAux}\NormalTok{(n)}|?
\end{itemize}

\hypertarget{exercises}{%
\subsection{Exercises}\label{exercises}}

TODO: I adapted many of these exercise descriptions from similar Haskell
exercises in ELIFP {[}Cunningham 2018{]} Chapters 5 and 9. They should
be reconsidered, refined, and tested better for use in a Scala-based
functional programming course. The order may also need to be modified
and some exercises are probably better placed with different notes.

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Answer the questions (precondition, postcondition, termination, time
  complexity, space complexity) in the discussion of
  \VERB|\NormalTok{expt1}|.
\item
  Answer the questions in the discussion of \VERB|\NormalTok{expt2}| and
  \VERB|\NormalTok{exptIter}|.
\item
  Answer the questions in the discussion of \VERB|\NormalTok{expt3}| and
  \VERB|\NormalTok{exptAux}|.
\item
  Develop a Scala function \texttt{sumSqBig} that takes three
  \VERB|\NormalTok{Double}| arguments and returns the sum of the squares
  of the two larger numbers.

  For example,
  \VERB|\FunctionTok{sumSqBig}\NormalTok{(}\FloatTok{2.0}\NormalTok{,}\FloatTok{1.0}\NormalTok{,}\FloatTok{3.0}\NormalTok{)}|
  yields \VERB|\FloatTok{13.0}|.
\item
  Develop a Scala function \VERB|\NormalTok{prodSqSmall}| that takes
  three \VERB|\NormalTok{Double}| arguments and returns the product of
  the squares of the two smaller numbers.

  For example,
  \VERB|\FunctionTok{prodSqSmall}\NormalTok{(}\FloatTok{2.0}\NormalTok{,}\FloatTok{4.0}\NormalTok{,}\FloatTok{3.0}\NormalTok{)}|
  yields \VERB|\FloatTok{36.0}|.
\item
  Develop a Scala function \VERB|\NormalTok{xor}| that takes two Boolean
  arguments and returns the ``exclusive-or'' of the two values. An
  exclusive-or operation returns \VERB|\KeywordTok{true}| when exactly
  one of its arguments is \VERB|\KeywordTok{true}| and returns
  \VERB|\KeywordTok{false}| otherwise.
\item
  Develop a Scala function \VERB|\NormalTok{implies}| that takes two
  Boolean arguments \VERB|\NormalTok{p}| and \VERB|\NormalTok{q}| and
  returns the Boolean result \VERB|\NormalTok{p}| \(\Rightarrow\)
  \VERB|\NormalTok{q}| (i.e.~logical implication). That is, if
  \VERB|\NormalTok{p}| is \VERB|\KeywordTok{true}| and
  \VERB|\NormalTok{q}| is \VERB|\KeywordTok{false}|, then the result is
  \VERB|\KeywordTok{false}|; otherwise, the result is
  \VERB|\KeywordTok{true}|.

  Note: This function is sometimes called \VERB|\NormalTok{nand}|.
\item
  Develop a Scala function \VERB|\NormalTok{div23n5}| that takes an
  \VERB|\NormalTok{Int}| and returns the Boolean
  \VERB|\KeywordTok{true}| if and only if the integer is divisible by 2
  or divisible by 3, but is not divisible by 5.

  For example,
  \VERB|\FunctionTok{div23n5}\NormalTok{(}\DecValTok{4}\NormalTok{)}|,
  \VERB|\FunctionTok{div23n5}\NormalTok{(}\DecValTok{6}\NormalTok{)}|,
  and
  \VERB|\FunctionTok{div23n5}\NormalTok{(}\DecValTok{9}\NormalTok{)}|
  yield \VERB|\KeywordTok{true}| and
  \VERB|\FunctionTok{div23n5}\NormalTok{(}\DecValTok{5}\NormalTok{)}|,
  \VERB|\FunctionTok{div23n5}\NormalTok{(}\DecValTok{7}\NormalTok{_}|,
  \VERB|\FunctionTok{div23n5}\NormalTok{(}\DecValTok{10}\NormalTok{)}|,
  \VERB|\FunctionTok{div23n5}\NormalTok{(}\DecValTok{15}\NormalTok{)}|,
  \VERB|\FunctionTok{div23n5}\NormalTok{(}\DecValTok{30}\NormalTok{)}|
  yield \VERB|\KeywordTok{false}|.
\item
  Develop a Scala function \VERB|\NormalTok{notDiv}| such that
  \VERB|\FunctionTok{notDiv}\NormalTok{(n,d)}| returns
  \VERB|\KeywordTok{true}| if and only if integer \VERB|\NormalTok{n}|
  is not divisible by integer \VERB|\NormalTok{d}|.

  For example,
  \VERB|\FunctionTok{notDiv}\NormalTok{(}\DecValTok{10}\NormalTok{,}\DecValTok{5}\NormalTok{)}|
  yields \VERB|\KeywordTok{false}| and
  \VERB|\FunctionTok{notDiv}\NormalTok{(}\DecValTok{11}\NormalTok{,}\DecValTok{5}\NormalTok{)}|
  yields \VERB|\KeywordTok{true}|.
\item
  Develop a Scala function \VERB|\NormalTok{ccArea}| that takes the
  \emph{diameters} of two concentric circles (i.e.~with the same center
  point) as \VERB|\NormalTok{Double}| values and returns the area of the
  space between the circles. That is, compute the area of the larger
  circle minus the area of the smaller circle.

  For example, \texttt{ccArea(2.0,4.0)} yields approximately
  \VERB|\FloatTok{9.42477796}|.
\item
  Develop a Scala function \VERB|\NormalTok{addTax}| that takes two
  \VERB|\NormalTok{Double}| values such that
  \VERB|\FunctionTok{addTax}\NormalTok{(c,p)}| returns
  \VERB|\NormalTok{c}| with a sales tax of \VERB|\NormalTok{p}|
  \emph{percent} added. For example,
  \VERB|\FunctionTok{addTax}\NormalTok{(}\FloatTok{2.0}\NormalTok{,}\FloatTok{9.0}\NormalTok{)}|
  returns \VERB|\FloatTok{2.18}|.

  Also develop a function \VERB|\NormalTok{subTax}| that is the inverse
  of \VERB|\NormalTok{addTax}|. That is,
  \VERB|\FunctionTok{subTax}\NormalTok{((}\FunctionTok{addTax}\NormalTok{(c,p)), p)}|
  yields \VERB|\NormalTok{c}|. For example,
  \VERB|\FunctionTok{subTax}\NormalTok{(}\FloatTok{2.18}\NormalTok{,}\FloatTok{9.0}\NormalTok{) = }\FloatTok{2.0}|.
\item
  Develop a backward recursive Scala function \VERB|\NormalTok{sumTo}|
  such that \VERB|\FunctionTok{sumTo}\NormalTok{(n)}| computes the sum
  of the integers from 1 to \VERB|\NormalTok{n}| for
  \VERB|\NormalTok{n > }\DecValTok{0}|.
\item
  Develop a Scala function \VERB|\NormalTok{sumTo2}| such that
  \VERB|\FunctionTok{sumTo2}\NormalTok{(n)}| computes the sum of the
  integers from 1 to \VERB|\NormalTok{n}| for
  \VERB|\NormalTok{n > }\DecValTok{0}|. Use a tail recursive auxilliary
  function.
\item
  Develop a backward recursive Scala function
  \VERB|\NormalTok{sumFromTo}| such that
  \VERB|\FunctionTok{sumFromTo}\NormalTok{(m,n)}| computes the sum of
  the integers from \VERB|\NormalTok{m}| to \VERB|\NormalTok{n}| for
  \VERB|\NormalTok{n >= m}|.
\item
  Develop a Scala function \VERB|\NormalTok{sumFromTo2}| such that
  \VERB|\FunctionTok{sumFromTo2}\NormalTok{(m,n)}| computes the sum of
  the integers from \VERB|\NormalTok{m}| to \VERB|\NormalTok{n}|
  \VERB|\NormalTok{n >= m}|. Use a tail recursive auxilliary function.
\item
  Suppose we have Scala functions \VERB|\NormalTok{succ}| (successor)
  and \VERB|\NormalTok{pred}| (predecessor) defined as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{succ}\NormalTok{(n: Int): Int = n + }\DecValTok{1}
    \KeywordTok{def} \FunctionTok{pred}\NormalTok{(n: Int): Int = n - }\DecValTok{1}
\end{Highlighting}
\end{Shaded}

  Develop a recursive Scala function \VERB|\NormalTok{add}| such that
  \VERB|\FunctionTok{add}\NormalTok{(m,n)}| computes
  \VERB|\NormalTok{m + n}| for two integers \VERB|\NormalTok{m}| and
  \VERB|\NormalTok{n}|. Function \VERB|\NormalTok{add}| \emph{cannot}
  use addition or subtraction operators but \emph{can} use unary
  negation, comparisons between integers, and the
  \VERB|\NormalTok{succ}| and \VERB|\NormalTok{pred}| functions defined
  above.
\item
  Develop a recursive Scala function \VERB|\NormalTok{mult}| such that
  \VERB|\FunctionTok{mult}\NormalTok{(m,n)}| computes
  \VERB|\NormalTok{m * n}| for two integers \VERB|\NormalTok{m}| and
  \VERB|\NormalTok{n}|. The function \emph{cannot} use the
  multiplication (\VERB|\NormalTok{*}|) or division
  (\VERB|\NormalTok{/}|) operators but \emph{can} use unary negation,
  comparisons between integers, and the \VERB|\NormalTok{succ}|,
  \VERB|\NormalTok{pred}|, and \VERB|\NormalTok{add}| function from the
  previous exercise.
\item
  Develop a recursive Scala function \VERB|\NormalTok{acker}| to compute
  Ackermann's function, which is a function \(A\) defined as follows for
  integers \VERB|\NormalTok{m}| and \VERB|\NormalTok{n}|:

  \begin{longtable}[]{@{}llll@{}}
  \toprule
  \endhead
  \(A(m,n)\) & \(=\) & \(n+1,\) & if \(m = 0\)\tabularnewline
  \(A(m,n)\) & \(=\) & \(A(m-1,1),\) & if \(m > 0\) and
  \(n = 0\)\tabularnewline
  \(A(m,n)\) & \(=\) & \(A(m-1,A(m,m-1)),\) & if \(m > 0\) and
  \(n > 0\)\tabularnewline
  \bottomrule
  \end{longtable}
\item
  Develop a recursive Scala function \VERB|\NormalTok{hailstone}| to
  implement the following function:

  \begin{longtable}[]{@{}llll@{}}
  \toprule
  \endhead
  \(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 \VERB|\NormalTok{hailstone}| function
  to the argument \texttt{3} would result in the following ``sequence''
  of ``calls'' and would ultimately return the result
  \VERB|\DecValTok{1}|.

\begin{Shaded}
\begin{Highlighting}[]
    \FunctionTok{hailstone}\NormalTok{(}\DecValTok{3}\NormalTok{)}
      \FunctionTok{hailstone}\NormalTok{(}\DecValTok{10}\NormalTok{)}
        \FunctionTok{hailstone}\NormalTok{(}\DecValTok{5}\NormalTok{)}
          \FunctionTok{hailstone}\NormalTok{(}\DecValTok{16}\NormalTok{)}
            \FunctionTok{hailstone}\NormalTok{(}\DecValTok{8}\NormalTok{)}
              \FunctionTok{hailstone}\NormalTok{(}\DecValTok{4}\NormalTok{)}
                \FunctionTok{hailstone}\NormalTok{(}\DecValTok{2}\NormalTok{)}
                  \FunctionTok{hailstone}\NormalTok{(}\DecValTok{1}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

  What is the domain of the \emph{hailstone} function? How do we know
  the function terminates?
\item
  Develop a Scala exponentiation function \VERB|\NormalTok{expt4}| that
  is similar to \VERB|\NormalTok{expt3}| but is tail recursive as well
  as logarithmic recursive.
\item
  Develop the following group of recursive Scala functions:

  \begin{itemize}
  \item
    \VERB|\NormalTok{test}| such that
    \VERB|\FunctionTok{test}\NormalTok{(a,b,c)}| is
    \VERB|\KeywordTok{true}| if and only if \VERB|\NormalTok{a <= b}|
    and no integer is the range from \VERB|\NormalTok{a}| to
    \VERB|\NormalTok{b}| inclusive is divisible by \VERB|\NormalTok{c}|.
  \item
    \VERB|\NormalTok{prime}| such that
    \VERB|\FunctionTok{prime}\NormalTok{(n)}| is
    \VERB|\KeywordTok{true}| if and only if \VERB|\NormalTok{n}| is a
    prime integer.
  \item
    \VERB|\NormalTok{nextPrime}| such that
    \VERB|\FunctionTok{nextPrime}\NormalTok{(n)}| returns the next prime
    integer greater than \VERB|\NormalTok{n}|
  \end{itemize}
\item
  Develop a recursive Scala function \VERB|\NormalTok{binom}| to compute
  \emph{binomial coefficients}. That is,
  \VERB|\FunctionTok{binom}\NormalTok{(n,k)}| returns \(\binom{n}{k}\)
  for integers \VERB|\NormalTok{n >= }\DecValTok{0}| and
  \VERB|\DecValTok{0}\NormalTok{ <= k <= n}|.
\item
  The time of day can be represented in Scala by the definitions

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{sealed} \KeywordTok{trait}\NormalTok{ APM }
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ AM }\KeywordTok{extends}\NormalTok{ APM }
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ PM }\KeywordTok{extends}\NormalTok{ APM }
    \KeywordTok{case} \KeywordTok{class} \FunctionTok{Time12}\NormalTok{(hours: Int, minutes: Int, apm: APM) }
\end{Highlighting}
\end{Shaded}

  where \VERB|\NormalTok{hours}| and \VERB|\NormalTok{minutes}| are
  integers such that
  \VERB|\DecValTok{1}\NormalTok{ <= hours <= }\DecValTok{12}| and
  \VERB|\DecValTok{0}\NormalTok{ <= minutes <= }\DecValTok{59}|.

  Develop a Boolean Scala function \VERB|\NormalTok{comesBefore}| that
  takes two \VERB|\NormalTok{Time12}| objects and determines whether the
  first is an earlier time than the second.

  TODO: Perhaps modify the exercise above to use the
  \VERB|\NormalTok{Ord}| trait as in the exercise below.
\item
  A date on the \emph{proleptic Gregorian calendar} (see note below) can
  be represented in Scala by the definition

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{case} \KeywordTok{class} \FunctionTok{PGDate}\NormalTok{(year: Int, month: Int, day: Int) }
\end{Highlighting}
\end{Shaded}

  with the following constraints on \emph{valid} objects:

  \begin{itemize}
  \tightlist
  \item
    \VERB|\NormalTok{year}| is any integer
  \item
    \VERB|\DecValTok{1}\NormalTok{ <= month <= }\DecValTok{12}|
  \item
    \VERB|\DecValTok{1}\NormalTok{ <= day <= }\FunctionTok{days_in_month}\NormalTok{(year,month)}|
  \end{itemize}

  Here \VERB|\FunctionTok{days_in_month}\NormalTok{(year,month)}|
  represents the number of days in the the given
  \VERB|\NormalTok{month}| (i.e.~28, 29, 30, or 31) for the given
  \VERB|\NormalTok{year}|. Remember that the number of days in February
  varies between regular and leap years.

  For the items below, write your own Scala functions. Do not use a date
  library.

  \begin{enumerate}
  \def\labelenumii{\alph{enumii}.}
  \item
    Extend class \VERB|\NormalTok{PGdate}| to implement trait
    \VERB|\NormalTok{Ord}| as defined below (and in the
    \href{../ScalaForJava/ScalaForJava.html}{\emph{Notes on Scala for
    Java Programmers}}):

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{trait}\NormalTok{ Ord \{}
        \KeywordTok{def}\NormalTok{ < (that: Any): Boolean }
        \KeywordTok{def}\NormalTok{ <=(that: Any): Boolean = }
\NormalTok{            (}\KeywordTok{this}\NormalTok{ < that) || (}\KeywordTok{this}\NormalTok{ == that) }
        \KeywordTok{def}\NormalTok{ > (that: Any): Boolean = !(}\KeywordTok{this}\NormalTok{ <= that) }
        \KeywordTok{def}\NormalTok{ >=(that: Any): Boolean = !(}\KeywordTok{this}\NormalTok{ < that) }
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

    If needed, redefine the method \VERB|\NormalTok{equals}|.

    The interpretation of \VERB|\NormalTok{d1 < d2}| is that
    \VERB|\NormalTok{d1}| is an earlier date than \VERB|\NormalTok{d2}|.
  \item
    Redefine method \VERB|\NormalTok{toString}| appropriately for
    \VERB|\NormalTok{PGDate}|.
  \item
    Develop a Scala function
    \VERB|\FunctionTok{validPGDate}\NormalTok{(d)}| that takes a
    \VERB|\NormalTok{PGDate}| object \VERB|\NormalTok{d}| and returns
    \VERB|\KeywordTok{true}| if and only if \VERB|\NormalTok{d}|
    satisfies the constraints given above.

    For example:

    \begin{itemize}
    \tightlist
    \item
      \VERB|\FunctionTok{validPGDate}\NormalTok{(}\FunctionTok{PGDate}\NormalTok{(}\DecValTok{2019}\NormalTok{,}\DecValTok{2}\NormalTok{,}\DecValTok{1}\NormalTok{)) == }\KeywordTok{true}|
    \item
      \VERB|\FunctionTok{validPGDate}\NormalTok{(}\FunctionTok{PGDate}\NormalTok{(}\DecValTok{2016}\NormalTok{,}\DecValTok{2}\NormalTok{,}\DecValTok{29}\NormalTok{)) == }\KeywordTok{true}|
    \item
      \VERB|\FunctionTok{validPGDate}\NormalTok{(}\FunctionTok{PGDate}\NormalTok{(}\DecValTok{2017}\NormalTok{,}\DecValTok{2}\NormalTok{,}\DecValTok{29}\NormalTok{)) == }\KeywordTok{false}|
    \item
      \VERB|\FunctionTok{validPGDate}\NormalTok{(}\FunctionTok{PGDate}\NormalTok{(}\DecValTok{0}\NormalTok{,}\DecValTok{0}\NormalTok{,}\DecValTok{0}\NormalTok{)) == }\KeywordTok{false}|
    \end{itemize}

    You may need to develop one or more other functions to implement the
    \VERB|\NormalTok{validPGDate}| function.
  \item
    For any \VERB|\NormalTok{PGDate}| beginning with
    (i.e.~\VERB|\NormalTok{>=}|)
    \VERB|\FunctionTok{PGDate}\NormalTok{(-}\DecValTok{4712}\NormalTok{,}\DecValTok{1}\NormalTok{,}\DecValTok{1}\NormalTok{)}|,
    develop Scala functions:

    \begin{itemize}
    \item
      \VERB|\FunctionTok{daysBetween}\NormalTok{(d1,d2)}| that takes two
      valid \VERB|\NormalTok{PGDate}| objects \VERB|\NormalTok{d1}| and
      \VERB|\NormalTok{d2}| and returns the number of days between them.
      The difference value is positive if \VERB|\NormalTok{d1 < d2}| and
      negative if \VERB|\NormalTok{d1 > d2}|.
    \item
      \VERB|\FunctionTok{addDays}\NormalTok{(d,days)}| takes a
      \VERB|\NormalTok{PGDate}| object \VERB|\NormalTok{d}| and an
      integer number of days and returns a valid
      \VERB|\NormalTok{PGDate}| object that is offset by that number of
      days. A positive offset results in a later date.
    \end{itemize}
  \end{enumerate}

  Note: The Gregorian calendar {[}Wikipedia 2019{]} was introduced by
  Pope Gregory of the Roman Catholic Church in October 1582. It replaced
  the Julian calendar system, which had been instituted in the Roman
  Empire by Julius Caesar in 46 BC. The goal of the change was to align
  the calendar year with the astronomical year.

  Some countries adopted the Gregorian calendar at that time. Other
  countries adopted it later. Some countries may never have adopted it
  officially.

  However, the Gregorian calendar system became the common calendar used
  worldwide for most civil matters. The \emph{proleptic Gregorian
  calendar} {[}Wikipedia 2019{]} extends the calendar backward in time
  from 1582. The year 1 BC becomes year 0, 2 BC becomes year -1, etc.
  The proleptic Gregorian calendar underlies the ISO 8601 standard used
  for dates and times in software systems {[}Wikipedia 2019{]}.

  Arithmetic on calendar dates is often done by converting a date to the
  Julian Day Number (JDN), doing the arithmetic on those values, and
  then converting back to the calendar date {[}Wikipedia 2019{]}.
\item
  Develop a Scala function \VERB|\NormalTok{roman}| that takes an
  \VERB|\NormalTok{Int}|) in the range from 0 to 3999 (inclusive) and
  returns the corresponding Roman numeral as a string (using capital
  letters). The function should halt with an appropriate
  \VERB|\NormalTok{sys.}\FunctionTok{error}| messages if the argument is
  below or above the range. Roman numbers use the following symbols and
  are combined by addition or subtraction of symbols.

  \begin{longtable}[]{@{}ll@{}}
  \toprule
  \endhead
  I & 1\tabularnewline
  V & 5\tabularnewline
  X & 10\tabularnewline
  L & 50\tabularnewline
  C & 100\tabularnewline
  D & 500\tabularnewline
  M & 1000\tabularnewline
  \bottomrule
  \end{longtable}

  \emph{For the purposes of this exercise, we represent the Roman
  numeral for 0 as the empty string.} The Roman numbers for integers
  1-20 are \texttt{I}, \texttt{II}, \texttt{III}, \texttt{IV},
  \texttt{V}, \texttt{VI}, \texttt{VII}, \texttt{VIII}, \texttt{IX},
  \texttt{X}, \texttt{XI}, \texttt{XII}, \texttt{XIII}, \texttt{XIV},
  \texttt{XV}, \texttt{XVI}, \texttt{XVII}, \texttt{XVII}, \texttt{XIX},
  and \texttt{XX}. Integers 40, 90, 400, and 900 are \texttt{XL},
  \texttt{XC}, \texttt{CD}, and \texttt{CM}.
\item
  Develop a Scala function

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{minf}\NormalTok{(g: (Int => Int)): Int}
\end{Highlighting}
\end{Shaded}

  that takes a function \VERB|\NormalTok{g}| and returns the smallest
  integer \VERB|\NormalTok{m}| such that
  \VERB|\DecValTok{0}\NormalTok{ <= m <= }\DecValTok{10000000}| and
  \VERB|\FunctionTok{g}\NormalTok{(m) == }\DecValTok{0}|. It should
  throw a \VERB|\NormalTok{sys.}\FunctionTok{error}| if there is no such
  integer.
\end{enumerate}

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

I wrote the first version of these notes in Fall 2013 to accompany my
lectures on recursion concepts and programming techniques for a
Lua-based course. I adapted some aspects of my earlier notes on
functional programming using Haskell {[}Cunningham 2014{]}.

I adapted the factorial, Fibonacci number, and exponentiation functions
from similar Scheme functions in the classic textbook
\href{http://mitpress.mit.edu/sicp/}{SICP} {[}Abelson 1996{]}.

I subsequently adapted these notes for use in functional or
multiparadigm programming classes using Elixir (Spring 2015), Scala
(Spring 2016), and Haskell (Summer 2016) {[}Cunningham 2016{]}.

In Summer 2016, I also incorporated the Haskell version in what is now
Chapter 9 of my Haskell-based textbook \emph{Exploring Languages using
Interpreters and Functional Programming} (ELIFP) {[}Cunningham 2018{]}.

In Spring 2019, I merged parts of ELIFP Chapter 9 and the earlier Scala
version of the notes to create the current document. I also included
some exercises from ELIFP Chapter 5.

\hypertarget{references}{%
\subsection{References}\label{references}}

\begin{description}
\tightlist
\item[{[}Abelson 1996{]}:]
Harold Abelson and Gerald Jay Sussman. \emph{Structure and
Interpretation of Computer Programs}
(\href{http://mitpress.mit.edu/sicp/}{SICP}), Second Edition, MIT Press,
1996.
\item[{[}Bird 1988{]}:]
Richard Bird and Philip Wadler. \emph{Introduction to Functional
Programming},
\href{https://usi-pl.github.io/lc/sp-2015/doc/Bird_Wadler.\%20Introduction\%20to\%20Functional\%20Programming.1ed.pdf}{First
Edition}, Prentice Hall, 1988.
\item[{[}Cunningham 2014{]}:]
H. Conrad Cunningham.
\href{https://john.cs.olemiss.edu/~hcc/csci450/notes/haskell_notes.pdf}{\emph{Notes
on Functional Programming with Haskell}}, 1993-2014.
\item[{[}Cunningham 2016{]}:]
H. Conrad Cunningham.
\href{https://john.cs.olemiss.edu/~hcc/csci555/notes/RecursionConcepts/RecursionConceptsScala.html}{Recursion
Concepts and Terminology}, 2013-2016.
\item[{[}Cunningham 2018{]}:]
H. Conrad Cunningham. Exploring Languages with Interpreters `and
Functional Programming, 2018. Available at
\url{https://john.cs.olemiss.edu/~hcc/csci450/ELIFP/ExploringLanguages.html}.
\item[{[}Wikipedia 2019{]}:]
\emph{Wikipedia}, articles on ``Gregorian Calendar'', ``Proleptic
Gregorian Calendar'', ``Julian Day'', and ``ISO 8601'', accessed on 31
January 2019.
\end{description}

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

Recursion styles (linear vs.~nonlinear, backward vs.~forward, tail, and
logarithmic), correctness (precondition, postcondition, and
termination), efficiency estimation (time and space complexity),
transformations to improve efficiency (auxiliary function, accumulator).

\end{document}