% Options for packages loaded elsewhere
\PassOptionsToPackage{unicode}{hyperref}
\PassOptionsToPackage{hyphens}{url}
%
\documentclass[
  english,
]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
  \usepackage{textcomp} % provide euro and other symbols
\else % if luatex or xetex
  \usepackage{unicode-math}
  \defaultfontfeatures{Scale=MatchLowercase}
  \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
\fi
% Use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
\IfFileExists{microtype.sty}{% use microtype if available
  \usepackage[]{microtype}
  \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\makeatletter
\@ifundefined{KOMAClassName}{% if non-KOMA class
  \IfFileExists{parskip.sty}{%
    \usepackage{parskip}
  }{% else
    \setlength{\parindent}{0pt}
    \setlength{\parskip}{6pt plus 2pt minus 1pt}}
}{% if KOMA class
  \KOMAoptions{parskip=half}}
\makeatother
\usepackage{xcolor}
\IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
\IfFileExists{bookmark.sty}{\usepackage{bookmark}}{\usepackage{hyperref}}
\hypersetup{
  pdftitle={CSci 555: Functional Programming Functional Programming in Scala Strictness and Laziness},
  pdfauthor={H. Conrad Cunningham},
  hidelinks,
  pdfcreator={LaTeX via pandoc}}
\urlstyle{same} % disable monospaced font for URLs
\usepackage{color}
\usepackage{fancyvrb}
\newcommand{\VerbBar}{|}
\newcommand{\VERB}{\Verb[commandchars=\\\{\}]}
\DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}}
% Add ',fontsize=\small' for more characters per line
\newenvironment{Shaded}{}{}
\newcommand{\AlertTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
\newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.49,0.56,0.16}{#1}}
\newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\BuiltInTok}[1]{#1}
\newcommand{\CharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\CommentTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textit{#1}}}
\newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.53,0.00,0.00}{#1}}
\newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
\newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.56,0.13,0.00}{#1}}
\newcommand{\DecValTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.73,0.13,0.13}{\textit{#1}}}
\newcommand{\ErrorTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
\newcommand{\ExtensionTok}[1]{#1}
\newcommand{\FloatTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.02,0.16,0.49}{#1}}
\newcommand{\ImportTok}[1]{#1}
\newcommand{\InformationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
\newcommand{\NormalTok}[1]{#1}
\newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.40,0.40,0.40}{#1}}
\newcommand{\OtherTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{#1}}
\newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.74,0.48,0.00}{#1}}
\newcommand{\RegionMarkerTok}[1]{#1}
\newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.73,0.40,0.53}{#1}}
\newcommand{\StringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\VariableTok}[1]{\textcolor[rgb]{0.10,0.09,0.49}{#1}}
\newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\WarningTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\setlength{\emergencystretch}{3em} % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{-\maxdimen} % remove section numbering
\usepackage{caption}
\DeclareCaptionLabelFormat{nolabel}{}
\captionsetup{labelformat=nolabel}
\ifxetex
  % Load polyglossia as late as possible: uses bidi with RTL langages (e.g. Hebrew, Arabic)
  \usepackage{polyglossia}
  \setmainlanguage[]{english}
\else
  \usepackage[shorthands=off,main=english]{babel}
\fi

\title{CSci 555: Functional Programming\\
Functional Programming in Scala\\
Strictness and Laziness}
\author{\textbf{H. Conrad Cunningham}}
\date{\textbf{2 May 2019}}

\begin{document}
\maketitle

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

\textbf{Note:} This set of notes accompanies my lectures on Chapter 5 of
the book \emph{Functional Programming in Scala} {[}Chiusano 2015{]}
(i.e.~the Red Book).

\textbf{Prerequisites}: In this set of notes, I assume the reader is
familiar with the programming concepts and Scala features covered in my
\emph{Notes on Scala for Java Programmers} {[}Cunningham 2019a{]},
\emph{Recursion Styles, Correctness, and Efficiency (Scala Version)}
{[}Cunningham 2019b{]}, \emph{Type System Concepts} {[}Cunningham
2019c{]}, \emph{Functional Data Structures} {[}Cunningham 2019d{]}, and
\emph{Handling Errors without Exceptions} {[}Cunningham 2019e{]}.

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

\newpage
\setcounter{section}{4}

\hypertarget{strictness-and-laziness}{%
\section{Strictness and Laziness}\label{strictness-and-laziness}}

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

The big idea we discuss in this chapter is how we can exploit nonstrict
functions to increase efficiency, increase code reuse, and improve
modularity in functional programs.

\hypertarget{motivation}{%
\subsubsection{Motivation}\label{motivation}}

In our discussion {[}Cunningham 2019d{]} of Chapter 3 of
\emph{Functional Programming in Scala} {[}Chiusano 2015{]}, we examined
purely functional data structures---in particular, the immutable, singly
linked list.

We also examined the design and use of several bulk operations---such as
\VERB|\NormalTok{map}|, \VERB|\NormalTok{filter}|,
\VERB|\NormalTok{foldLeft}|, and \VERB|\NormalTok{foldRight}|. Each of
these operations makes a pass over the input list and often constructs a
new list for its output.

Consider the Scala expression

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    List(}\DecValTok{10}\NormalTok{,}\DecValTok{20}\NormalTok{,}\DecValTok{30}\NormalTok{,}\DecValTok{40}\NormalTok{,}\DecValTok{50}\NormalTok{).}\FunctionTok{map}\NormalTok{(_/}\DecValTok{10}\NormalTok{).}\FunctionTok{filter}\NormalTok{(_%}\DecValTok{2}\NormalTok{ == }\DecValTok{1}\NormalTok{).}\FunctionTok{map}\NormalTok{(_*}\DecValTok{100}\NormalTok{) }
\end{Highlighting}
\end{Shaded}

that generates the result:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    List(}\DecValTok{100}\NormalTok{, }\DecValTok{300}\NormalTok{, }\DecValTok{500}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

The evaluation of the expression requires three passes through the list.
However, we could code a specialized function that does the same work in
one pass.

\begin{Shaded}
\begin{Highlighting}[]
        \KeywordTok{def} \FunctionTok{mfm}\NormalTok{(xs: List[Int]): List[Int] = xs }\KeywordTok{match}\NormalTok{ \{}
          \KeywordTok{case}\NormalTok{ Nil     => Nil }
          \KeywordTok{case}\NormalTok{ (y::ys) => }
            \KeywordTok{val}\NormalTok{ z = y / }\DecValTok{10} 
            \KeywordTok{if}\NormalTok{ (z % }\DecValTok{2}\NormalTok{ == }\DecValTok{1}\NormalTok{) (z*}\DecValTok{100}\NormalTok{) :: }\FunctionTok{mfm}\NormalTok{(ys) }\KeywordTok{else} \FunctionTok{mfm}\NormalTok{(ys) }
\NormalTok{        \}}
\end{Highlighting}
\end{Shaded}

Note: In this chapter, we use the method-chaining formulation of
\VERB|\NormalTok{List}| from the standard library, not the one we
developed in the ``Functional Data Structures'' chapter.
\VERB|\NormalTok{::}| constructs a list with its left operand as the
head value and its right operand as the tail list.

It would be convenient if we could instead get a result similar to
\VERB|\NormalTok{mfm}| by composing simpler functions like
\VERB|\NormalTok{map}| and \VERB|\NormalTok{filter}|.

Can we do this?

We can by taking advantage of \emph{nonstrict} functions to build a
\emph{lazy} list structure. We introduced the concepts of strict and
nonstrict functions in Chapter 4 {[}Cunningham 2019e{]}; we elaborate on
them in this chapter.

\hypertarget{what-are-strictness-and-nonstrictness}{%
\subsubsection{What are strictness and
nonstrictness?}\label{what-are-strictness-and-nonstrictness}}

If the evaluation of an expression runs forever or throws an exception
instead of returning an explicit value, we say the expression does not
\emph{terminate}---or that it evaluates to \emph{bottom} (written
symbolically as \(\bot\)).

A function \VERB|\NormalTok{f}| is \emph{strict} if
\VERB|\FunctionTok{f}\NormalTok{(x)}| evaluates to bottom for all
\VERB|\NormalTok{x}| that themselves evaluate to bottom. That is,
\texttt{f(}\(\bot\)\texttt{)} \VERB|\NormalTok{==}| \(\bot\). A strict
function's argument must always have a value for the function to have a
value.

A function is \emph{nonstrict} (sometimes called \emph{lenient}) if it
is not strict. That is, \texttt{f(}\(\bot\)\texttt{)}
\VERB|\NormalTok{!=}| \(\bot\). The function can sometimes have value
even if its argument does not have a value.

For multiparameter functions, we sometimes apply these terms to
individual parameters. A \emph{strict} parameter of a function must
always be evaluated by the function. A \emph{nonstrict} parameter of a
function may sometimes be evaluated by the function and sometimes not.

\hypertarget{exploring-nonstrictness}{%
\subsubsection{Exploring nonstrictness}\label{exploring-nonstrictness}}

By default, Scala functions are strict.

However, some operations are nonstrict. For example, the
``short-circuited'' \VERB|\NormalTok{&&}| operation is nonstrict; it
does not evaluate its second operand when the first operation is
\VERB|\KeywordTok{false}|. Similarly,
\VERB|\NormalTok{\VerbBar{}\VerbBar{}}| does not evaluate its second
operand when its first operand is \VERB|\KeywordTok{true}|.

Consider the \VERB|\KeywordTok{if}| expression as a ternary operator.
When the condition operand evaluates to \VERB|\KeywordTok{true}|, the
operator evaluates the second (i.e.~then) operand but not the third
(i.e.~else) operand. Similarly, when the condition is
\VERB|\KeywordTok{false}|, the operator evaluates the third operand but
not the second.

We could implement \VERB|\KeywordTok{if}| as a function as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ if2[A](cond: Boolean, onTrue: () => A, }
\NormalTok{               onFalse: () => A): A =}
        \KeywordTok{if}\NormalTok{ (cond) }\FunctionTok{onTrue}\NormalTok{() }\KeywordTok{else} \FunctionTok{onFalse}\NormalTok{()}
\end{Highlighting}
\end{Shaded}

Then we can call \VERB|\NormalTok{if2}| as in the code fragment

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{val}\NormalTok{ age = }\DecValTok{21}
    \FunctionTok{if2}\NormalTok{(age >= }\DecValTok{18}\NormalTok{, () => }\FunctionTok{println}\NormalTok{(}\StringTok{"Can vote"}\NormalTok{), }
\NormalTok{                   () => }\FunctionTok{println}\NormalTok{(}\StringTok{"Cannot vote"}\NormalTok{))}
\end{Highlighting}
\end{Shaded}

and get the output:

\begin{verbatim}
    Can vote
\end{verbatim}

The parameter type \VERB|\NormalTok{() => A}| means that the
corresponding argument is passed as a parameterless function that
returns a value of type \VERB|\NormalTok{A}|. This function wraps the
expression, which is not evaluated before the call. This function is an
explicitly specified \emph{thunk}.

When the value is needed, then the called function must \emph{force} the
evaluation of the thunk by calling it explicitly, for example by using
\VERB|\FunctionTok{onTrue}\NormalTok{()}|.

To use the approach above, the caller must explicitly create the thunk.
However, as we saw in the previous chapter, Scala provides
\emph{call-by-name} parameter passing that relieves the caller of this
requirement in most circumstances. We can thus rewrite
\VERB|\NormalTok{if2}| as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ if2[A](cond: Boolean, onTrue: => A, onFalse: => A): A =}
        \KeywordTok{if}\NormalTok{ (cond) onTrue }\KeywordTok{else}\NormalTok{ onFalse}
\end{Highlighting}
\end{Shaded}

The \VERB|\NormalTok{onTrue: => A}| notation makes the argument
expression a by-name parameter. Scala automatically creates the thunk
for parameter \VERB|\NormalTok{onTrue}| and enables it to be referenced
within the function without explicitly forcing its evaluation, for
example by using \VERB|\NormalTok{onTrue}|.

An advantage of call-by-name parameter passing is that the evaluation of
an expression can be delayed until its value is referenced, which may be
never. A disadvantage is that the expression will be evaluated every
time it is referenced.

To determine how to address this disadvantage, consider function

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{maybeTwice}\NormalTok{(b: Boolean, i: => Int) = }\KeywordTok{if}\NormalTok{ (b) i + i }\KeywordTok{else} \DecValTok{0}
\end{Highlighting}
\end{Shaded}

which can be called as

\begin{Shaded}
\begin{Highlighting}[]
    \FunctionTok{println}\NormalTok{(}\FunctionTok{maybeTwice}\NormalTok{(}\KeywordTok{true}\NormalTok{, \{}\FunctionTok{println}\NormalTok{(}\StringTok{"hi"}\NormalTok{); }\DecValTok{1}\NormalTok{ + }\DecValTok{41}\NormalTok{\}))}
\end{Highlighting}
\end{Shaded}

to generate output:

\begin{verbatim}
    hi
    hi
    84
\end{verbatim}

Note that the argument expression \VERB|\NormalTok{i}| is evaluated
twice.

We can address this issue by defining a new variable and initializing it
\emph{lazily} to have the same value as the by-name parameter. We do
this by declaring the temporary variable as a
\VERB|\KeywordTok{lazy} \KeywordTok{val}|. The temporary variable will
not be initialized until it is referenced, but it \emph{caches} the
calculated value so that it can be used without reevaluation on
subsequent references.

We can rewrite \VERB|\NormalTok{maybeTwice}| as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{maybeTwice2}\NormalTok{(b: Boolean, i: => Int) = \{}
        \KeywordTok{lazy} \KeywordTok{val}\NormalTok{ j = i }
        \KeywordTok{if}\NormalTok{ (b) j+j }\KeywordTok{else} \DecValTok{0}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

Now calling it as

\begin{Shaded}
\begin{Highlighting}[]
    \FunctionTok{println}\NormalTok{(}\FunctionTok{maybeTwice2}\NormalTok{(}\KeywordTok{true}\NormalTok{, \{}\FunctionTok{println}\NormalTok{(}\StringTok{"hi"}\NormalTok{); }\DecValTok{1}\NormalTok{ + }\DecValTok{41}\NormalTok{\}))}
\end{Highlighting}
\end{Shaded}

generates output:

\begin{verbatim}
    hi
    84
\end{verbatim}

This technique of caching the result of the evaluation gives us
\emph{call-by-need} parameter passing as it is called in Haskell and
other lazily evaluated languages.

\hypertarget{lazy-lists}{%
\subsection{Lazy Lists}\label{lazy-lists}}

Now let's return to the problem discussed in the Motivation subsection.
How can we use laziness to improve efficiency and modularity of our
programs?

In this section, we answer this question by developing \emph{lazy lists}
or \emph{streams}. These allow us to carry out multiple operations on a
list without always making multiple passes over the elements.

Consider a simple ``stream'' algebraic data type
\VERB|\NormalTok{StreamC}|. A nonempty stream consists of a head and a
tail, both of which must be nonstrict.

Note: The \emph{Functional Programming in Scala} book uses algebraic
data type \VERB|\NormalTok{Stream}|, which differs from the
implementation of the similar \VERB|\NormalTok{Stream}| type in Scala's
standard library. To avoid conflicts with the standard library type,
these notes use \VERB|\NormalTok{StreamC}|.

For technical reasons, Scala does not allow by-name parameters in the
constructors for case classes. Thus these components must be explicitly
defined thunks whose evaluations are explicitly forced when their values
are required.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{import}\NormalTok{ StreamC._}
        
    \KeywordTok{sealed} \KeywordTok{trait}\NormalTok{ StreamC[+A]}
    \KeywordTok{case} \KeywordTok{object}\NormalTok{ Empty }\KeywordTok{extends}\NormalTok{ StreamC[Nothing]}
    \KeywordTok{case} \KeywordTok{class}\NormalTok{ Cons[+A](h: () => A, t: () => StreamC[A]) }
        \KeywordTok{extends}\NormalTok{ StreamC[A]}

    \KeywordTok{object}\NormalTok{ StreamC \{}
        \KeywordTok{def}\NormalTok{ cons[A](hd: => A, tl: => StreamC[A]): StreamC[A] = \{}
            \KeywordTok{lazy} \KeywordTok{val}\NormalTok{ head = hd  }\CommentTok{// cache values once computed}
            \KeywordTok{lazy} \KeywordTok{val}\NormalTok{ tail = tl}
            \FunctionTok{Cons}\NormalTok{(() => head, () => tail)  }\CommentTok{// create thunks for Cons}
\NormalTok{        \}}
        \KeywordTok{def}\NormalTok{ empty[A]: StreamC[A] = Empty}
        \KeywordTok{def}\NormalTok{ apply[A](as: A*): StreamC[A] =}
            \KeywordTok{if}\NormalTok{ (as.}\FunctionTok{isEmpty}\NormalTok{) }
\NormalTok{                empty }
            \KeywordTok{else} 
                \FunctionTok{cons}\NormalTok{(as.}\FunctionTok{head}\NormalTok{, }\FunctionTok{apply}\NormalTok{(as.}\FunctionTok{tail}\NormalTok{: _*))}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

\hypertarget{smart-constructors-and-memoized-streams}{%
\subsubsection{Smart constructors and memoized
streams}\label{smart-constructors-and-memoized-streams}}

In the \VERB|\NormalTok{StreamC}| data type, we define two \emph{smart
constructors} to create new streams. By convention, these are functions
defined in the companion object with the same names as the corresponding
type constructors except they begin with a lowercase letter. They
construct a data type object, ensuring that the needed integrity
invariants are established. In the \VERB|\NormalTok{StreamC}| type,
these take care of the routine work of creating the thunks, caching the
values, and enabling transparent use of the parameters.

Smart constructor function \VERB|\NormalTok{cons}| takes the head and
tail of the new \VERB|\NormalTok{StreamC}| as by-name parameters,
equates these to lazy variables to cache their values, and then creates
a \VERB|\NormalTok{Cons}| cell. The \VERB|\NormalTok{h}| and
\VERB|\NormalTok{t}| fields of the \VERB|\NormalTok{Cons}| are
explicitly defined thunks wrapping the head and the tail of the stream,
respectively.

The evaluation of the thunk \VERB|\NormalTok{h}| of a
\VERB|\NormalTok{Cons}| cell returns the value of the lazy variable
\VERB|\NormalTok{head}| in the cell's closure. If this is the first
access to \VERB|\NormalTok{head}|, then the access causes the
corresponding by-name argument \VERB|\NormalTok{hd}| to be evaluated and
cached in \VERB|\NormalTok{head}|. Subsequent evaluations of
\VERB|\NormalTok{h}| get the cached value.

The evaluation of the thunk \VERB|\NormalTok{t}| of a
\VERB|\NormalTok{Cons}| cell causes similar effects on the lazy variable
\VERB|\NormalTok{tail}| and the corresponding by-name argument
\VERB|\NormalTok{tl}|. However, the value of this argument is itself a
\VERB|\NormalTok{StreamC}|, which may include lazily evaluated fields.

Smart constructor function \VERB|\NormalTok{empty}| just creates an
\VERB|\NormalTok{Empty}| \VERB|\NormalTok{StreamC}|.

We define both smart constructors to have return type
\VERB|\NormalTok{StreamC[A]}|. In addition to establishing the needed
invariants, the use of the smart constructors helps Scala's type
inference mechanism infer the \VERB|\NormalTok{StreamC}| type (which is
what we usually want) instead of the subtypes associated with the case
class/object constructors (which is what often will be inferred in
Scala's object-oriented type system).

Convenience function \VERB|\NormalTok{apply}| takes a sequence of zero
or more arguments and creates the corresponding
\VERB|\NormalTok{StreamC}|.

If a function examines or traverses a \VERB|\NormalTok{StreamC}|, it
must explicitly force evaluation of the thunks. In general, we should
encapsulate such accesses within functions defined as a part of the
\VERB|\NormalTok{StreamC}| implementation. (That is, we should practice
\emph{information hiding}, hide this design detail as a \emph{secret} of
the \VERB|\NormalTok{StreamC}| implementation as we discuss in the notes
on abstract data types {[}Cunningham 2019f{]}.)

An example of this is function \VERB|\NormalTok{headOption}| that
optionally extracts the head of the stream.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ headOption: Option[A] = }\KeywordTok{this} \KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case}\NormalTok{ Empty     => None}
        \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(h,t) => Some(}\FunctionTok{h}\NormalTok{()) }\CommentTok{// force thunk}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

It explicitly forces evaluation of the thunk and thus enables code that
called it to work with the values.

This technique for caching the value of the by-name argument is an
example of memoizing the function. In general, \emph{memoization} is an
implementation technique in which a function stores the return value
computed for certain arguments. Instead of recomputing the value on a
subsequent call, the function just returns the cached values. This
technique uses memory space to (potentially) save computation time
later.

\hypertarget{helper-functions}{%
\subsubsection{Helper functions}\label{helper-functions}}

Now let's define a few functions that help us manipulate streams. We
implement these as methods on the \VERB|\NormalTok{StreamC}| trait.

First, let's define a function \VERB|\NormalTok{toList}| that takes a
\VERB|\NormalTok{StreamC}| (as its implicit argument) and constructs the
corresponding Scala \VERB|\NormalTok{List}|. A standard backward
recursive method can be defined as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ toListRecursive: List[A] = }\KeywordTok{this} \KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(h,t) => }\FunctionTok{h}\NormalTok{() :: }\FunctionTok{t}\NormalTok{().}\FunctionTok{toListRecursive} \CommentTok{// force thunks}
        \KeywordTok{case}\NormalTok{ _         => List()}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

Of course, this method may suffer from stack overflow for long streams.
We can remedy this by using a tail recursive auxiliary function that
uses an accumulator to build up the list in reverse order and then
reverses the constructed list.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ toList: List[A] = \{}
\NormalTok{        @annotation.}\FunctionTok{tailrec}
        \KeywordTok{def} \FunctionTok{go}\NormalTok{(s: StreamC[A], acc: List[A]): List[A] = s }\KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(h,t) => }\FunctionTok{go}\NormalTok{(}\FunctionTok{t}\NormalTok{(), }\FunctionTok{h}\NormalTok{() :: acc) }\CommentTok{// force thunks}
            \KeywordTok{case}\NormalTok{ _         => acc}
\NormalTok{        \}}
        \FunctionTok{go}\NormalTok{(}\KeywordTok{this}\NormalTok{, List()).}\FunctionTok{reverse}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

To avoid the \VERB|\NormalTok{reverse}|, we could instead build up the
list in a mutable \VERB|\NormalTok{ListBuffer}| using a loop and then,
when finished, convert the buffer to an immutable
\VERB|\NormalTok{List}|. We preserve the \emph{purity} of the
\VERB|\NormalTok{toList}| function by encapsulating use of the mutable
buffer inside the function.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ toListFast: List[A] = \{}
        \KeywordTok{val}\NormalTok{ buf = }\KeywordTok{new}\NormalTok{ collection.}\FunctionTok{mutable}\NormalTok{.}\FunctionTok{ListBuffer}\NormalTok{[A]}
\NormalTok{        @annotation.}\FunctionTok{tailrec}
        \KeywordTok{def} \FunctionTok{go}\NormalTok{(s: StreamC[A]): List[A] = s }\KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(h,t) =>}
\NormalTok{                buf += }\FunctionTok{h}\NormalTok{() }\CommentTok{// force head thunk, add to end of buffer}
                \FunctionTok{go}\NormalTok{(}\FunctionTok{t}\NormalTok{())    }\CommentTok{// force tail thunk, process recursively}
            \KeywordTok{case}\NormalTok{ _ => buf.}\FunctionTok{toList}  \CommentTok{// convert buffer to immutable list}
\NormalTok{        \}}
        \FunctionTok{go}\NormalTok{(}\KeywordTok{this}\NormalTok{)}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

Next, let's define function \VERB|\NormalTok{take}| to return the first
\VERB|\NormalTok{n}| elements from a \VERB|\NormalTok{StreamC}| and
function \VERB|\NormalTok{drop}| to skip the first \VERB|\NormalTok{n}|
elements.

We can define method \VERB|\NormalTok{take}| using a standard backward
recursive form that matches on the structure of the implicit argument.
However, we must be careful not to evaluate either the head or the tail
thunks unnecessarily (e.g.~by treating the
\VERB|\NormalTok{n == }\DecValTok{1}| and
\VERB|\NormalTok{n == }\DecValTok{0}| cases specially).

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{take}\NormalTok{(n: Int): StreamC[A] = }\KeywordTok{this} \KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(h, t) }\KeywordTok{if}\NormalTok{ n > }\DecValTok{1}\NormalTok{  => }\FunctionTok{cons}\NormalTok{(}\FunctionTok{h}\NormalTok{(), }\FunctionTok{t}\NormalTok{().}\FunctionTok{take}\NormalTok{(n - }\DecValTok{1}\NormalTok{))}
        \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(h, _) }\KeywordTok{if}\NormalTok{ n == }\DecValTok{1}\NormalTok{ => }\FunctionTok{cons}\NormalTok{(}\FunctionTok{h}\NormalTok{(), empty)}
        \KeywordTok{case}\NormalTok{ _ => empty  }\CommentTok{// stream empty or n < 1}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

Function \VERB|\NormalTok{take}| does its work \emph{incrementally}. The
recursive leg of the definition (i.e.~the first leg) returns a
\VERB|\NormalTok{Cons}| cell with the recursive call to
\VERB|\NormalTok{take}| embedded in the lazily evaluated tail field. It
will only be evaluated if its value is required.

We can define method \VERB|\NormalTok{drop}| to recursively calling
\VERB|\NormalTok{drop}| on the forced tail. This yields the following
tail recursive function.

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    @annotation.}\FunctionTok{tailrec}
    \KeywordTok{final} \KeywordTok{def} \FunctionTok{drop}\NormalTok{(n: Int): StreamC[A] = }\KeywordTok{this} \KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(_, t) }\KeywordTok{if}\NormalTok{ n > }\DecValTok{0}\NormalTok{ => }\FunctionTok{t}\NormalTok{().}\FunctionTok{drop}\NormalTok{(n - }\DecValTok{1}\NormalTok{)}
        \KeywordTok{case}\NormalTok{ _ => }\KeywordTok{this}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

Unlike \VERB|\NormalTok{take}|, \VERB|\NormalTok{drop}| is not
incremental. The recursive call is not lazily evaluated.

Finally, let's also define method \VERB|\NormalTok{takeWhile}| to return
all starting elements of the \VERB|\NormalTok{StreamC}| that satisfy the
given predicate.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{takeWhile}\NormalTok{(p: A => Boolean): StreamC[A] = }\KeywordTok{this} \KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(h,t) }\KeywordTok{if} \FunctionTok{p}\NormalTok{(}\FunctionTok{h}\NormalTok{()) => }\FunctionTok{cons}\NormalTok{(}\FunctionTok{h}\NormalTok{(), }\FunctionTok{t}\NormalTok{() takeWhile p)}
        \KeywordTok{case}\NormalTok{ _ => empty}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

In the first case, we apply method \VERB|\NormalTok{takeWhile}| as an
infix operator.

\hypertarget{separating-program-description-from-evaluation}{%
\subsection{Separating Program Description from
Evaluation}\label{separating-program-description-from-evaluation}}

One of the fundamental design concepts in software engineering and
programming is \emph{separation of concerns}. A concern is some set of
information that affects the design and implementation of a software
system {[}Wikipedia 2019a{]}. We identify the key concerns in a software
design and try to keep them separate and independent from each other.
The goal is to implement the parts independently and then combine the
parts to form a complete solution.

We apply separation of concerns in modular programming and abstract data
types as \emph{information hiding} {[}Cunningham 2019f{]} {[}Parnas
1972{]} {[}Wikipedia 2019b{]}. We hide the \emph{secrets} of how a
module is implemented (e.g.~what algorithms and data structures are
used, what specific operating system or hardware devices are used, etc.)
from the external users of the module or data type. We encapsulate the
secrets behind an \emph{abstract interface} {[}Britton 1981{]}
{[}Cunningham 2019f{]}.

We also apply separation of concerns in software architecture for
computing applications. For example, we try to keep an application's
\emph{business logic} (i.e.~specific knowledge about the application
area) separate from its user interface such as described by the
\emph{Model-View-Controller} (MVC) architectural design pattern
{[}Wikipedia 2019c{]} commonly used in Web applications.

In functional programming, we also apply separation of concerns by
seeking to \emph{keep the description of computations separate from
their evaluation} (execution). Examples include:

\begin{itemize}
\item
  first-class functions that express computations in their bodies but
  which must be supplied arguments before they execute
\item
  use of \VERB|\NormalTok{Option}| or \VERB|\NormalTok{Either}| to
  express that an error has occurred but deferring the handling of the
  error to other parts of the program
\item
  use of \VERB|\NormalTok{StreamC}| operators to assemble a computation
  that generates a sequence without actually running the computation
  until later when its result in needed
\end{itemize}

\hypertarget{laziness-promotes-reuse}{%
\subsubsection{Laziness promotes reuse}\label{laziness-promotes-reuse}}

In general, lazy evaluation enables us to separate the description of an
expression from the evaluation of the expression. It enables us to to
describe a ``larger'' expression than we need and then to only evaluate
the portion that we actually need. This offers us the potential for
greater \emph{code reuse}.

Note: For a classic discussion of how higher-order and first-class
functions and lazy evaluation promote software modularity and reuse, see
the John Hughes paper ``Why Functional Programming Matters'' {[}Hughes
1989{]}.

Consider a method \VERB|\NormalTok{exists}| on
\VERB|\NormalTok{StreamC}| that checks whether an element matching a
Boolean function \VERB|\NormalTok{p}| occurs in the stream. We can
define this using an explicit tail recursion as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{exists}\NormalTok{(p: A => Boolean): Boolean = }\KeywordTok{this} \KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(h,t) => }\FunctionTok{p}\NormalTok{(}\FunctionTok{h}\NormalTok{()) || }\FunctionTok{t}\NormalTok{().}\FunctionTok{exists}\NormalTok{(p)}
        \KeywordTok{case}\NormalTok{ _         => }\KeywordTok{false}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

Given that \VERB|\NormalTok{\VerbBar{}\VerbBar{}}| is nonstrict in its
second argument, this function terminates and returns
\VERB|\KeywordTok{true}| as soon as it finds the first element that
makes \VERB|\NormalTok{p}| true. Because the stream holds the tail in a
\VERB|\KeywordTok{lazy} \KeywordTok{val}|, it is only evaluated when
needed. So \VERB|\NormalTok{exists}| does not evaluate the stream past
the first occurrence.

As with the \VERB|\NormalTok{List}| data type in Chapter 3, we can
define a more general method \VERB|\NormalTok{foldRight}| on
\VERB|\NormalTok{StreamC}| to represent the pattern of computation
exhibited by \VERB|\NormalTok{exists}|.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ foldRight[B](z: => B)(f: (A, => B) => B): B = }\KeywordTok{this} \KeywordTok{match}\NormalTok{ \{}
        \KeywordTok{case} \FunctionTok{Cons}\NormalTok{(h,t) => }\FunctionTok{f}\NormalTok{(}\FunctionTok{h}\NormalTok{(), }\FunctionTok{t}\NormalTok{().}\FunctionTok{foldRight}\NormalTok{(z)(f)) }
        \KeywordTok{case}\NormalTok{ _         => z}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

The notation \VERB|\NormalTok{=> B}| in the second parameter of
combining function \VERB|\NormalTok{f}| takes its second argument
by-name and, hence, may not evaluate it in all circumstances. If
\VERB|\NormalTok{f}| does not evaluate its second argument, then the
recursion terminates. Thus the overall \VERB|\NormalTok{foldRight}|
computation can terminate before it completes the complete traversal
through the stream.

We can now redefine \VERB|\NormalTok{exists}| to use the more general
function as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{exists2}\NormalTok{(p: A => Boolean): Boolean =}
        \FunctionTok{foldRight}\NormalTok{(}\KeywordTok{false}\NormalTok{)((a, b) => }\FunctionTok{p}\NormalTok{(a) || b) }
\end{Highlighting}
\end{Shaded}

Here parameter \VERB|\NormalTok{b}| represents the unevaluated recursive
step that folds the tail of the stream. If
\VERB|\FunctionTok{p}\NormalTok{(a)}| returns \VERB|\KeywordTok{true}|,
then \VERB|\NormalTok{b}| is not evaluated and the computation
terminates early.

Caveat: The second version of \VERB|\NormalTok{exists}| illustrates how
we can use a general function to represent a variety of more specific
computations. But, for a large stream in which all elements evaluate to
\VERB|\KeywordTok{false}|, this version is not stack safe.

Because the \VERB|\NormalTok{foldRight}| method on
\VERB|\NormalTok{StreamC}| can terminate its traversal early, we can use
it to implement \VERB|\NormalTok{exists}| efficiently. Unfortunately, we
cannot implement the \VERB|\NormalTok{List}| version of
\VERB|\NormalTok{exists}| efficiently in terms of the
\VERB|\NormalTok{List}| version of \VERB|\NormalTok{foldRight}|. We must
implement a specialized recursive version of \VERB|\NormalTok{exists}|
to get early termination.

\emph{Laziness thus enhances our ability to reuse code.}

\hypertarget{incremental-computations}{%
\subsubsection{Incremental
computations}\label{incremental-computations}}

Now, let's flesh out the \VERB|\NormalTok{StreamC}| trait and implement
the basic \VERB|\NormalTok{map}|, \VERB|\NormalTok{filter}|,
\VERB|\NormalTok{append}|, and \VERB|\NormalTok{flatMap}| methods using
the general function \VERB|\NormalTok{foldRight}|, as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ map[B](f: A => B): StreamC[B] =}
        \FunctionTok{foldRight}\NormalTok{(empty[B])((h,t) => }\FunctionTok{cons}\NormalTok{(}\FunctionTok{f}\NormalTok{(h), t))}
            
    \KeywordTok{def} \FunctionTok{filter}\NormalTok{(p: A => Boolean): StreamC[A] =}
        \FunctionTok{foldRight}\NormalTok{(empty[A])((h,t) => }\KeywordTok{if}\NormalTok{ (}\FunctionTok{p}\NormalTok{(h)) }\FunctionTok{cons}\NormalTok{(h, t) }\KeywordTok{else}\NormalTok{ t)}
            
    \KeywordTok{def}\NormalTok{ append[B >: A](s: => StreamC[B]): StreamC[B] =}
        \FunctionTok{foldRight}\NormalTok{(s)((h,t) => }\FunctionTok{cons}\NormalTok{(h,t))}

    \KeywordTok{def}\NormalTok{ flatMap[B](f: A => StreamC[B]): StreamC[B] =}
        \FunctionTok{foldRight}\NormalTok{(empty[B])((h,t) => }\FunctionTok{f}\NormalTok{(h) append t)}
\end{Highlighting}
\end{Shaded}

These implementations are \emph{incremental}. They do not fully generate
all their answers. No computation takes place until some other
computation examines the elements of the output
\VERB|\NormalTok{StreamC}| and then only enough elements are generated
to give the requested result.

Because of their incremental nature, we can call these functions one
after another without fully generating the intermediate results.

We can now address the problem raised in the Introduction section of
these notes. There we asked the question of how can we compute the
result of the expression

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    List(}\DecValTok{10}\NormalTok{,}\DecValTok{20}\NormalTok{,}\DecValTok{30}\NormalTok{,}\DecValTok{40}\NormalTok{,}\DecValTok{50}\NormalTok{).}\FunctionTok{map}\NormalTok{(_/}\DecValTok{10}\NormalTok{).}\FunctionTok{filter}\NormalTok{(_%}\DecValTok{2}\NormalTok{ == }\DecValTok{1}\NormalTok{).}\FunctionTok{map}\NormalTok{(_*}\DecValTok{100}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

without producing two unneeded intermediate lists.

The \VERB|\NormalTok{StreamC}| expression

\begin{Shaded}
\begin{Highlighting}[]
    \FunctionTok{StreamC}\NormalTok{(}\DecValTok{10}\NormalTok{,}\DecValTok{20}\NormalTok{,}\DecValTok{30}\NormalTok{,}\DecValTok{40}\NormalTok{,}\DecValTok{50}\NormalTok{).}\FunctionTok{map}\NormalTok{(_/}\DecValTok{10}\NormalTok{).}\FunctionTok{filter}\NormalTok{(_%}\DecValTok{2}\NormalTok{ == }\DecValTok{1}\NormalTok{).}
        \FunctionTok{map}\NormalTok{(_*}\DecValTok{100}\NormalTok{).}\FunctionTok{toList}
\end{Highlighting}
\end{Shaded}

generates the result:

\begin{verbatim}
    List(100, 300, 500)
\end{verbatim}

which is the same as the \VERB|\NormalTok{List}| expression. The
expression looks the same except that we create a
\VERB|\NormalTok{StreamC}| initially instead of a
\VERB|\NormalTok{List}| and we call \VERB|\NormalTok{toList}| to force
evaluation of stream at the end.

When executed, the lazy evaluation interleaves two
\VERB|\NormalTok{map}|, the \VERB|\NormalTok{filter}|, and the
\VERB|\NormalTok{toList}| transformations. The computation does not
fully instantiate any intermediate streams. It is a similar interleaving
to what we did in the special purpose function \VERB|\NormalTok{mfm}| in
the introduction.

(For a more detailed discussion of this interleaving, see Listing 5.3 in
the \emph{Functional Programming in Scala} book {[}Chiusano 2015{]}.)

Because stream computations do not generate intermediate streams in
full, we are free to use stream operations in ways that might seem
counterintuitive at first. For example, we can use
\VERB|\NormalTok{filter}| (which seems to process the entire stream) to
implement \VERB|\NormalTok{find}|, a function to return the first
occurrence of an element in a stream that satisfies a given predicate,
as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{find}\NormalTok{(p: A => Boolean): Option[A] = }\FunctionTok{filter}\NormalTok{(p).}\FunctionTok{headOption}
\end{Highlighting}
\end{Shaded}

The incremental nature of these computations can sometimes save memory.
The computation may only need a small amount of working memory; the
garbage collector can quickly recover working memory that the current
step does not need.

Of course, some computations may require more intermediate elements and
each element may itself require a large amount of memory, so not all
computations are as well-behaved as the examples in this section.

\hypertarget{for-comprehensions-on-streams}{%
\subsubsection{For comprehensions on
streams}\label{for-comprehensions-on-streams}}

Given that we have defined \VERB|\NormalTok{map}|,
\VERB|\NormalTok{filter}|, and \VERB|\NormalTok{flatMap}|, we can now
use sequence comprehensions on our \VERB|\NormalTok{StreamC}| data. For
example, the code fragment

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{val}\NormalTok{ seq = }\KeywordTok{for}\NormalTok{ (x <- }\FunctionTok{StreamC}\NormalTok{(}\DecValTok{1}\NormalTok{,}\DecValTok{2}\NormalTok{,}\DecValTok{3}\NormalTok{,}\DecValTok{4}\NormalTok{) }\KeywordTok{if}\NormalTok{ x > }\DecValTok{2}\NormalTok{; }
\NormalTok{                   y <- }\FunctionTok{StreamC}\NormalTok{(}\DecValTok{1}\NormalTok{,}\DecValTok{2}\NormalTok{)) }\KeywordTok{yield}\NormalTok{ x}
    \FunctionTok{println}\NormalTok{(seq.}\FunctionTok{toList}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

causes the following to print on the console:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    List(}\DecValTok{3}\NormalTok{, }\DecValTok{3}\NormalTok{, }\DecValTok{4}\NormalTok{, }\DecValTok{4}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

Note: During compilation, some versions of the Scala compiler may issue
a deprecation warning that \VERB|\NormalTok{filter}| is used instead of
\VERB|\NormalTok{withFilter}|. In a future release of Scala, this
substitution may no longer work. Because \VERB|\NormalTok{filter}| is
lazy for streams, we could define \VERB|\NormalTok{f<ilter}| as an alias
for \VERB|\NormalTok{withFilter}| with the following:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ withFilter = filter _}
\end{Highlighting}
\end{Shaded}

However, \VERB|\NormalTok{filter}| does generate a new
\VERB|\NormalTok{StreamC}| where \VERB|\NormalTok{withFilter}| normally
does not generate a new collection. Although this gets rid of the
warning, it would be better to implement a proper
\VERB|\NormalTok{withFilter}| function.

\hypertarget{infinite-streams-snd-corecursion}{%
\subsection{Infinite Streams snd
Corecursion}\label{infinite-streams-snd-corecursion}}

Because the streams are incremental, the functions we have defined also
work for \emph{infinite streams}.

Consider the following definition for an infinite sequence of ones:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{lazy} \KeywordTok{val}\NormalTok{ ones: StreamC[Int] = }\FunctionTok{cons}\NormalTok{(}\DecValTok{1}\NormalTok{, ones)}
\end{Highlighting}
\end{Shaded}

Note: The book \emph{Functional Programming in Scala} {[}Chuisano
2015{]} does not add the \VERB|\KeywordTok{lazy}| annotation, but that
version gives a compilation error in some versions of Scala. Adding
\VERB|\KeywordTok{lazy}| seems to fix the problem, but this issue should
be investigated further.

Although \VERB|\NormalTok{ones}| is infinite, the
\VERB|\NormalTok{StreamC}| functions only reference the finite prefix of
the stream needed to compute the needed result.

For example:

\begin{itemize}
\item
  \VERB|\NormalTok{ones.}\FunctionTok{take}\NormalTok{(}\DecValTok{5}\NormalTok{).}\FunctionTok{toList}|
  yields
  \VERB|\NormalTok{List(}\DecValTok{1}\NormalTok{,}\DecValTok{1}\NormalTok{,}\DecValTok{1}\NormalTok{,}\DecValTok{1}\NormalTok{,}\DecValTok{1}\NormalTok{)}|
\item
  \VERB|\NormalTok{ones.}\FunctionTok{map}\NormalTok{(_+}\DecValTok{2}\NormalTok{).}\FunctionTok{take}\NormalTok{(}\DecValTok{5}\NormalTok{).}\FunctionTok{toList}|
  yields
  \VERB|\NormalTok{List(}\DecValTok{3}\NormalTok{,}\DecValTok{3}\NormalTok{,}\DecValTok{3}\NormalTok{,}\DecValTok{3}\NormalTok{,}\DecValTok{3}\NormalTok{)}|
\item
  What about
  \VERB|\NormalTok{ones.}\FunctionTok{map}\NormalTok{(_+}\DecValTok{2}\NormalTok{).}\FunctionTok{toList}|?
\end{itemize}

We can generalize \VERB|\NormalTok{ones}| to a
\VERB|\NormalTok{constant}| function as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ constant[A](a: A): StreamC[A] = \{}
        \KeywordTok{lazy} \KeywordTok{val}\NormalTok{ tail: StreamC[A] = }\FunctionTok{Cons}\NormalTok{(() => a, () => tail)}
\NormalTok{        tail}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

An alternative would be just to make the body
\VERB|\FunctionTok{cons}\NormalTok{(a, }\FunctionTok{constant}\NormalTok{(a))}|.
But the above is more efficient because it is just one object
referencing itself.

We can also define an increasing \VERB|\NormalTok{StreamC}| of all
integers beginning with \VERB|\NormalTok{n}| as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{from}\NormalTok{(n: Int): StreamC[Int] =}
        \FunctionTok{cons}\NormalTok{(n, }\FunctionTok{from}\NormalTok{(n+}\DecValTok{1}\NormalTok{))}
\end{Highlighting}
\end{Shaded}

The (second-order) Fibonacci sequence begins with the elements 0 and 1;
each subsequent element is the sum of the two previous elements. We can
define the Fibonacci sequence as a stream \VERB|\NormalTok{fibs}| with
the following definition:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{val}\NormalTok{ fibs = \{}
        \KeywordTok{def} \FunctionTok{go}\NormalTok{(f0: Int, f1: Int): StreamC[Int] =}
            \FunctionTok{cons}\NormalTok{(f0, }\FunctionTok{go}\NormalTok{(f1, f0+f1))}
        \FunctionTok{go}\NormalTok{(}\DecValTok{0}\NormalTok{, }\DecValTok{1}\NormalTok{)}
\NormalTok{    \}}
\end{Highlighting}
\end{Shaded}

\hypertarget{prime-numbers-sieve-of-erastosthenes}{%
\subsubsection{Prime numbers: Sieve of
Erastosthenes}\label{prime-numbers-sieve-of-erastosthenes}}

A positive integer greater than 1 is \emph{prime} if it is divisible
only by itself and 1. The \emph{Sieve of Eratosthenes} algorithm works
by removing multiples of numbers once they are identified as prime.

\begin{itemize}
\item
  We begin the increasing stream of integers starting with 2, a prime
  number.
\item
  The head is 2, so we remove all the multiples of 2 from the stream.
\item
  The head of the tail is 3, so it is prime because it was not removed
  as a multiple of 2 and it is the smallest integer remaining.
\item
  Continue the process recursively on the tail.
\end{itemize}

We can define this calculation with the following
\VERB|\NormalTok{StreamC}| functions.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{sieve}\NormalTok{(ints: StreamC[Int]): StreamC[Int] = }
\NormalTok{        ints.}\FunctionTok{headOption} \KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case}\NormalTok{ None => }
\NormalTok{                sys.}\FunctionTok{error}\NormalTok{(}
                    \StringTok{"Should not occur: No head on infinite stream."}\NormalTok{)}
            \KeywordTok{case}\NormalTok{ Some(x) => }
                \FunctionTok{cons}\NormalTok{(x,}\FunctionTok{sieve}\NormalTok{(ints drop }\DecValTok{1} \FunctionTok{filter}\NormalTok{ (_ % x > }\DecValTok{0}\NormalTok{)))}
\NormalTok{        \}}
    \KeywordTok{val}\NormalTok{ primes: StreamC[Int] = }\FunctionTok{sieve}\NormalTok{(}\FunctionTok{from}\NormalTok{(}\DecValTok{2}\NormalTok{))}
\end{Highlighting}
\end{Shaded}

We can then use \VERB|\NormalTok{primes}| to define a function
\VERB|\NormalTok{isPrime}| to test whether an integer is prime.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def} \FunctionTok{isPrime}\NormalTok{(c: Int): Boolean =}
\NormalTok{        (primes }\FunctionTok{filter}\NormalTok{ (_ >= c) }\FunctionTok{map}\NormalTok{ (_ == c)).}\FunctionTok{headOption}\NormalTok{ getOrElse}
\NormalTok{            sys.}\FunctionTok{error}\NormalTok{(}
                \StringTok{"Should not occur: No head on infinite list."}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

\hypertarget{function-unfold}{%
\subsubsection{\texorpdfstring{Function
\texttt{unfold}}{Function unfold}}\label{function-unfold}}

Now let's consider \VERB|\NormalTok{unfold}|, a more general
stream-building function. Function \VERB|\NormalTok{unfold}| takes an
initial state and a function that produces both the next state and the
next value in the stream and builds the resulting stream. We can define
it as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ unfold[A, S](z: S)(f: S => Option[(A, S)]): StreamC[A] =}
        \FunctionTok{f}\NormalTok{(z) }\KeywordTok{match}\NormalTok{ \{}
            \KeywordTok{case}\NormalTok{ Some((h,s)) => }\FunctionTok{cons}\NormalTok{(h, }\FunctionTok{unfold}\NormalTok{(s)(f))}
            \KeywordTok{case}\NormalTok{ None        => empty}
\NormalTok{        \}}
\end{Highlighting}
\end{Shaded}

This function applies \VERB|\NormalTok{f}| to the current state
\VERB|\NormalTok{z}| to generate the next state \VERB|\NormalTok{s}| and
the next element \VERB|\NormalTok{h}| of the stream. We use
\VERB|\NormalTok{Option}| so \VERB|\NormalTok{f}| can signal when to
terminate the \VERB|\NormalTok{StreamC}|.

Function \VERB|\NormalTok{unfold}| is an example of a corecursive
function.

A \emph{recursive} function consumes data. The input of each successive
call is ``smaller'' than the previous one. Eventually the recursion
terminates when input size reaches the minimum.

A \emph{corecursive} function produces data. Corecursive functions need
not terminate as long as they remain \emph{productive}. By productive,
we mean that the function can continue to evaluate more of the result in
a finite amount of time.

Where we seek to argue that recursive functions terminate, we seek to
argue that corecursive functions are productive.

The \VERB|\NormalTok{unfold}| function remains productive as long as its
argument function \VERB|\NormalTok{f}| terminates. Function
\VERB|\NormalTok{f}| must terminate for the \VERB|\NormalTok{unfold}|
computation to reach its next state.

Some writers in the functional programming community use the term
\emph{guarded recursion} instead of corecursion and the term
\emph{cotermination} instead of productivity. See the Wikipedia articles
on corecursion {[}Wikipedia 2019d{]} and coinduction {[}Wikipedia
2019e{]} for more information and links.

The function \VERB|\NormalTok{unfold}| is very general. For example, we
can now define \VERB|\NormalTok{ones}|, \VERB|\NormalTok{constant}|,
\VERB|\NormalTok{from}|, and \VERB|\NormalTok{fibs}| with
\VERB|\NormalTok{unfold}|.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{val}\NormalTok{ onesViaUnfold = }\FunctionTok{unfold}\NormalTok{(}\DecValTok{1}\NormalTok{)(_ => Some((}\DecValTok{1}\NormalTok{,}\DecValTok{1}\NormalTok{)))}

    \KeywordTok{def}\NormalTok{ constantViaUnfold[A](a: A) =}
        \FunctionTok{unfold}\NormalTok{(a)(_ => Some((a,a)))}

    \KeywordTok{def} \FunctionTok{fromViaUnfold}\NormalTok{(n: Int) =}
        \FunctionTok{unfold}\NormalTok{(n)(n => Some((n,n+}\DecValTok{1}\NormalTok{)))}

    \KeywordTok{val}\NormalTok{ fibsViaUnfold =}
        \FunctionTok{unfold}\NormalTok{((}\DecValTok{0}\NormalTok{,}\DecValTok{1}\NormalTok{)) \{ }\KeywordTok{case}\NormalTok{ (f0,f1) => Some((f0,(f1,f0+f1))) \}}
\end{Highlighting}
\end{Shaded}

\hypertarget{summary}{%
\subsection{Summary}\label{summary}}

The big idea in this chapter is that we can exploit nonstrict functions
to increase efficiency, increase code reuse, and improve the modularity
in functional programs.

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

\begin{itemize}
\tightlist
\item
  \href{StreamC.scala}{\texttt{StreamC.scala}}
\end{itemize}

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

TODO: Add

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

In Spring 2016, I wrote this set of notes to accompany my lectures on
Chapter 5 of the book \emph{Functional Programming in Scala} {[}Chiusano
2015{]} (i.e.~the Red Book). I constructed the notes around the ideas,
general structure, and Scala examples from that chapter and its
associated materials.

In 2018 and 2019, I updated the format of the document to be more
compatible with my evolving document structures. In 2019, I also renamed
the \VERB|\NormalTok{Stream}| (used in the Red Book) to
\VERB|\NormalTok{StreamC}| to better avoid conflicts with the standard
library type \VERB|\NormalTok{Stream}|.

I maintain these notes as text in Pandoc's dialect of Markdown using
embedded LaTeX markup for the mathematical formulas and then translate
the notes to HTML, PDF, and other forms as needed.

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

\begin{description}
\tightlist
\item[{[}Britton 1981{]}:]
K. H. Britton, R. A. Parker, and D. L. Parnas. ``A Procedure for
Designing Abstract Interfaces for Device Interface Modules,'' In
\emph{Proceedings of the 5th International Conference on Software
Engineering}, pp.~195-204, March 1981.
\item[{[}Chiusano 2015{]}:]
Paul Chiusano and Runar Bjarnason. \emph{Functional Programming in
Scala}, Manning, 2015. This book is sometimes called the Red Book. The
chapter notes for this book are available on GitHub at
\url{https://github.com/fpinscala/fpinscala/wiki}.
\item[{[}Cunningham 2019a{]}:]
H. Conrad Cunningham.
\href{../ScalaForJava/ScalaForJava.html}{\emph{Notes on Scala for Java
Programmers}}, 2019.
\item[{[}Cunningham 2019b{]}:]
H. Conrad Cunningham.
\href{../RecursionStyles/RecursionStylesScala.html}{\emph{Recursion
Styles, Correctness, and Efficiency (Scala Version)}}, 2019.
\item[{[}Cunningham 2019c{]}:]
H. Conrad Cunningham.
\href{../TypeConcepts/TypeSystemConcepts.html}{\emph{Type System
Concepts}}, 2019.
\item[{[}Cunningham 2019d{]}:]
H. Conrad Cunningham. \href{../FPS03/FunctionalDS.html}{\emph{Functional
Data Structures}}, 2019.
\item[{[}Cunningham 2019e{]}:]
H. Conrad Cunningham. \href{../FPS04/ErrorHandling.html}{\emph{Handling
Errors without Exceptions}}, 2019.
\item[{[}Cunningham 2019f{]}:]
H. Conrad Cunningham.
\href{../Digraph/Scala/AbstractDataTypes.html}{\emph{Abstract Data Types
in Scala}}, 2019.
\item[{[}Hughes 1989{]}:]
John Hughes, \href{localcopy/whyfp.pdf}{Why Functional Programming
Matters}, \emph{Computer Journal}, Vol. 32, No.~2, pp.~98-107, 1989.
\item[{[}Parnas 1972{]}:]
D. L. Parnas. ``On the Criteria to Be Used in Decomposing Systems into
Modules,'' \emph{Communications of the ACM}, Vol. 15, No.~12,
pp.1053-1058, 1972.
\item[{[}Wikipedia 2019a{]}:]
Wikipedia,
\href{https://en.wikipedia.org/wiki/Separation_of_concerns}{Separation
of concerns}, accessed 12 March 2019.
\item[{[}Wikipedia 2019b{]}:]
Wikipedia,
\href{https://en.wikipedia.org/wiki/Information_hiding}{Information
hiding}, accessed 12 March 2019.
\item[{[}Wikipedia 2019c{]}:]
Wikipedia,
\href{https://en.wikipedia.org/wiki/Model-view-controller}{Model-View-Controller},
accessed 12 March 2019.
\item[{[}Wikipedia 2019d{]}:]
Wikipedia,
\href{https://en.wikipedia.org/wiki/Corecursion}{Corecursion}, accessed
12 March 2019.
\item[{[}Wikipedia 2019e{]}:]
Wikipedia,
\href{https://en.wikipedia.org/wiki/Coinduction}{Coinduction}, accessed
12 March 2019.
\end{description}

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

\emph{Big idea}: Exploiting nonstrict function to increase efficiency,
increase code reuse, and improve modularity

\emph{Concepts}: Strict and nonstrict (lenient) functions/parameters,
termination, bottom, call-by-name, thunk, forcing, call-by-need, lazy
evaluation, lazy lists or streams, \texttt{Stream} data type, smart
constructors, memoization, \VERB|\KeywordTok{lazy}| variables, purity of
functions, separation of concerns, information hiding, design secret,
abstract interface, business logic, Model-View-Controller (MVC) design
pattern, keeping program description separate from evaluation,
incremental computation, prime number, Sieve of Eratosthenes, recursive,
corecursive (guarded recursion), productivity (cotermination).

\end{document}
