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