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

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

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

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

\begin{document}
\maketitle

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

\textbf{Acknowledgements}: This is a set of notes written to accompany
my lectures on Chapter 5 of the book \emph{Functional Programming in
Scala} by Paul Chiusano and Runar Bjarnason (Manning, 2015). I
constructed the notes around the ideas and Scala examples from that
chapter and its accompanying materials. I encourage all students to
study the chapter.

\textbf{Prerequisite}: This discussion assumes the reader is familiar
with the programming concepts and Scala features covered in my
\emph{Notes on Scala for Java Programmers}, \emph{Recursion Concepts and
Terminology}, \emph{Functional Data Structures}, and \emph{Handling
Errors without Exceptions}.

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

TODO: Change to use code blocks, restructure to match current style

\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 of Chapter 3 of \emph{Functional Programming in
Scala}, 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
\texttt{map}, \texttt{filter}, \texttt{foldLeft}, and
\texttt{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{verbatim}
      List(10,20,30,40,50).map(_ / 10).filter(_ % 2 == 1).map(_ * 100) 
\end{verbatim}

that generates the result:

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

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{verbatim}
    def mfm(xs: List[Int]): List[Int] = xs match {
      case Nil     => Nil 
      case (y::ys) => 
        val z = y / 10 
        if (z % 2 == 1) (z*100) :: mfm(ys) else mfm(ys) 
    }
\end{verbatim}

It would be convenient if we could instead get a result similar to
\texttt{mfm} by composing simpler functions like \texttt{map} and
\texttt{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 and elaborate on them in this chapter.

\hypertarget{what-is-strictness-and-nonstrictness}{%
\subsubsection{What is strictness and
nonstrictness?}\label{what-is-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 \texttt{f} is \emph{strict} if \texttt{f(x)} evaluates to
bottom for all \texttt{x} that themselves evaluate to bottom. That is,
\texttt{f(}\(\bot\)\texttt{)} \texttt{==} \(\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{)} \texttt{!=}
\(\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'' \texttt{\&\&} operation is nonstrict; it does not
evaluate its second operand when the first operation is \texttt{false}.
Similarly, \texttt{\textbar{}\textbar{}} does not evaluate its second
operand when its first operand is \texttt{true}.

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

We could implement \texttt{if} as a function as follows:

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

Then we can call \texttt{if2} as in the code fragment

\begin{verbatim}
      val age = 21
      if2(age >= 18, () => println("Can vote"),() => println("Cannot vote"))
\end{verbatim}

and get the output

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

The parameter type \texttt{()\ =\textgreater{}\ A} means that the
corresponding argument is passed as a parameterless function that
returns a value of type \texttt{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
\texttt{onTrue()}

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 \texttt{if2} as
follows:

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

The \texttt{onTrue:\ =\textgreater{}\ A} notation makes the argument
expression a by-name parameter. Scala automatically creates the thunk
for parameter \texttt{onTrue} and enables it to be referenced within the
function without explicitly forcing its evaluation, for example by using
\texttt{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{verbatim}
      def maybeTwice(b: Boolean, i: => Int) = if (b) i + i else 0
\end{verbatim}

which can be called as

\begin{verbatim}
      println(maybeTwice(true, {println("hi"); 1 + 41}))
\end{verbatim}

to generate output:

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

Note that the argument expression \texttt{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 \texttt{lazy\ val}. The
temporary variable will not be initialized until it is referenced, but
it caches the calculated value so that it can be used without
reevaluation on subsequent references.

We can rewrite \texttt{maybeTwice} as follows:

\begin{verbatim}
      def maybeTwice2(b: Boolean, i: => Int) = {
        lazy val j = i
        if (b) j+j else 0
      }
\end{verbatim}

Now calling it as

\begin{verbatim}
      println(maybeTwice2(true, {println("hi"); 1 + 41}))
\end{verbatim}

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 algebraic data tupe \texttt{Stream}. A nonempty stream
consists of a head and a tail, both of which must be nonstrict.

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{verbatim}
    import scala.{Stream => _, _}
    import Stream._
    
    sealed trait Stream[+A]
    case object Empty extends Stream[Nothing]
    case class Cons[+A](h: () => A, t: () => Stream[A]) extends Stream[A]

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

\hypertarget{memoizing-streams}{%
\subsubsection{Memoizing streams}\label{memoizing-streams}}

In the \texttt{Stream} 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 \texttt{Stream} 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 \texttt{cons} takes the head and tail of the
new \texttt{Stream} as by-name parameters, equates these to lazy
variables to cache their values, and then creates a \texttt{Cons} cell
whose fields are two explicit thunks wrapping the head and the tail.

Smart constructor function \texttt{empty} just creates an \texttt{Empty}
\texttt{Stream}.

Both smart constructors have return type \texttt{Stream{[}A{]}}. In
addition to establishing the needed invariants, the use of the smart
constructors helps Scala's type inference mechanism infer the
\texttt{Stream} 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 \texttt{apply} takes a sequence of zero or more
arguments and creates the corresponding \texttt{Stream}.

If a function examines or traverses a \texttt{Stream}, it must
explicitly force the thunks. In general, we should encapsulate such
accesses within functions defined as a part of the \texttt{Stream}
implementation. (That is, we should practice \emph{information hiding},
hide this design detail as a \emph{secret} of the \texttt{Stream}
implementation as we discuss in the notes on Data Abstraction.)

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

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

It explicitly forces 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 \texttt{Stream} trait.

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

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

Of course, this method may suffer from stack overflow for large 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{verbatim}
     def toList: List[A] = {
       @annotation.tailrec
       def go(s: Stream[A], acc: List[A]): List[A] = s match {
         case Cons(h,t) => go(t(), h() :: acc) // force thunks
         case _         => acc
       }
       go(this, List()).reverse
     }
\end{verbatim}

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

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

Next, let's define function \texttt{take} to return the first \texttt{n}
elements from a \texttt{Stream} and function \texttt{drop} to skip the
first \texttt{n} elements.

We can define method \texttt{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 \texttt{n\ ==\ 1} and
\texttt{n\ ==\ 0} cases specially).

\begin{verbatim}
      def take(n: Int): Stream[A] = this match {
        case Cons(h, t) if n > 1  => cons(h(), t().take(n - 1))
        case Cons(h, _) if n == 1 => cons(h(), empty)
\end{verbatim}

\textless{} case \_ =\textgreater{} empty // stream empty or n
\textless{} 1 \}

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

\begin{verbatim}
      @annotation.tailrec
      final def drop(n: Int): Stream[A] = this match {
        case Cons(_, t) if n > 0 => t().drop(n - 1)
        case _ => this
      }
\end{verbatim}

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

\begin{verbatim}
      def takeWhile(p: A => Boolean): Stream[A] = this match {
        case Cons(h,t) if p(h()) => cons(h(), t() takeWhile p)
        case _ => empty
      }
\end{verbatim}

In the first case, we apply method \texttt{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 a software system. 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}. 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}.

We also apply separation of concerns in software architecture for
computing applications. For example, we try to keep the \emph{business
logic} (i.e., specific knowledge about the application area), the user
interface, and the data representation for an application separate from
each other using an approach such as the \emph{Model-View-Controller}
(MVC) architectural design pattern.

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 \texttt{Option} or \texttt{Either} to express that an error has
  occurred but deferring the handling of the error to other parts of the
  program
\item
  use of \texttt{Stream} 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}.

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

\begin{verbatim}
      def exists(p: A => Boolean): Boolean = this match {
        case Cons(h,t) => p(h()) || t().exists(p)
        case _         => false
      }
\end{verbatim}

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

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

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

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

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

\begin{verbatim}
        def exists2(p: A => Boolean): Boolean =
          foldRight(false)((a, b) => p(a) || b) 
          
\end{verbatim}

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

Caveat: The second version of \texttt{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
\texttt{false}, this version is not stack safe.

Because the \texttt{foldRight} method on \texttt{Stream} can terminate
its traversal early, we can use it to implement \texttt{exists}
efficiently. Unfortunately, we cannot implement the \texttt{List}
version of \texttt{exists} efficiently in terms of the \texttt{List}
version of \texttt{foldRight}. We must implement a specialized recursive
version of \texttt{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 \texttt{Stream} trait and implement the basic
\texttt{map}, \texttt{filter}, \texttt{append}, and \texttt{flatMap}
methods using the general function \texttt{foldRight}, as follows:

\begin{verbatim}
      def map[B](f: A => B): Stream[B] =
        foldRight(empty[B])((h,t) => cons(f(h), t))
        
      def filter(p: A => Boolean): Stream[A] =
        foldRight(empty[A])((h,t) => if (p(h)) cons(h, t) else t)
        
      def append[B >: A](s: => Stream[B]): Stream[B] =
        foldRight(s)((h,t) => cons(h,t))

      def flatMap[B](f: A => Stream[B]): Stream[B] =
        foldRight(empty[B])((h,t) => f(h) append t)
\end{verbatim}

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 \texttt{Stream} 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 by the problem in the Introduction
to these notes. There we asked the question of how can we compute the
result of the expression

\begin{verbatim}
      List(10,20,30,40,50).map(_ / 10).filter(_ % 2 == 1).map(_ * 100)
\end{verbatim}

without producing two unneeded intermediate lists.

The \texttt{Stream} expression

\begin{verbatim}
      Stream(10,20,30,40,50).map(_ / 10).filter(_ % 2 == 1).map(_ * 100).toList
\end{verbatim}

generates the result

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

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

When executed, the lazy evaluation interleaves two \texttt{map}, the
\texttt{filter}, and the \texttt{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
\texttt{mfm} in the introduction.

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

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 \texttt{filter}
(which seems to process the entire stream) to implement \texttt{find}, a
function to return the first occurrence of an element in a stream that
satisfies a given predicate, as follows:

\begin{verbatim}
     def find(p: A => Boolean): Option[A] = filter(p).headOption
\end{verbatim}

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 \texttt{map}, \texttt{filter}, and
\texttt{flatMap}, we can now use sequence comprehensions on our
\texttt{Stream} data. For example, the code fragment

\begin{verbatim}
      val seq = for (x <- Stream(1,2,3,4) if x > 2; y <- Stream(1,2)) yield x
      println(seq.toList)
\end{verbatim}

causes the following to print on the console:

\begin{verbatim}
      List(3, 3, 4, 4)
\end{verbatim}

Note: During compilation, the Scala compiler issues a deprecation
warning that \texttt{filter} is used instead of \texttt{withFilter}. In
a future release of Scala, this substitution may no longer work. Because
\texttt{filter} is lazy for streams, we could define \texttt{withFilter}
as an alias for \texttt{withFilter} with the following:

\begin{verbatim}
      def withFilter = filter _
\end{verbatim}

However, \texttt{filter} does generate a new \texttt{Stream} where
\texttt{withFilter} normally does not generate a new collection.
Although this gets rid of the warning, it would be better to implement a
proper \texttt{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{verbatim}
     lazy val ones: Stream[Int] = cons(1, ones)
\end{verbatim}

Note: The book \emph{Functional Programming in Scala} does not add the
\texttt{lazy} annotation, but that version gives a compilation error.
Adding \texttt{lazy} seemed to fix the problem, but this issue should be
investigated further.

Although \texttt{ones} is infinite, the \texttt{Stream} functions only
reference the finite prefix of the stream needed to compute the needed
result.

For example:

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

We can generalize \texttt{ones} to a \texttt{constant} function as
follows:

\begin{verbatim}
      def constant[A](a: A): Stream[A] = {
        lazy val tail: Stream[A] = Cons(() => a, () => tail)
        tail
      }
\end{verbatim}

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

We can also define an increasing \texttt{Stream} of all integers
beginning with \texttt{n} as follows:

\begin{verbatim}
      def from(n: Int): Stream[Int] =
        cons(n, from(n+1))
\end{verbatim}

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 \texttt{fibs} with the
following definition:

\begin{verbatim}
      val fibs = {
        def go(f0: Int, f1: Int): Stream[Int] =
          cons(f0, go(f1, f0+f1))
        go(0, 1)
      }
\end{verbatim}

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

\begin{verbatim}
      def sieve(ints: Stream[Int]): Stream[Int] = ints.headOption match {
        case None => sys.error("Should not occur: No head on infinite stream.")
        case Some(x) => cons(x,sieve(ints drop 1 filter (_ % x > 0)))
      }

      val primes: Stream[Int] = sieve(from(2))
\end{verbatim}

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

\begin{verbatim}
    def isPrime(c: Int): Boolean =
      (primes filter (_ >= c) map (_ == c)).headOption getOrElse
        sys.error("Should not occur: No head on infinite list.")
\end{verbatim}

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

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

\begin{verbatim}
      def unfold[A, S](z: S)(f: S => Option[(A, S)]): Stream[A] =
        f(z) match {
          case Some((h,s)) => cons(h, unfold(s)(f))
          case None        => empty
        }
\end{verbatim}

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

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

The \texttt{unfold} function remains productive as long as its argument
function \texttt{f} terminates. Function \texttt{f} must terminate for
the \texttt{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 and coinduction for more information and links.

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

\begin{verbatim}
     val onesViaUnfold = unfold(1)(_ => Some((1,1)))

     def constantViaUnfold[A](a: A) =
       unfold(a)(_ => Some((a,a)))

     def fromViaUnfold(n: Int) =
       unfold(n)(n => Some((n,n+1)))

     val fibsViaUnfold =
       unfold((0,1)) { case (f0,f1) => Some((f0,(f1,f0+f1))) }
\end{verbatim}

\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
  \url{StreamC.scala}
\end{itemize}

\end{document}