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

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

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

\title{CSci 450: Org. of Programming Languages\\
Higher-Order Functions}
\author{H. Conrad Cunningham}
\date{9 October 2017}

\begin{document}
\maketitle

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

\textbf{Acknowledgements:} In Summer 2016, I adapted and revised this
chapter from chapter 6 of my \emph{Notes on Functional Programming with
Haskell} and from my notes on \emph{Functional Data Structures} from the
Spring 2016 Scala variant of CSci 555. The latter was based, in part, on
chapter 3 of the book \emph{Functional Programming in Scala} by Paul
Chiusano and Runar Bjarnason (Manning, 2015).

I also expanded the discussion of of combinators and functional
composition and added discussion of \texttt{seq}, \texttt{\$}, and
\texttt{\$!}. These drew on ideas from chapters 4 and 7 of Richard
Bird's \emph{Thinking Functionally with Haskell} (Cambridge University
Press, 2015) and chapter 11 of Simon Thompson's \emph{Haskell: The Craft
of Programming, Third Edition} (Pearson 2011).

In 2017, I continue to develop this chapter.

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

\textbf{Advisory}: The HTML version of this document may require use of
a browser that supports the display of MathML. A good choice as of
October 2017 is a recent version of Firefox from Mozilla.

TODO:

\begin{itemize}
\tightlist
\item
  Consider other examples for use of map, filter, fold
\item
  Consider testing
\item
  Consider larger case study
\item
  Edit and add more exercises
\end{itemize}

\setcounter{section}{4}

\section{Higher-Order Functions}\label{higher-order-functions}

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

This chapter introduces higher-order functions and constructs a library
of useful higher-order functions to process lists.

The goals of the chapter are for the students to be able to:

\begin{itemize}
\item
  develop correct Haskell functional programs that include appropriate
  higher-order polymorphic functions, functional composition,
  combinators, and inline function definitions
\item
  develop Haskell programs that terminate and are efficient and elegant.
\end{itemize}

Upon successful completion of this chapter, students should be able to:

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  describe the syntax and semantics of Haskell function concepts and
  operators such as strictness, currying, partial application, operator
  sections, combinators, lambda expressons, and strict function
  application
\item
  describe the syntax and semantics of first-class and higher-order
  Haskell functions
\item
  develop Haskell programs using using Haskell function concepts and
  operators such as strictness, currying, partial application, operator
  sections, combinators, lambda expressons, and strict function
  application
\item
  use a library of higher-order Haskell functions to develop Haskell
  programs
\item
  generalize and develop higher-order Haskell functions for reuse
\item
  appreciate the mathematical characteristics of Haskell functions
  (e.g., to state properties of functions and operators)
\end{enumerate}

The Haskell module for this chapter is in
\href{code05/Mod05HigherOrder.hs}{\texttt{Mod05HigherOrder.hs}}.

\subsection{Higher-Order List
Programming}\label{higher-order-list-programming}

\subsubsection{Generalizing procedural
abstractions}\label{generalizing-procedural-abstractions}

A function in a programming language is a \emph{procedural abstraction}.
It separates the logical properties of a computation from the details of
how the computation is implemented. It abstracts a pattern of behavior
and encapsulates it within a program unit.

Suppose we wish to perform the \emph{same} computation on a set of
\emph{similar} data structures. As we have seen, we can encapsulate the
computation in a function having the data structure as an argument. For
example, the function \texttt{length\textquotesingle{}} computes the
number of elements in a list of any type.

Suppose instead we wish to perform a \emph{similar} (but not identical)
computation on a set of \emph{similar} data structures. For example, we
want to compute the sum or the product of a list of numbers. In this
case, we may can pass the operation itself into the function.

This kind of function is called a \emph{higher-order function}. A
higher-order function is a function that takes functions as arguments or
returns functions in a result. Most traditional imperative languages do
not fully support higher-order functions.

In most functional programming languages, functions are treated as
\emph{first class} values. That is, functions can be stored in data
structures, passed as arguments to functions, and returned as the
results of functions. Historically, imperative languages have not
treated functions as first-class values. (Recently, many imperative
languages, such as Java 8, have added support for functions as
first-class values.)

The higher-order functions in Haskell and other functional programming
languages enable us to construct regular and powerful abstractions and
operations. By taking advantage of a library of higher-order functions
that capture common patterns of computation, we can quickly construct
concise, yet powerful, programs.

This can increase programmer productivity and program reliability
because such programs are shorter, easier to understand, and constructed
from well-tested components.

Higher-order functions can also increase the \emph{modularity} of
programs by enabling simple program fragments to be ``glued together''
readily into more complex programs.

In this section, we examine several common patterns and build a library
of useful higher-order functions.

\subsubsection{\texorpdfstring{Defining
\texttt{map}}{Defining map}}\label{defining-map}

Consider the following two functions, noting their type signatures and
patterns of recursion.

The first, \texttt{squareAll}, takes a list of integers and returns the
corresponding list of squares of the integers.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    squareAll ::}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }\OtherTok{->}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{]}\OtherTok{  squareAll ::}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }\OtherTok{->}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }
\NormalTok{    squareAll []     }\FunctionTok{=}\NormalTok{ [] }
\NormalTok{    squareAll (x}\FunctionTok{:}\NormalTok{xs) }\FunctionTok{=}\NormalTok{ (x }\FunctionTok{*}\NormalTok{ x) }\FunctionTok{:}\NormalTok{ squareAll xs}
\end{Highlighting}
\end{Shaded}

The second, \texttt{lengthAll}, takes a list of lists and returns the
corresponding list of the lengths of the element lists; it uses the
Prelude function \texttt{length}.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    lengthAll ::}\NormalTok{ [[a]] }\OtherTok{->}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }
\NormalTok{    lengthAll []       }\FunctionTok{=}\NormalTok{ [] }
\NormalTok{    lengthAll (xs}\FunctionTok{:}\NormalTok{xss) }\FunctionTok{=}\NormalTok{ (length xs) }\FunctionTok{:}\NormalTok{ lengthAll xss}
\end{Highlighting}
\end{Shaded}

Although these functions take different kinds of data (a list of
integers versus a list of polymorphically typed lists) and apply
different operations (squaring versus list length), they exhibit the
same pattern of computation. That is, both take a list of some type and
apply a given function to each element to generate a resulting list of
the same length as the original.

The combination of polymorphic typing and higher-order functions allow
us to abstract this pattern of computation into a standard function.

We can abstract the pattern of computation common to \texttt{squareAll}
and \texttt{lengthAll} as the (broadly useful) function \texttt{map},
which we define as follows. (In this chapter, we often add a suffix to
the base function names to avoid conflicts with the similarly named
functions in the Prelude. Here we use \texttt{map’} instead of
\texttt{map}.)

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    map' ::}\NormalTok{ (a }\OtherTok{->}\NormalTok{ b) }\OtherTok{->}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ [b]  }\CommentTok{-- map in Prelude}
\NormalTok{    map' f []     }\FunctionTok{=}\NormalTok{ [] }
\NormalTok{    map' f (x}\FunctionTok{:}\NormalTok{xs) }\FunctionTok{=}\NormalTok{ f x }\FunctionTok{:}\NormalTok{ map' f xs }
\end{Highlighting}
\end{Shaded}

Function \texttt{map} \emph{generalizes} \texttt{squareAll},
\texttt{lengthAll}, and similar functions by adding a higher-order
parameter for the operation applied and making the input and the output
lists polymorphic. Specifically, the function takes a function
\texttt{f} of type \texttt{a\ -\textgreater{}\ b} and a list of type
\texttt{{[}a{]}}, applies function \texttt{f} to each element of the
list, and produces a list of type \texttt{{[}b{]}}.

Thus we can \emph{specialize} \texttt{map} to give new definitions of
\texttt{squareAll} and \texttt{lengthAll} as follows:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    squareAll2 ::}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }\OtherTok{->}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }
\NormalTok{    squareAll2 xs }\FunctionTok{=}\NormalTok{ map' sq xs }
                    \KeywordTok{where}\NormalTok{ sq x }\FunctionTok{=}\NormalTok{ x }\FunctionTok{*}\NormalTok{ x }
    \DataTypeTok{InIn}
\OtherTok{    lengthAll2 ::}\NormalTok{ [[a]] }\OtherTok{->}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }
\NormalTok{    lengthAll2 xss }\FunctionTok{=}\NormalTok{ map' length xss}
\end{Highlighting}
\end{Shaded}

Consider the following questions.

\begin{itemize}
\item
  Under what circumstances does \texttt{map\textquotesingle{}\ f\ xs}
  terminate? Do we have to assume anything about \texttt{f}? about
  \texttt{xs}?
\item
  What is the time complexity of \texttt{map\ f\ xs}? space complexity?
\item
  What is the time complexity of \texttt{squareAll2\ xs}? of
  \texttt{lengthAll2\ xs}?
\end{itemize}

\subsubsection{Thinking about data
transformations}\label{thinking-about-data-transformations}

Above we define \texttt{map} as a recursive function that transforms the
elements of a list one by one. However, it is often more useful to think
of \texttt{map} in one of two ways:

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  as a powerful list operator that transforms every element of the list.
  We can combine \texttt{map} with other powerful operators to quickly
  construct powerful list processing programs.

  We can consider \texttt{map} as operating on every element of the list
  ``simultaneously''. In fact, an implementation could use separate
  processors to transform each element: this is essentially the
  \texttt{map} operation in Google's \texttt{mapReduce} distributed
  ``big data'' processing framework.

  Referential transparency and immutable data structures make
  parallelism easier in Haskell than in most imperative languages.
\item
  as a operator node in a dataflow network. A stream of data objects
  flows into the \texttt{map} node. The \texttt{map} node transforms
  each object by applying the argument function. Then the data object
  flows out to the next node of the network.

  The lazy evaluation of the Haskell functions enables such an
  implementation.
\end{enumerate}

Although in the early parts of these notes we give attention to the
details of recursion, learning how to \emph{think like a functional
programmer} requires us to think about large-scale transformations of
collections of data.

\subsubsection{Generalizing function
definitions}\label{generalizing-function-definitions}

Whenever we recognize a computational pattern in a set of related
functions, we can \emph{generalize the function} definition as follows:

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Do a \emph{scope-commonality-variability analysis} on the set of
  related functions.

  That is, identify what is to be included and what not (i.e., the
  scope), the parts of functions that are the same (the
  \emph{commonalities} or \emph{frozen spots}), and the parts that
  differ (the \emph{variabilities} or \emph{hot spots})
\item
  Leave the commonalities in the generalized function's body.
\item
  Move the variabilities into the generalized function's header -- its
  type signature and parameter list.

  \begin{itemize}
  \item
    If the part moved to the generalized function's parameter list is an
    expression, then make that part a function with a parameter for each
    local variable accessed.
  \item
    If a data type potentially differs from a specific type used in the
    set of related functions, then add a type parameter to the
    generalized function.
  \item
    If the same data value or type appears in multiple roles, then
    consider adding distinct type or value parameters for each role.
  \end{itemize}
\item
  Consider other approaches if the generalized function's type type
  signature and parameter list become too complex.

  For example, we can introduce new data or procedural abstractions for
  parts of the generalized function. These may be in the same module of
  the generalized function or in an appropriately defined separate
  module.
\end{enumerate}

\subsubsection{\texorpdfstring{Defining
\texttt{filter}}{Defining filter}}\label{defining-filter}

Consider the following two functions.

The first, \texttt{getEven}, takes a list of integers and returns the
list of those integers that are even (i.e., are multiples of 2). The
function preserves the relative order of the elements in the list.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    getEven ::}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }\OtherTok{->}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }
\NormalTok{    getEven []      }\FunctionTok{=}\NormalTok{ [] }
\NormalTok{    getEven (x}\FunctionTok{:}\NormalTok{xs)}
        \FunctionTok{|}\NormalTok{ even x    }\FunctionTok{=}\NormalTok{ x }\FunctionTok{:}\NormalTok{ getEven xs }
        \FunctionTok{|}\NormalTok{ otherwise }\FunctionTok{=}\NormalTok{ getEven xs}
\end{Highlighting}
\end{Shaded}

The second, \texttt{doublePos}, takes a list of integers and returns the
list of doubles of the positive integers from the input list; it
preserves the relative order of the elements.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    doublePos ::}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }\OtherTok{->}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }
\NormalTok{    doublePos []          }\FunctionTok{=}\NormalTok{ [] }
\NormalTok{    doublePos (x}\FunctionTok{:}\NormalTok{xs) }
        \FunctionTok{|} \DecValTok{0} \FunctionTok{<}\NormalTok{ x     }\FunctionTok{=}\NormalTok{ (}\DecValTok{2} \FunctionTok{*}\NormalTok{ x) }\FunctionTok{:}\NormalTok{ doublePos xs }
        \FunctionTok{|}\NormalTok{ otherwise }\FunctionTok{=}\NormalTok{ doublePos xs}
\end{Highlighting}
\end{Shaded}

Function \texttt{even} is from the Prelude; it returns \texttt{True} if
its argument is evenly divisible by 2 and returns \texttt{False}
otherwise.

What do these two functions have in common? What differs?

\begin{itemize}
\item
  Both take a list of integers and return a (possibly shorter) list of
  integers.

  However, the fact they use integers is not important; the key fact is
  that they take and return lists of the same element type.
\item
  Both return an empty list when its input list is empty.
\item
  In both, the relative orders of elements in the output list is the
  same as in the input list.
\item
  Both select some elements to copy to the output and others not to
  copy.

  Function \texttt{getEven} selects elements that are even numbers and
  function \texttt{doublePos} selects elements that are positive
  numbers.
\item
  Function \texttt{doublePos} doubles the value copied and
  \texttt{getEven} leaves the value unchanged.
\end{itemize}

Using the generalization method outlined above, we abstract the pattern
of computation common to \texttt{getEven} and \texttt{doublePos} as the
(broadly useful) function \texttt{filter} found in the Prelude. (We call
the function \texttt{filter’} below to avoid a name conflict.)

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    filter' ::}\NormalTok{ (a }\OtherTok{->} \DataTypeTok{Bool}\NormalTok{) }\OtherTok{->}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ [a]  }\CommentTok{-- filter in Prelude}
\NormalTok{    filter' _ []    }\FunctionTok{=}\NormalTok{ [] }
\NormalTok{    filter' p (x}\FunctionTok{:}\NormalTok{xs)}
        \FunctionTok{|}\NormalTok{ p x       }\FunctionTok{=}\NormalTok{ x }\FunctionTok{:}\NormalTok{ xs' }
        \FunctionTok{|}\NormalTok{ otherwise }\FunctionTok{=}\NormalTok{ xs' }
                    \KeywordTok{where}\NormalTok{ xs' }\FunctionTok{=}\NormalTok{ filter' p xs}
\end{Highlighting}
\end{Shaded}

Function \texttt{filter} takes a predicate \texttt{p} of type
\texttt{a\ -\textgreater{}\ Bool} and a list of type \texttt{{[}a{]}}
and returns a list containing those elements that satisfy \texttt{p}, in
the same order as the input list. Note that the keyword \texttt{where}
begins in the same column as the \texttt{=} in the defining equations;
thus the scope of the definition of \texttt{xs’} extends over
\emph{both} legs of the definition.

Function \texttt{filter} does not incorporate the doubling operation
from \texttt{doublePos}. We could have included it as another
higher-order parameter, but we leave it out to keep the generalized
function simple. We can use the already defined \texttt{map} function to
achieve this separately.

Therefore, we can specialize \texttt{filter} to give new definitions of
\texttt{getEven} and \texttt{doublePos} as follows:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    getEven2 ::}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }\OtherTok{->}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }
\NormalTok{    getEven2 xs }\FunctionTok{=}\NormalTok{ filter' even xs }

\OtherTok{    doublePos2 ::}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }\OtherTok{->}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }
\NormalTok{    doublePos2 xs }\FunctionTok{=}\NormalTok{ map' dbl (filter' pos xs) }
                    \KeywordTok{where}\NormalTok{ dbl x  }\FunctionTok{=} \DecValTok{2} \FunctionTok{*}\NormalTok{ x}
\NormalTok{                          pos x }\FunctionTok{=}\NormalTok{ (}\DecValTok{0} \FunctionTok{<}\NormalTok{ x)}
\end{Highlighting}
\end{Shaded}

Note that function \texttt{doublePos2} exhibits both the \texttt{filter}
and the \texttt{map} patterns of computation.

The standard higher-order functions \texttt{map} and \texttt{filter}
allow us to restate the three-leg definitions of \texttt{getEven} and
\texttt{doublePos} in just one leg each, except that \texttt{doublePos}
requires two lines of local definitions. In subsequent subsections, we
see how to eliminate these simple local definitions as well.

Consider the following questions.

\begin{itemize}
\item
  Under what circumstances does \texttt{filter\textquotesingle{}\ p\ xs}
  terminate? Do we have to assume anything about \texttt{p}? about
  \texttt{xs}?
\item
  What is the time complexity of
  \texttt{filter\textquotesingle{}\ p\ xs}? space complexity?
\item
  What is the time complexity of \texttt{getEven2\ xs}? space
  complexity?
\item
  What is the time complexity of \texttt{doublePos2\ xs}? space
  complexity?
\end{itemize}

\subsubsection{\texorpdfstring{Defining fold right
(\texttt{foldr})}{Defining fold right (foldr)}}\label{defining-fold-right-foldr}

Consider the \texttt{sum} and \texttt{product} functions we defined in a
previous chapter, ignoring the short-cut handling of the zero element in
\texttt{product}.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    sum' ::}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }\OtherTok{->} \DataTypeTok{Int}             \CommentTok{-- sum in Prelude}
\NormalTok{    sum' []     }\FunctionTok{=} \DecValTok{0}
\NormalTok{    sum' (x}\FunctionTok{:}\NormalTok{xs) }\FunctionTok{=}\NormalTok{ x }\FunctionTok{+}\NormalTok{ sum' xs }
        
\OtherTok{    product' ::}\NormalTok{ [}\DataTypeTok{Integer}\NormalTok{] }\OtherTok{->} \DataTypeTok{Integer} \CommentTok{-- product in Prelude}
\NormalTok{    product' []     }\FunctionTok{=} \DecValTok{1} 
\NormalTok{    product' (x}\FunctionTok{:}\NormalTok{xs) }\FunctionTok{=}\NormalTok{ x }\FunctionTok{*}\NormalTok{ product' xs }
\end{Highlighting}
\end{Shaded}

Both \texttt{sum\textquotesingle{}} and
\texttt{product\textquotesingle{}} apply arithmetic operations to
integers. What about other operations with similar pattern of
computation?

Also consider a function \texttt{concat} that concatenates a list of
lists of some type into a list of that type with the order of the input
lists and their elements preserved.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    concat' ::}\NormalTok{ [[a]] }\OtherTok{->}\NormalTok{ [a]  }\CommentTok{-- concat in Prelude}
\NormalTok{    concat' []       }\FunctionTok{=}\NormalTok{  []}
\NormalTok{    concat' (xs}\FunctionTok{:}\NormalTok{xss) }\FunctionTok{=}\NormalTok{  xs }\FunctionTok{++}\NormalTok{ concat' xss}
\end{Highlighting}
\end{Shaded}

For example,

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    sum' [}\DecValTok{1}\NormalTok{,}\DecValTok{2}\NormalTok{,}\DecValTok{3}\NormalTok{]          }\FunctionTok{=}\NormalTok{ (}\DecValTok{1} \FunctionTok{+}\NormalTok{ (}\DecValTok{2} \FunctionTok{+}\NormalTok{ (}\DecValTok{3} \FunctionTok{+} \DecValTok{0}\NormalTok{)))}
\NormalTok{    product' [}\DecValTok{1}\NormalTok{,}\DecValTok{2}\NormalTok{,}\DecValTok{3}\NormalTok{]      }\FunctionTok{=}\NormalTok{ (}\DecValTok{1} \FunctionTok{*}\NormalTok{ (}\DecValTok{2} \FunctionTok{*}\NormalTok{ (}\DecValTok{3} \FunctionTok{*} \DecValTok{1}\NormalTok{)))}
\NormalTok{    concat' [}\StringTok{"1"}\NormalTok{,}\StringTok{"2"}\NormalTok{,}\StringTok{"3"}\NormalTok{] }\FunctionTok{=}\NormalTok{ (}\StringTok{"1"} \FunctionTok{++}\NormalTok{ (}\StringTok{"2"} \FunctionTok{++}\NormalTok{ (}\StringTok{"3"} \FunctionTok{++} \StringTok{""}\NormalTok{)))}
\end{Highlighting}
\end{Shaded}

What do \texttt{sum\textquotesingle{}},
\texttt{product\textquotesingle{}}, and
\texttt{concat\textquotesingle{}} have in common? What differs?

All exhibit the same pattern of computation.

\begin{itemize}
\item
  All take a list.

  But the element type differs. Function \texttt{sum\textquotesingle{}}
  takes a list of \texttt{Int}s, \texttt{product\textquotesingle{}}
  takes a list of \texttt{Integer}s, and
  \texttt{concat\textquotesingle{}} takes a polymorphic list.
\item
  All insert a binary operator between all the consecutive elements of
  the list in order to reduce the list to a single value.

  But the binary operation differs. Function
  \texttt{sum\textquotesingle{}}applies integer addition,
  \texttt{product\textquotesingle{}}applies integer multiplication, and
  \texttt{concat\textquotesingle{}} applies \texttt{++}.
\item
  All group the operations from the right to the left.
\item
  Each function returns some value for an empty list. The function
  extends nonempty input lists to implicitly include this value as the
  ``rightmost'' value of the input list.

  But the actual value differs.

  Function \texttt{sum\textquotesingle{}} returns integer 0, the (right)
  identity element for addition.

  Function \texttt{product\textquotesingle{}} returns 1, the (right)
  identity element for multiplication.

  Function \texttt{concat\textquotesingle{}} returns \texttt{{[}{]}},
  the (right) identity element for \texttt{++}.

  In general, this value could be something other than the identity
  element,
\item
  All return a value of the same element type as the input list.

  But the input type differs, as we noted above.
\end{itemize}

This group of functions inserts operations of type
\texttt{a\ -\textgreater{}\ a\ -\textgreater{}\ a} between elements a
list of type \texttt{{[}a{]}}.

But these are special cases of more general operations of type
\texttt{a\ -\textgreater{}\ b\ -\textgreater{}\ b}. In this case, the
value returned must be of type \texttt{b} in the case of both empty and
nonempty lists.

We can abstract the pattern of computation common to
\texttt{sum\textquotesingle{}}, \texttt{product\textquotesingle{}}, and
\texttt{concat’} as the function \texttt{foldr} (pronounced ``fold
right'') found in the Prelude. (Here we use \texttt{foldrX} to avoid the
name conflict.)

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    foldrX ::}\NormalTok{ (a }\OtherTok{->}\NormalTok{ b }\OtherTok{->}\NormalTok{ b) }\OtherTok{->}\NormalTok{ b }\OtherTok{->}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ b  }\CommentTok{-- foldr in Prelude}
\NormalTok{    foldrX f z []     }\FunctionTok{=}\NormalTok{ z}
\NormalTok{    foldrX f z (x}\FunctionTok{:}\NormalTok{xs) }\FunctionTok{=}\NormalTok{ f x (foldrX f z xs) }
\end{Highlighting}
\end{Shaded}

Function \texttt{foldr}:

\begin{itemize}
\item
  uses two type parameters \texttt{a} and \texttt{b} -- one for the type
  of elements in the list and one for the type of the result
\item
  passes in the general binary operation \texttt{f} (with type
  \texttt{a\ -\textgreater{}\ b\ -\textgreater{}\ b}) that combines
  (i.e., folds) the list elements
\item
  passes in the ``seed'' element \texttt{z} (of type \texttt{b}) to be
  returned for empty lists
\end{itemize}

The \texttt{foldr} function ``folds'' the list elements (of type
\texttt{a}) into a value (of type \texttt{b}) by ``inserting'' operation
\texttt{f} between the elements, with value \texttt{z} ``appended'' as
the rightmost element.

Often the seed value \texttt{z} is the right identity element for the
operation, but \texttt{foldr} may be useful in some circumstances where
it is not (or perhaps even if there is no right identity).

For example, \texttt{foldr\ f\ z\ {[}1,2,3{]}} expands to
\texttt{f\ 1\ (f\ 2\ (f\ 3\ z))}, or, using an infix style:

\begin{Shaded}
\begin{Highlighting}[]
    \DecValTok{1} \OtherTok{`f`}\NormalTok{ (}\DecValTok{2} \OtherTok{`f`}\NormalTok{ (}\DecValTok{3} \OtherTok{`f`}\NormalTok{ z)) }
\end{Highlighting}
\end{Shaded}

Function \texttt{foldr} does not depend upon \texttt{f} being
associative or having either a right or left identity.

Function \texttt{foldr} is backward recursive. If the function
application is fully evaluated, it needs a new stack frame for each
element of the input list. If its list argument is long or the folding
function itself is expensive, then the function can terminate with a
\emph{stack overflow} error.

In Haskell, \texttt{foldr} is called a \emph{fold} operation. Other
languages sometimes call this a \emph{reduce} or \emph{insert}
operation.

We can specialize \texttt{foldr} to restate the definitions for
\texttt{sum\textquotesingle{}}, \texttt{product\textquotesingle{}}, and
\texttt{concat’}.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    sum2 ::}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }\OtherTok{->} \DataTypeTok{Int}             \CommentTok{-- sum}
\NormalTok{    sum2 xs }\FunctionTok{=}\NormalTok{ foldrX (}\FunctionTok{+}\NormalTok{) }\DecValTok{0}\NormalTok{ xs}

\OtherTok{    product2 ::}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }\OtherTok{->} \DataTypeTok{Int}         \CommentTok{-- product}
\NormalTok{    product2 xs }\FunctionTok{=}\NormalTok{ foldrX (}\FunctionTok{*}\NormalTok{) }\DecValTok{1}\NormalTok{ xs}

\OtherTok{    concat2::}\NormalTok{ [[a]] }\OtherTok{->}\NormalTok{ [a]           }\CommentTok{-- concat}
\NormalTok{    concat2 xss }\FunctionTok{=}\NormalTok{ foldrX (}\FunctionTok{++}\NormalTok{) [] xss}
\end{Highlighting}
\end{Shaded}

As further examples, consider the folding of the Boolean operators
\texttt{\&\&} (``and'') and \texttt{\textbar{}\textbar{}} (``or'') over
lists of Boolean values as Prelude functions \texttt{and} and
\texttt{or} (shown as \texttt{and’} and \texttt{or’} below to avoid name
conflicts):

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    and',}\OtherTok{ or' ::}\NormalTok{ [}\DataTypeTok{Bool}\NormalTok{] }\OtherTok{->} \DataTypeTok{Bool}  \CommentTok{-- and, or in Prelude}
\NormalTok{    and' xs }\FunctionTok{=}\NormalTok{ foldrX (}\FunctionTok{&&}\NormalTok{) }\DataTypeTok{True}\NormalTok{ xs }
\NormalTok{    or'  xs }\FunctionTok{=}\NormalTok{ foldrX (}\FunctionTok{||}\NormalTok{) }\DataTypeTok{False}\NormalTok{ xs}
\end{Highlighting}
\end{Shaded}

Although their definitions look different, \texttt{and’} and
\texttt{or’} are actually identical to functions \texttt{and} and
\texttt{or} in the Prelude.

Consider the following questions.

\begin{itemize}
\item
  Under what circumstances does \texttt{foldrX\ f\ z\ xs} terminate? Do
  we have to assume anything about \texttt{f}? about \texttt{xs}?
\item
  What is the time complexity of \texttt{product2}? of \texttt{concat2}?
\end{itemize}

\subsubsection{\texorpdfstring{Using
\texttt{foldr}}{Using foldr}}\label{using-foldr}

The fold functions are very powerful. By choosing an appropriate folding
function argument, many different list functions can be implemented in
terms of \texttt{foldr}.

For example, we can implement \texttt{map} using \texttt{foldr} as
follows:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    map2 ::}\NormalTok{ (a }\OtherTok{->}\NormalTok{ b) }\OtherTok{->}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ [b] }\CommentTok{-- map}
\NormalTok{    map2 f xs }\FunctionTok{=}\NormalTok{ foldr mf [] xs }
        \KeywordTok{where}\NormalTok{ mf y ys }\FunctionTok{=}\NormalTok{ (f y) }\FunctionTok{:}\NormalTok{ ys}
\end{Highlighting}
\end{Shaded}

The folding function \texttt{mf\ y\ ys\ =\ (f\ y):ys} applies the
mapping function \texttt{f} to the next element of the list (moving
right to left) and attaches the result on the front of the processed
tail. This is a case where the folding function \texttt{mf} does not
have a right identity, but where \texttt{foldr} is quite useful.

We can also implement \texttt{filter} in terms of \texttt{foldr} as
follows:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    filter2 ::}\NormalTok{ (a }\OtherTok{->} \DataTypeTok{Bool}\NormalTok{) }\OtherTok{->}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ [a]  }\CommentTok{-- filter}
\NormalTok{    filter2 p xs }\FunctionTok{=}\NormalTok{ foldr ff [] xs}
        \KeywordTok{where}\NormalTok{ ff y ys }\FunctionTok{=} \KeywordTok{if}\NormalTok{ p y }\KeywordTok{then}\NormalTok{ (y}\FunctionTok{:}\NormalTok{ys) }\KeywordTok{else}\NormalTok{ ys}
\end{Highlighting}
\end{Shaded}

The folding function
\texttt{ff\ y\ ys\ =\ if\ p\ x\ then\ (y:ys)\ else\ ys} applies the
filter predicate \texttt{p} to the next element of the list (moving
right to left). If the predicate evaluates to \texttt{True}, the folding
function attaches that element on the front of the processed tail;
otherwise, it omits the element from the result.

We can also use \texttt{foldr} to compute the length of a polymorphic
list.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    length2 ::}\NormalTok{ [a] }\OtherTok{->} \DataTypeTok{Int}  \CommentTok{-- length}
\NormalTok{    length2 xs  }\FunctionTok{=}\NormalTok{ foldr len  }\DecValTok{0}\NormalTok{  xs}
        \KeywordTok{where}\NormalTok{ len _ acc }\FunctionTok{=}\NormalTok{ acc }\FunctionTok{+} \DecValTok{1}
\end{Highlighting}
\end{Shaded}

This uses the \texttt{z} parameter of \texttt{foldr} to initialize the
count to 0. Higher order argument \texttt{f} of \texttt{foldr} is a
function that takes an element of the list as its left argument and the
previous accumulator as its right argument and returns the accumulator
incremented by 1. In this application, \texttt{z} is not the identity
element for \texttt{f} but is a convenient beginning value for the
counter.

We can construct an ``append'' function that uses \texttt{foldr} as
follows:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    append2 ::}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ [a]  }\CommentTok{-- ++}
\NormalTok{    append2 xs ys }\FunctionTok{=}\NormalTok{ foldr (}\FunctionTok{:}\NormalTok{) ys xs}
\end{Highlighting}
\end{Shaded}

Here the the list that \texttt{foldr} operates on the first argument of
the append. The \texttt{z} parameter is the entire second argument and
the folding function is just \texttt{(:)}. So the effect is to replace
the \texttt{{[}{]}} at the end of the first list by the entire second
list.

Function \texttt{foldr} 1s a backward recursive function that processes
the elements of a list one by one. However, as we have seen, it is often
more useful to think of \texttt{foldr} as a powerful list operator that
reduces the element of the list into a single value. We can combine
\texttt{foldr} with other operators to conveniently construct list
processing programs.

\subsubsection{\texorpdfstring{Defining fold left
(\texttt{foldl})}{Defining fold left (foldl)}}\label{defining-fold-left-foldl}

We designed function \texttt{foldr} as a backward linear recursive
function with the signature:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    foldr ::}\NormalTok{ (a }\OtherTok{->}\NormalTok{ b }\OtherTok{->}\NormalTok{ b) }\OtherTok{->}\NormalTok{ b }\OtherTok{->}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ b}
\end{Highlighting}
\end{Shaded}

As noted:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    foldr f z [}\DecValTok{1}\NormalTok{,}\DecValTok{2}\NormalTok{,}\DecValTok{3}\NormalTok{] }\FunctionTok{==}\NormalTok{  f }\DecValTok{1}\NormalTok{ (f }\DecValTok{2}\NormalTok{ (f }\DecValTok{3}\NormalTok{ z))}
                      \FunctionTok{==}  \DecValTok{1} \OtherTok{`f`}\NormalTok{ (}\DecValTok{2} \OtherTok{`f`}\NormalTok{ (}\DecValTok{3} \OtherTok{`f`}\NormalTok{ z))}
\end{Highlighting}
\end{Shaded}

Consider a function \texttt{foldl} (pronounced ``fold left'') such that:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    foldl f z [}\DecValTok{1}\NormalTok{,}\DecValTok{2}\NormalTok{,}\DecValTok{3}\NormalTok{]  }\FunctionTok{==}\NormalTok{  f (f (f z }\DecValTok{1}\NormalTok{) }\DecValTok{2}\NormalTok{) }\DecValTok{3}
                       \FunctionTok{==}\NormalTok{  ((z }\OtherTok{`f`} \DecValTok{1}\NormalTok{) }\OtherTok{`f`} \DecValTok{2}\NormalTok{) }\OtherTok{`f`} \DecValTok{3}\OtherTok{`}
\end{Highlighting}
\end{Shaded}

This function folds from the left. It offers us the opportunity to use
parameter \texttt{z} as an accumulating parameter in a tail recursive
implementation. This is shown below as \texttt{foldlX}, which is similar
to \texttt{foldl} in the Prelude.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    foldlX ::}\NormalTok{ (a }\OtherTok{->}\NormalTok{ b }\OtherTok{->}\NormalTok{ a) }\OtherTok{->}\NormalTok{ a }\OtherTok{->}\NormalTok{ [b] }\OtherTok{->}\NormalTok{ a  }\CommentTok{-- foldl in Prelude}
\NormalTok{    foldlX f z []     }\FunctionTok{=}\NormalTok{ z  }
\NormalTok{    foldlX f z (x}\FunctionTok{:}\NormalTok{xs) }\FunctionTok{=}\NormalTok{ foldlX f (f z x) xs}
\end{Highlighting}
\end{Shaded}

Note how the second leg of \texttt{foldlX} implements the left binding
of the operation. In the recursive call of \texttt{foldlX} the ``seed
value'' argument is used as an accumulating parameter.

Also note how the types of \texttt{foldr} and \texttt{foldl} differ.

Often the beginning value of \texttt{z} is the left identity of the
operation \texttt{f}, but \texttt{foldl} (like \texttt{foldr}) can be a
quite useful function in circumstances when it is not (or when
\texttt{f} has no left identity).

\subsubsection{\texorpdfstring{Using
\texttt{foldl}}{Using foldl}}\label{using-foldl}

If \(\oplus\) is an associative binary operation of type
\texttt{t\ -\textgreater{}\ t\ -\textgreater{}\ t} with identity element
\texttt{z} (i.e., \(\oplus\) and \texttt{t} form the algebraic structure
know as a monoid), then, for any \texttt{xs},

\begin{quote}
\texttt{foldr\ (}\(\oplus\)\texttt{)\ z\ xs\ =\ foldl\ (}\(\oplus\)\texttt{)\ z\ xs}
\end{quote}

The classic Bird and Wadler textbook {[}Bird-Wadler, 1998{]} calls this
property the \emph{first duality theorem}.

Because \texttt{+}, \texttt{*}, and \texttt{++} are all associative
operations with identity elements, \texttt{sum}, \texttt{product}, and
\texttt{concat} can all be implemented with either \texttt{foldr} or
\texttt{foldl}.

Which is better?

Depending upon the nature of the operation, an implementation using
\texttt{foldr} may be more efficient than \texttt{foldl} or vice versa.

We defer a more complete discussion of the efficiency until we study
evaluation strategies further in a later chapter.

As a rule of thumb, however, if the operation \(\oplus\) is
\emph{nonstrict} in either argument, then it is usually better to use
\texttt{foldr}. That form takes better advantage of lazy evaluation.

If the operation \(\oplus\) is \emph{strict} in both arguments, then it
is often better (i.e., more efficient) to use the optimized version of
\texttt{foldl} called \texttt{foldl\textquotesingle{}} from the standard
Haskell module \texttt{Data.List}.

The append operation \texttt{++} is nonstrict in its second argument, so
it is better to use \texttt{foldr} to implement \texttt{concat}.

Addition and multiplication are strict in both arguments, so we can
implement \texttt{sum} and \texttt{product} functions efficiently with
\texttt{foldl\textquotesingle{}}, as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{import }\DataTypeTok{Data.List}   \CommentTok{-- to make foldl' available}
\NormalTok{    sum3,}\OtherTok{ product3 ::} \DataTypeTok{Num}\NormalTok{ a }\OtherTok{=>}\NormalTok{  [a] }\OtherTok{->}\NormalTok{ a }\CommentTok{-- sum, product}
\NormalTok{    sum3 xs     }\FunctionTok{=}\NormalTok{ foldl' (}\FunctionTok{+}\NormalTok{) }\DecValTok{0}\NormalTok{ xs}
\NormalTok{    product3 xs }\FunctionTok{=}\NormalTok{ foldl' (}\FunctionTok{*}\NormalTok{) }\DecValTok{1}\NormalTok{ xs}
\end{Highlighting}
\end{Shaded}

Note that we generalize these functions to operate on polymorphic lists
with a base type in class \texttt{Num}. Class \texttt{Num} includes all
numeric types.

Function \texttt{length3} uses \texttt{foldl}. It is like
\texttt{length2} except that the arguments of function \texttt{len} are
reversed.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    length3 ::}\NormalTok{ [a] }\OtherTok{->} \DataTypeTok{Int}  \CommentTok{-- length}
\NormalTok{    length3 xs  }\FunctionTok{=}\NormalTok{ foldl len }\DecValTok{0}\NormalTok{  xs}
        \KeywordTok{where}\NormalTok{ len acc _ }\FunctionTok{=}\NormalTok{ acc }\FunctionTok{+} \DecValTok{1}
\end{Highlighting}
\end{Shaded}

However, it is usually better to use the \texttt{foldr} version
\texttt{length2} because the folding function \texttt{len} is nonstrict
in the argument corresponding to the list.

We can also implement list reversal using \texttt{foldl} as follows:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    reverse2 ::}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ [a]  }\CommentTok{-- reverse}
\NormalTok{    reverse2 xs }\FunctionTok{=}\NormalTok{ foldl rev [] xs}
        \KeywordTok{where}\NormalTok{ rev acc x }\FunctionTok{=}\NormalTok{ (x}\FunctionTok{:}\NormalTok{acc) }
\end{Highlighting}
\end{Shaded}

This gives a solution similar to the tail recursive \texttt{reverse}
function from a previous chapter. Function \texttt{foldl}'s \texttt{z}
parameter is initially an empty list; \texttt{foldl}'s folding function
parameter \texttt{f} uses \texttt{(:)} to ``attach'' each element of the
list as the new head of the accumulator, incrementally building the list
in reverse order.

Although cons is nonstrict in its right operand, \texttt{reverse2}
builds up that argument from \texttt{{[}{]}}, so \texttt{reverse2}
cannot take advantage of lazy evaluation by using \texttt{foldr}
instead.

To avoid a stack overflow situation with \texttt{foldr}, we can first
apply \texttt{reverse} to the list argument and then apply
\texttt{foldl} as follows:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    foldr2 ::}\NormalTok{ (a }\OtherTok{->}\NormalTok{ b }\OtherTok{->}\NormalTok{ b) }\OtherTok{->}\NormalTok{ b }\OtherTok{->}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ b  }\CommentTok{-- foldr}
\NormalTok{    foldr2 f z xs }\FunctionTok{=}\NormalTok{ foldl flipf z (reverse xs)}
        \KeywordTok{where}\NormalTok{ flipf y x }\FunctionTok{=}\NormalTok{ f x y}
\end{Highlighting}
\end{Shaded}

The combining function in the call to \texttt{foldl} is the same as the
one passed to \texttt{foldr} except that its arguments are reversed.

\subsubsection{\texorpdfstring{Defining \texttt{concatMap}
(flatmap)}{Defining concatMap (flatmap)}}\label{defining-concatmap-flatmap}

The higher-order function \texttt{map} applies its function argument
\texttt{f} to every element of a list and returns the list of results.
If the function argument \texttt{f} returns a list, then the result is a
list of lists. Often we wish to flatten this into a single list, that
is, apply a function like \texttt{concat} defined in a previous section.

This computation is sufficiently common that we give it the name
\texttt{concatMap}. We can define it in terms of \texttt{map} and
\texttt{concat} as

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    concatMap' ::}\NormalTok{ (a }\OtherTok{->}\NormalTok{ [b]) }\OtherTok{->}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ [b] }
\NormalTok{    concatMap' f xs }\FunctionTok{=}\NormalTok{ concat (map f xs)}
\end{Highlighting}
\end{Shaded}

or by combining \texttt{map} and \texttt{concat} into one \texttt{foldr}
as:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    concatMap2 ::}\NormalTok{ (a }\OtherTok{->}\NormalTok{ [b]) }\OtherTok{->}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ [b] }
\NormalTok{    concatMap2 f xs }\FunctionTok{=}\NormalTok{ foldr fmf [] xs }
        \KeywordTok{where}\NormalTok{ fmf x ys }\FunctionTok{=}\NormalTok{ f x }\FunctionTok{++}\NormalTok{ ys}
\end{Highlighting}
\end{Shaded}

Above, the function argument to \texttt{foldr} applies the
\texttt{concatMap} function argument \texttt{f} to each element of the
list argument and then appends the resulting list in front of the result
from processing the elements to the right.

We can also define \texttt{filter} in terms of \texttt{concatMap} as
follows:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    filter3 ::}\NormalTok{ (a }\OtherTok{->} \DataTypeTok{Bool}\NormalTok{) }\OtherTok{->}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ [a]}
\NormalTok{    filter3 p xs }\FunctionTok{=}\NormalTok{ concatMap' fmf xs}
        \KeywordTok{where}\NormalTok{ fmf x }\FunctionTok{=} \KeywordTok{if}\NormalTok{ p x }\KeywordTok{then}\NormalTok{ [x] }\KeywordTok{else}\NormalTok{ []}
\end{Highlighting}
\end{Shaded}

The function argument to \texttt{concatMap} generates a one-element list
if the filter predicate \texttt{p} is true and an empty list if it is
false.

Some other languages (e.g., Scala) call the \texttt{concatMap} function
by the name \texttt{flatmap}.

\subsection{Haskell Function Concepts and
Notation}\label{haskell-function-concepts-and-notation}

\subsubsection{Strictness}\label{strictness}

Some expressions cannot be reduced to a simple value, for example,
\texttt{div\ 1\ 0}. The attempted evaluation of such expressions either
return an error immediately or cause the interpreter to go into an
``infinite loop''.

In our discussions of functions, it is often convenient to assign the
symbol \(\bot\) (pronounced ``bottom'') as the value of expressions like
\texttt{div\ 1\ 0}. We use \(\bot\) is a polymorphic symbo--as a value
of every type.

The symbol \(\bot\) is not in the Haskell syntax and the interpreter
cannot actually generate the value \(\bot\). It is merely a name for the
value of an expression in situations where the expression cannot really
be evaluated. It's use is somewhat analogous to use of symbols such as
\(\infty\) in mathematics.

Although we cannot actually produce the value \(\bot\), we can,
conceptually at least, apply any function to \(\bot\).

If \texttt{f} \(\bot = \bot\), then we say that the function is
\emph{strict}; otherwise, it is \emph{nonstrict} (sometimes called
\emph{lenient}).

That is, a strict argument of a function must be evaluated before the
final result can be computed. A nonstrict argument of a function may not
need to be evaluated to compute the final result.

Assume that lazy evaluation is being used and consider the function
\texttt{two} that takes an argument of any type and returns the integer
value two.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    two ::}\NormalTok{ a }\OtherTok{->} \DataTypeTok{Int} 
\NormalTok{    two x }\FunctionTok{=} \DecValTok{2}
\end{Highlighting}
\end{Shaded}

The function \texttt{two} is nonstrict. The argument expression is not
evaluated to compute the final result. Hence, \texttt{two} \(\bot = 2\).

Consider the following examples.

\begin{itemize}
\item
  The arithmetic operations (e.g., \texttt{+}) are strict in both
  arguments.
\item
  Function \texttt{rev} (discussed in a previous chapter) is strict in
  its one argument.
\item
  Operation \texttt{++} is strict in its first argument, but nonstrict
  in its second argument.
\item
  Boolean functions \texttt{\&\&} and \texttt{\textbar{}\textbar{}} from
  the Prelude are also strict in their first arguments and nonstrict in
  their second arguments.

  \textsubscript{\textasciitilde{}}\{.haskell\} (\&\&),
  (\textbar{}\textbar{}) :: Bool -\textgreater{} Bool -\textgreater{}
  Bool False \&\& x = False -- second argument not evaluated True \&\& x
  = x

\begin{verbatim}
False || x = x 
True  || x = True   -- second argument not evaluated
\end{verbatim}

  \textsubscript{\textasciitilde{}}
\end{itemize}

\subsubsection{Currying and partial
application}\label{currying-and-partial-application}

Consider the following two functions:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    add ::}\NormalTok{ (}\DataTypeTok{Int}\NormalTok{,}\DataTypeTok{Int}\NormalTok{) }\OtherTok{->} \DataTypeTok{Int} 
\NormalTok{    add (x,y) }\FunctionTok{=}\NormalTok{ x }\FunctionTok{+}\NormalTok{ y }

\OtherTok{    add' ::} \DataTypeTok{Int} \OtherTok{->}\NormalTok{ (}\DataTypeTok{Int} \OtherTok{->} \DataTypeTok{Int}\NormalTok{) }
\NormalTok{    add' x y  }\FunctionTok{=}\NormalTok{ x }\FunctionTok{+}\NormalTok{ y }
\end{Highlighting}
\end{Shaded}

These functions are closely related, but they are not identical.

For all integers \texttt{x} and \texttt{y},
\texttt{add\ (x,y)\ =\ add’\ x\ y}. But functions \texttt{add} and
\texttt{add’} have different types.

Function \texttt{add} takes a 2-tuple \texttt{(Int,Int)} and returns an
\texttt{Int}. Function \texttt{add’} takes an \texttt{Int} and returns a
function of type \texttt{Int\ -\textgreater{}\ Int}.

What is the result of the application \texttt{add\ 3}? An error.

What is the result of the application \texttt{add’\ 3}? The result is a
function that ``adds 3 to its argument''.

What is the result of the application \texttt{(add’\ 3)\ 4}? The result
is the integer value .

By convention, function application (denoted by the juxtaposition of a
function and its argument) binds to the left. That is,
\texttt{add’\ x\ y\ =\ ((add’\ x)\ y)}.

Hence, the higher-order functions in Haskell allow us to replace any
function that takes a tuple argument by an equivalent function that
takes a sequence of simple arguments corresponding to the components of
the tuple. This process is called \emph{currying}. It is named after
American logician Haskell B. Curry, who first exploited the technique.

Function \texttt{add’} above is similar to the function \texttt{(+)}
from the Prelude (i.e., the addition operator).

We sometimes speak of the function \texttt{(+)} as being \emph{partially
applied} in the expression \texttt{((+)\ 3)}. In this expression, the
first argument of the function is ``frozen in'' and the resulting
function can be passed as an argument, returned as a result, or applied
to another argument.

Partially applied functions are very useful in conjunction with other
higher-order functions.

For example, consider the partial applications of the relational
comparison operator \texttt{(\textless{})} and multiplication operator
\texttt{(*)} in the function \texttt{doublePos3}. This function, which
is equivalent to the function \texttt{doublePos} discussed in an earlier
subsection, doubles the positive integers in a list:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    doublePos3 ::}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }\OtherTok{->}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }
\NormalTok{    doublePos3 xs }\FunctionTok{=}\NormalTok{ map' ((}\FunctionTok{*}\NormalTok{) }\DecValTok{2}\NormalTok{) (filter' ((}\FunctionTok{<}\NormalTok{) }\DecValTok{0}\NormalTok{) xs) }
\end{Highlighting}
\end{Shaded}

Related to the concept of currying is the \emph{property of
extensionality}. Two functions \texttt{f} and \texttt{g} are
extensionally equal if \texttt{f\ x\ =\ g\ x} for all \texttt{x}.

Thus instead of writing the definition of \texttt{g} as

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    f,}\OtherTok{ g ::}\NormalTok{ a }\OtherTok{->}\NormalTok{ a}
\NormalTok{    f x }\FunctionTok{=}\NormalTok{ some_expression}

\NormalTok{    g x }\FunctionTok{=}\NormalTok{ f x}
\end{Highlighting}
\end{Shaded}

we can write the definition of \texttt{g} as simply:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    g }\FunctionTok{=}\NormalTok{ f}
\end{Highlighting}
\end{Shaded}

\subsubsection{Operator sections}\label{operator-sections}

Expressions such as \texttt{((*)\ 2)} and \texttt{((\textless{})\ 0)},
used in the definition of \texttt{doublePos3} in the previous
subsection, can be a bit confusing because we normally use these
operators in infix form. (In particular, it is difficult to remember
that \texttt{((\textless{})\ 0)} returns \texttt{True} for positive
integers.)

Also, it would be helpful to be able to use the division operator to
express a function that halves (i.e., divides by two) its operand. The
function \texttt{((/)\ 2)} does not do it; it divides 2 by its operand.

We can use the function \texttt{flip} from the Prelude to state the
halving operation. Function \texttt{flip} takes a function and two
additional arguments and applies the argument function to the two
arguments with their order reversed.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    flip' ::}\NormalTok{ (a }\OtherTok{->}\NormalTok{ b }\OtherTok{->}\NormalTok{ c) }\OtherTok{->}\NormalTok{ b }\OtherTok{->}\NormalTok{ a }\OtherTok{->}\NormalTok{ c  }\CommentTok{-- flip in Prelude}
\NormalTok{    flip' f x y }\FunctionTok{=}\NormalTok{ f y x}
\end{Highlighting}
\end{Shaded}

Thus we can express the halving operator with the expression
\texttt{(flip\ (/)\ 2)}.

Because expressions such as \texttt{((\textless{})\ 0)} and
\texttt{(flip\ (/)\ 2)} are quite common in programs, Haskell provides a
special, more compact and less confusing, syntax.

For some infix operator \(\oplus\) and arbitrary expression \texttt{e},
expressions of the form \texttt{(e}\(\oplus\)\texttt{)} and
\texttt{(}\(\oplus\)\texttt{e)} represent
\texttt{((}\(\oplus\)\texttt{)\ e)} and
\texttt{(flip\ (}\(\oplus\)\texttt{)\ e)}, respectively. Expressions of
this form are called \emph{operator sections}.

Examples of operator sections include:

\begin{quote}
\texttt{(1+)} is the successor function, which returns the value of its
argument plus 1.
\end{quote}

\begin{quote}
\texttt{(0\textless{})} is a test for a positive integer.
\end{quote}

\begin{quote}
\texttt{(/2)} is the halving function.
\end{quote}

\begin{quote}
\texttt{(1.0/)} is the reciprocal function.
\end{quote}

\begin{quote}
\texttt{(:{[}{]})} is the function that returns the singleton list
containing the argument.
\end{quote}

Suppose we want to sum the cubes of list of integers. We can express the
function in the following way:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    sumCubes ::}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }\OtherTok{->} \DataTypeTok{Int} 
\NormalTok{    sumCubes xs }\FunctionTok{=}\NormalTok{ sum' (map' (}\FunctionTok{^}\DecValTok{3}\NormalTok{) xs)}
\end{Highlighting}
\end{Shaded}

Above \texttt{\^{}} is the exponentiation operator and \texttt{sum} is
the list summation function defined in the Prelude as:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    sum' }\FunctionTok{=}\NormalTok{ foldl' (}\FunctionTok{+}\NormalTok{) }\DecValTok{0}  \CommentTok{-- sum}
\end{Highlighting}
\end{Shaded}

\subsubsection{Combinators}\label{combinators}

The function \texttt{flip} in the previous subsection is an example of a
useful type of function called a combinator.

A \emph{combinator} is a function without any free variables. That is,
on right side of a defining equation there are no variables or operator
symbols that are not bound on the left side of the equation.

For historical reasons, \texttt{flip} is sometimes called the \texttt{C}
combinator.

There are several other useful combinators in the Prelude.

The combinator \texttt{const} (shown below as \texttt{const’}) is the
constant function constructor; it is a two-argument function that
returns its first argument. For historical reasons, this combinator is
sometimes called the \texttt{K} combinator.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    const' ::}\NormalTok{ a }\OtherTok{->}\NormalTok{ b }\OtherTok{->}\NormalTok{ a  }\CommentTok{-- const in Prelude}
\NormalTok{    const' k x }\FunctionTok{=}\NormalTok{ k}
\end{Highlighting}
\end{Shaded}

Example: \texttt{(const\ 1)} takes any argument and returns the value 1.

Question: What does \texttt{sum\ (map\ (const\ 1)\ xs)} do?

Function \texttt{id} (shown below as \texttt{id’}) is the identity
function; it is a one-argument function that returns its argument
unmodified. For historical reasons, this function is sometimes called
the \texttt{I} combinator.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    id' ::}\NormalTok{ a }\OtherTok{->}\NormalTok{ a  }\CommentTok{-- id in Prelude}
\NormalTok{    id' x }\FunctionTok{=}\NormalTok{ x}
\end{Highlighting}
\end{Shaded}

Combinators \texttt{fst} and \texttt{snd} (shown below as \texttt{fst’}
and \texttt{snd’}) extract the first and second components,
respectively, of 2-tuples.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    fst' ::}\NormalTok{ (a,b) }\OtherTok{->}\NormalTok{ a  }\CommentTok{-- fst in Prelude}
\NormalTok{    fst' (x,_) }\FunctionTok{=}\NormalTok{ x }

\OtherTok{    snd' ::}\NormalTok{ (a,b) }\OtherTok{->}\NormalTok{ b  }\CommentTok{-- snd in Prelude}
\NormalTok{    snd' (_,y) }\FunctionTok{=}\NormalTok{ y}
\end{Highlighting}
\end{Shaded}

Similarly, \texttt{fst3}, \texttt{snd3}, and \texttt{thd3} extract the
first, second, and third components, respectively, of 3-tuples.

An interesting example that uses a combinator is the function
\texttt{reverse} as defined in the Prelude (shown below as
\texttt{reverse’}):

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    reverse' ::}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ [a]          }\CommentTok{-- reverse in Prelude}
\NormalTok{    reverse' }\FunctionTok{=}\NormalTok{ foldlX (flip' (}\FunctionTok{:}\NormalTok{)) []}
\end{Highlighting}
\end{Shaded}

Function \texttt{flip\ (:)} takes a list on the left and an element on
the right. As this operation is folded through the list from the left it
attaches each element as the new head of the list.

We can also define combinators that convert an uncurried function into a
curried function and vice versa. The functions
\texttt{curry\textquotesingle{}} and \texttt{uncurry\textquotesingle{}}
defined below are similar to the Prelude functions.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    curry' ::}\NormalTok{ ((a, b) }\OtherTok{->}\NormalTok{ c) }\OtherTok{->}\NormalTok{ a }\OtherTok{->}\NormalTok{ b }\OtherTok{->}\NormalTok{ c }\CommentTok{-- curry in Prelude }
\NormalTok{    curry' f x y }\FunctionTok{=}\NormalTok{  f (x, y) }

\OtherTok{    uncurry' ::}\NormalTok{ (a }\OtherTok{->}\NormalTok{ b }\OtherTok{->}\NormalTok{ c) }\OtherTok{->}\NormalTok{ ((a, b) }\OtherTok{->}\NormalTok{ c) }\CommentTok{-- uncurry in Prelude }
\NormalTok{    uncurry' f p }\FunctionTok{=}\NormalTok{  f (fst p) (snd p) }
\end{Highlighting}
\end{Shaded}

Two other useful combinators are \texttt{fork} and \texttt{cross}.
Combinator \texttt{fork} applies each component of a pair of functions
to a value to create a pair of results. Combinator \texttt{cross}
applies each component of a pair of functions to the corresponding
components of a pair of values to create a pair of results. We can
define these as follows:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    fork ::}\NormalTok{ (a }\OtherTok{->}\NormalTok{ b, a }\OtherTok{->}\NormalTok{ c) }\OtherTok{->}\NormalTok{ a }\OtherTok{->}\NormalTok{ (b,c)}
\NormalTok{    fork (f,g) x }\FunctionTok{=}\NormalTok{ (f x, g x)}

\OtherTok{    cross ::}\NormalTok{ (a }\OtherTok{->}\NormalTok{ b, c }\OtherTok{->}\NormalTok{ d) }\OtherTok{->}\NormalTok{ (a,c) }\OtherTok{->}\NormalTok{ (b,d)}
\NormalTok{    cross (f,g) (x,y) }\FunctionTok{=}\NormalTok{ (f x, g y)}
\end{Highlighting}
\end{Shaded}

\subsubsection{Functional composition}\label{functional-composition}

The functional composition operator allows several ``smaller'' functions
to be combined to form ``larger'' functions. In Haskell, this combinator
is denoted by the period (\texttt{.}) symbol and is defined in the
Prelude as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{infixr} \DecValTok{9} \FunctionTok{.} 
\OtherTok{    (.) ::}\NormalTok{ (b }\OtherTok{->}\NormalTok{ c) }\OtherTok{->}\NormalTok{ (a }\OtherTok{->}\NormalTok{ b) }\OtherTok{->}\NormalTok{ (a }\OtherTok{->}\NormalTok{ c) }
\NormalTok{    (f }\FunctionTok{.}\NormalTok{ g) x }\FunctionTok{=}\NormalTok{ f (g x) }
\end{Highlighting}
\end{Shaded}

Composition's default binding is from the right and its precedence is
higher than all the operators we have discussed so far except function
application itself.

Functional composition is an associative binary operation with the
identity function \texttt{id} as its identity element:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{     f }\FunctionTok{.}\NormalTok{ (g }\FunctionTok{.}\NormalTok{ h) }\FunctionTok{=}\NormalTok{ (f }\FunctionTok{.}\NormalTok{ g) }\FunctionTok{.}\NormalTok{ h }
\NormalTok{     id }\FunctionTok{.}\NormalTok{ f  }\FunctionTok{=}\NormalTok{ f }\FunctionTok{.}\NormalTok{ id}
\end{Highlighting}
\end{Shaded}

An advantage of the use of functional composition is that some
expressions can be written more concisely. For example, the function

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    doit x }\FunctionTok{=}\NormalTok{ f1 (f2 (f3 (f4 x))) }
\end{Highlighting}
\end{Shaded}

can be written more concisely as:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    doit }\FunctionTok{=}\NormalTok{ f1 }\FunctionTok{.}\NormalTok{ f2 }\FunctionTok{.}\NormalTok{ f3 }\FunctionTok{.}\NormalTok{ f4 }
\end{Highlighting}
\end{Shaded}

This latter definition is in what is called the \emph{point-free style}.
It defines function \texttt{doit} as being equal to the composition of
the other functions. It leaves the parameters (i.e., the points) of
\texttt{doit} as implicit; \texttt{doit} has the same parameters as the
composition.

The former definition (that gives all the explicit parameters) is in
what is called \emph{pointful style}.

If \texttt{doit} is defined in point-free style as above, then we can
use the function in expressions such as \texttt{map\ (doit)\ xs}. Of
course, if this is the only use of the \texttt{doit} function, we can
eliminate it completely and use the composition directly, e.g.,
\texttt{map\ (f1\ .\ f2\ .\ f3\ .\ f4)\ xs}.

As an example, consider the function \texttt{count} that takes two
arguments, an integer \texttt{n} and a list of lists, and returns the
number of the lists from the second argument that are of length
\texttt{n}. Note that all functions composed below are single-argument
functions: \texttt{length}, \texttt{(filter\ (==\ n))},
\texttt{(map\ length)}.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    count ::} \DataTypeTok{Int} \OtherTok{->}\NormalTok{ [[a]] }\OtherTok{->} \DataTypeTok{Int} 
\NormalTok{    count n }
        \FunctionTok{|}\NormalTok{ n }\FunctionTok{>=} \DecValTok{0}    \FunctionTok{=}\NormalTok{ length' }\FunctionTok{.}\NormalTok{ filter' (}\FunctionTok{==}\NormalTok{ n) }\FunctionTok{.}\NormalTok{ map' length' }
        \FunctionTok{|}\NormalTok{ otherwise }\FunctionTok{=}\NormalTok{ const' }\DecValTok{0}   \CommentTok{-- discard 2nd arg, return 0 }
\end{Highlighting}
\end{Shaded}

We can think of the point-free expression
\texttt{length\textquotesingle{}\ .\ filter\textquotesingle{}\ (==\ n)\ .\ map\textquotesingle{}\ length\textquotesingle{}}
as defining a \emph{function pipeline} through which data flows from
right to left.

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  The pipeline takes a polymorphic list of lists as input.
\item
  The \texttt{map\textquotesingle{}\ length\textquotesingle{}} component
  of the pipeline replaces each inner list by its length.
\item
  The \texttt{filter\textquotesingle{}\ (==\ n)} component takes the
  list created by the previous step and removes all elements not equal
  to \texttt{n}.
\item
  The \texttt{length\textquotesingle{}} component takes the list created
  by the previous step and determines how many elements are remaining.
\item
  The pipeline outputs the value computed by the previous component. The
  number of lists within the input list of lists that are of length
  \texttt{n}.
\end{enumerate}

Thus composition is a powerful form of ``glue'' that can be used to
``stick'' simpler functions together to build more powerful functions.
The simpler functions in this case include partial applications of
higher order functions from the library we have developed.

As we see above in the definition of \texttt{count}, partial
applications (e.g., \texttt{filter\ (==\ n)}), operator sections (e.g.,
\texttt{(==\ n)}), and combinators (e.g., \texttt{const}) are useful as
\emph{plumbing} the function pipeline.

Remember the function \texttt{doublePos} that we discussed in earlier
subsections.

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    doublePos3 xs }\FunctionTok{=}\NormalTok{ map' ((}\FunctionTok{*}\NormalTok{) }\DecValTok{2}\NormalTok{) (filter' ((}\FunctionTok{<}\NormalTok{) }\DecValTok{0}\NormalTok{) xs) }
\end{Highlighting}
\end{Shaded}

Using composition, partial application, and operator sections we can
restate its definition in point-free style as follows:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    doublePos4 ::}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }\OtherTok{->}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }
\NormalTok{    doublePos4 }\FunctionTok{=}\NormalTok{ map' (}\DecValTok{2}\FunctionTok{*}\NormalTok{) }\FunctionTok{.}\NormalTok{ filter' (}\DecValTok{0}\FunctionTok{<}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

Consider a function \texttt{last} to return the last element in a
non-nil list and a function \texttt{init} to return the initial segment
of a non-nil list (i.e., everything except the last element). These
could quickly and concisely be written as follows:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    last' }\FunctionTok{=}\NormalTok{ head }\FunctionTok{.}\NormalTok{ reverse'            }\CommentTok{-- last in Prelude}
\NormalTok{    init' }\FunctionTok{=}\NormalTok{ reverse' }\FunctionTok{.}\NormalTok{ tail }\FunctionTok{.}\NormalTok{ reverse' }\CommentTok{-- init in Prelude}
\end{Highlighting}
\end{Shaded}

However, since these definitions are not very efficient, the Prelude
implements functions \texttt{last} and \texttt{init} in a more direct
and efficient way similar to the following:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    last2 ::}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ a    }\CommentTok{-- last in Prelude}
\NormalTok{    last2 [x]    }\FunctionTok{=}\NormalTok{ x }
\NormalTok{    last2 (_}\FunctionTok{:}\NormalTok{xs) }\FunctionTok{=}\NormalTok{ last2 xs }

\OtherTok{    init2 ::}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ [a]  }\CommentTok{-- init in Prelude}
\NormalTok{    init2 [x]    }\FunctionTok{=}\NormalTok{ [] }
\NormalTok{    init2 (x}\FunctionTok{:}\NormalTok{xs) }\FunctionTok{=}\NormalTok{ x }\FunctionTok{:}\NormalTok{ init2 xs }
\end{Highlighting}
\end{Shaded}

The definitions for Prelude functions \texttt{any} and \texttt{all} are
similar to the definitions show below; they take a predicate and a list
and apply the predicate to each element of the list, returning
\texttt{True} when any and all, respectively, of the individual tests
evaluate to \texttt{True}.

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    any',}\OtherTok{ all' ::}\NormalTok{ (a }\OtherTok{->} \DataTypeTok{Bool}\NormalTok{) }\OtherTok{->}\NormalTok{ [a] }\OtherTok{->} \DataTypeTok{Bool} 
\NormalTok{    any' p }\FunctionTok{=}\NormalTok{ or' }\FunctionTok{.}\NormalTok{ map' p   }\CommentTok{-- any in Prelude}
\NormalTok{    all' p }\FunctionTok{=}\NormalTok{ and' }\FunctionTok{.}\NormalTok{ map' p  }\CommentTok{-- all in Prelude}
\end{Highlighting}
\end{Shaded}

The functions \texttt{elem} and \texttt{notElem} test for an object
being an element of a list and not an element, respectively. They are
defined in the Prelude similarly to the following:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    elem',}\OtherTok{ notElem' ::} \DataTypeTok{Eq}\NormalTok{ a }\OtherTok{=>}\NormalTok{ a }\OtherTok{->}\NormalTok{ [a] }\OtherTok{->} \DataTypeTok{Bool} 
\NormalTok{    elem'    }\FunctionTok{=}\NormalTok{ any' }\FunctionTok{.}\NormalTok{ (}\FunctionTok{==}\NormalTok{)  }\CommentTok{-- elem in Prelude}
\NormalTok{    notElem' }\FunctionTok{=}\NormalTok{ all' }\FunctionTok{.}\NormalTok{ (}\FunctionTok{/=}\NormalTok{)  }\CommentTok{-- notElem in Prelude}
\end{Highlighting}
\end{Shaded}

These are a bit more difficult to understand since \texttt{any},
\texttt{all}, \texttt{==}, and \texttt{/=} are two-argument functions.
Note that expression \texttt{elem\ x\ xs} would be evaluated as follows:

\begin{longtable}[]{@{}ll@{}}
\toprule
& \texttt{elem’\ x\ xs}\tabularnewline
\(\Longrightarrow\) & \{ expand \texttt{elem’} \}\tabularnewline
& \texttt{(any’\ .\ (==))\ x\ xs}\tabularnewline
\(\Longrightarrow\) & \{ expand composition \}\tabularnewline
& \texttt{any’\ ((==)\ x)\ xs}\tabularnewline
\bottomrule
\end{longtable}

The composition operator binds the first argument with \texttt{(==)} to
construct the first argument to \texttt{any’}. The second argument of
\texttt{any’} is the second argument of \texttt{elem’}.

\subsubsection{Lambda expressions}\label{lambda-expressions}

Remember the function \texttt{squareAll2} we examined in an earlier
subsection on maps:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    squareAll2 ::}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }\OtherTok{->}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }
\NormalTok{    squareAll2 xs }\FunctionTok{=}\NormalTok{ map' sq xs }
                    \KeywordTok{where}\NormalTok{ sq x }\FunctionTok{=}\NormalTok{ x }\FunctionTok{*}\NormalTok{ x }
\end{Highlighting}
\end{Shaded}

We introduced the local function definition \texttt{sq} to denote the
function to be passed to \texttt{map}. It seems to be a waste of effort
to introduce a new symbol for a simple function that is only used in one
place in an expression. Would it not be better, somehow, to just give
the defining expression itself in the argument position?

Haskell provides a mechanism to do just that, an anonymous function
definition. For historical reasons, these nameless functions are called
\emph{lambda expressions}. They begin with a backslash
\texttt{\textbackslash{}} and have the syntax:

\begin{quote}
\texttt{\textbackslash{}} \emph{atomicPatterns} \texttt{-\textgreater{}}
\emph{expression}
\end{quote}

For example, the squaring function (\texttt{sq}) could be replaced by a
lambda expression as
\texttt{(\textbackslash{}x\ -\textgreater{}\ x\ *\ x)}. The pattern
\texttt{x} represents the single argument for this anonymous function
and the expression \texttt{x\ *\ x} is its result.

Thus we can rewrite \texttt{squareAll2} in point-free style using a
lambda expression as follows:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    squareAll3 ::}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }\OtherTok{->}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{] }
\NormalTok{    squareAll3 }\FunctionTok{=}\NormalTok{ map' (\textbackslash{}x }\OtherTok{->}\NormalTok{ x }\FunctionTok{*}\NormalTok{ x)}
\end{Highlighting}
\end{Shaded}

A lambda expression to average two numbers can be written
\texttt{(\textbackslash{}x\ y\ -\textgreater{}\ (x+y)/2)}.

An interesting example that uses a lambda expression is the function
\texttt{length} as defined in the Prelude--similar to \texttt{length4}
below. (Note that this uses the optimized function
\texttt{foldl\textquotesingle{}} from the standard Haskell
\texttt{Data.List} module.)

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    length4 ::}\NormalTok{ [a] }\OtherTok{->} \DataTypeTok{Int}   \CommentTok{-- length in Prelude}
\NormalTok{    length4  }\FunctionTok{=}\NormalTok{ foldl' (\textbackslash{}n _ }\OtherTok{->}\NormalTok{ n}\FunctionTok{+}\DecValTok{1}\NormalTok{) }\DecValTok{0}
\end{Highlighting}
\end{Shaded}

The anonymous function
\texttt{(\textbackslash{}n\ \_\ -\textgreater{}\ n+1)} takes an integer
``counter'' and a polymorphic value and returns the ``counter''
incremented by one. As this function is folded through the list from the
left, this function counts each element of the second argument.

\subsubsection{\texorpdfstring{Application operator
\texttt{\$}}{Application operator \$}}\label{application-operator}

In Haskell, function application associates to the left and has higher
binding power than any infix operator. For example, for some function
two-argument function \texttt{f} and values \texttt{w}, \texttt{x},
\texttt{y}, and \texttt{z}

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    w }\FunctionTok{+}\NormalTok{ f x y }\FunctionTok{*}\NormalTok{ z}
\end{Highlighting}
\end{Shaded}

is the same as

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    w }\FunctionTok{+}\NormalTok{ (((f x) y) }\FunctionTok{*}\NormalTok{ z)}
\end{Highlighting}
\end{Shaded}

given the relative binding powers of function application and the
numeric operators.

However, sometimes we want to be able to use function application where
it associates to the right and binds less tightly than any other
operator. Haskell defines the \texttt{\$} operator to enable this style,
as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{infixr} \DecValTok{0} \FunctionTok{$}
\OtherTok{    ($) ::}\NormalTok{ (a }\OtherTok{->}\NormalTok{ b) }\OtherTok{->}\NormalTok{ a }\OtherTok{->}\NormalTok{ b }
\NormalTok{    f }\FunctionTok{$}\NormalTok{ x }\FunctionTok{=}\NormalTok{ f x}
\end{Highlighting}
\end{Shaded}

Thus, for single argument functions \texttt{f}, \texttt{g}, and
\texttt{h},

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    f }\FunctionTok{$}\NormalTok{ g }\FunctionTok{$}\NormalTok{ h }\FunctionTok{$}\NormalTok{ z }\FunctionTok{+} \DecValTok{7}
\end{Highlighting}
\end{Shaded}

is the same as

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    (f (g (h (z}\FunctionTok{+}\DecValTok{7}\NormalTok{))))}
\end{Highlighting}
\end{Shaded}

and as:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    (f }\FunctionTok{.}\NormalTok{ g }\FunctionTok{.}\NormalTok{ h) (z}\FunctionTok{+}\DecValTok{7}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

Similarly, for two-argument functions \texttt{f\textquotesingle{}},
\texttt{g\textquotesingle{}}, and \texttt{h\textquotesingle{}},

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    f' w }\FunctionTok{$}\NormalTok{ g' x }\FunctionTok{$}\NormalTok{ h' y }\FunctionTok{$}\NormalTok{ z }\FunctionTok{+} \DecValTok{7}
\end{Highlighting}
\end{Shaded}

is the same as

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    ((f' w) ((g' x) ((h' y) (z}\FunctionTok{+}\DecValTok{7}\NormalTok{))))}
\end{Highlighting}
\end{Shaded}

and as:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    (f' w }\FunctionTok{.}\NormalTok{ g' x }\FunctionTok{.}\NormalTok{ h' y) (z}\FunctionTok{+}\DecValTok{7}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

For example, this operator allows us to write

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    foldr (}\FunctionTok{+}\NormalTok{) }\DecValTok{0} \FunctionTok{$}\NormalTok{ map (}\DecValTok{2}\FunctionTok{*}\NormalTok{) }\FunctionTok{$}\NormalTok{ filter odd }\FunctionTok{$}\NormalTok{ enumFromTo }\DecValTok{1} \DecValTok{20}
\end{Highlighting}
\end{Shaded}

where Prelude function \texttt{enumFromTo\ m\ n} generates the sequence
of integers from \texttt{m} to \texttt{n}, inclusive.

\subsubsection{\texorpdfstring{Eager evaluation using \texttt{seq} and
\texttt{\$!}}{Eager evaluation using seq and \$!}}\label{eager-evaluation-using-seq-and}

Haskell is a lazily evaluated language. That is, if an argument is
nonstrict it may never be evaluated.

Sometimes, using the technique called \emph{strictness analysis}, the
Haskell compiler can detect that an argument's value will always be
needed. The compiler can then safely force eager evaluation as an
optimization without changing the meaning of the program.

In particular, by selecting the \texttt{-O} option to the Glasgow
Haskell Compiler (GHC), we can enable GHC's code optimization
processing. GHC will generally create smaller, faster object code at the
expense of increased compilation time by taking advantage of strictness
analysis and other optimizations.

However, sometimes we may want to force eager evaluation explicitly
without invoking a full optimization on all the code (e.g., to make a
particular function's evaluation more space efficient). Haskell provides
the primitive function \texttt{seq} that enables this. That is,

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    seq ::}\NormalTok{ a }\OtherTok{->}\NormalTok{ b }\OtherTok{->}\NormalTok{ b}
\NormalTok{    x }\OtherTok{`seq`}\NormalTok{ y }\FunctionTok{=}\NormalTok{ y}
\end{Highlighting}
\end{Shaded}

where it just returns the second argument except that, as a side effect,
\texttt{x} is evaluated before \texttt{y} is returned. (Technically,
\texttt{x} is evaluated to what is called \emph{head normal form}. It is
evaluated until the outer layer of structure such as \texttt{h:t} is
revealed, but \texttt{h} and \texttt{t} themselves are not fully
evaluated. We examine evaluation in more detail in a later chapter.)

Function \texttt{foldl}, the ``optimized'' version of \texttt{foldl} can
be defined using \texttt{seq} as follows

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    foldlP ::}\NormalTok{ (a }\OtherTok{->}\NormalTok{ b }\OtherTok{->}\NormalTok{ a) }\OtherTok{->}\NormalTok{ a }\OtherTok{->}\NormalTok{ [b] }\OtherTok{->}\NormalTok{ a  }\CommentTok{-- foldl' in Data.List }
\NormalTok{    foldlP f z []     }\FunctionTok{=}\NormalTok{ z }
\NormalTok{    foldlP f z (x}\FunctionTok{:}\NormalTok{xs) }\FunctionTok{=}\NormalTok{ y }\OtherTok{`seq`}\NormalTok{ foldl' f y xs }
                        \KeywordTok{where}\NormalTok{ y }\FunctionTok{=}\NormalTok{ f z x}
\end{Highlighting}
\end{Shaded}

That is, this evaluates the \texttt{z} argument of the tail recursive
application eagerly.

Using \texttt{seq}, Haskell also defines \texttt{\$!}, a strict version
of the \texttt{\$} operator, as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{infixr} \DecValTok{0} \FunctionTok{$!} 
\OtherTok{    ($!) ::}\NormalTok{ (a }\OtherTok{->}\NormalTok{ b) }\OtherTok{->}\NormalTok{ a }\OtherTok{->}\NormalTok{ b }
\NormalTok{    f }\FunctionTok{$!}\NormalTok{ x }\FunctionTok{=}\NormalTok{ x }\OtherTok{`seq`}\NormalTok{ f x }
\end{Highlighting}
\end{Shaded}

The effect of \texttt{f\ \$!\ x} is the same as \texttt{f\ \$\ x} except
that \texttt{\$!} eagerly evaluates the argument \texttt{x} before
applying function \texttt{f} to it.

We can rewrite \texttt{foldl\textquotesingle{}} using \texttt{\$!} as
follows:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    foldlQ ::}\NormalTok{ (a }\OtherTok{->}\NormalTok{ b }\OtherTok{->}\NormalTok{ a) }\OtherTok{->}\NormalTok{ a }\OtherTok{->}\NormalTok{ [b] }\OtherTok{->}\NormalTok{ a  }\CommentTok{-- foldl' in Data.List }
\NormalTok{    foldlQ f z []     }\FunctionTok{=}\NormalTok{ z }
\NormalTok{    foldlQ f z (x}\FunctionTok{:}\NormalTok{xs) }\FunctionTok{=}\NormalTok{ (foldlQ f }\FunctionTok{$!}\NormalTok{ f z x) xs}
\end{Highlighting}
\end{Shaded}

We can write a tail recursive function to sum the elements of the list
as follows:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    sum4 ::}\NormalTok{ [}\DataTypeTok{Integer}\NormalTok{] }\OtherTok{->} \DataTypeTok{Integer}  \CommentTok{-- sum in Prelude}
\NormalTok{    sum4 xs }\FunctionTok{=}\NormalTok{ sumIter xs }\DecValTok{0}
        \KeywordTok{where}\NormalTok{ sumIter []     acc }\FunctionTok{=}\NormalTok{ acc}
\NormalTok{              sumIter (x}\FunctionTok{:}\NormalTok{xs) acc }\FunctionTok{=}\NormalTok{ sumIter xs (acc}\FunctionTok{+}\NormalTok{x)}
\end{Highlighting}
\end{Shaded}

We can then redefine \texttt{sum4} to force eager evaluation of the
accumulating parameter of \texttt{sumIter} as follows:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    sum5 ::}\NormalTok{ [}\DataTypeTok{Integer}\NormalTok{] }\OtherTok{->} \DataTypeTok{Integer} \CommentTok{-- sum in Prelude}
\NormalTok{    sum5 xs }\FunctionTok{=}\NormalTok{ sumIter xs }\DecValTok{0}
        \KeywordTok{where}\NormalTok{ sumIter []     acc }\FunctionTok{=}\NormalTok{ acc}
\NormalTok{              sumIter (x}\FunctionTok{:}\NormalTok{xs) acc }\FunctionTok{=}\NormalTok{ sumIter xs }\FunctionTok{$!}\NormalTok{ acc }\FunctionTok{+}\NormalTok{ x}
\end{Highlighting}
\end{Shaded}

However, we need to be careful in applying \texttt{seq} and
\texttt{\$!}. They change the semantics of the lazily evaluated language
in the case where the argument is nonstrict. They may force a program to
terminate abnormally and/or cause it to take unnecessary evaluation
steps.

\subsection{Additional Higher-Order List
Functions}\label{additional-higher-order-list-functions}

\subsubsection{List-breaking operations}\label{list-breaking-operations}

In a previous chapter we looked at the list-breaking functions
\texttt{take} and \texttt{drop}. The Prelude also includes several
higher-order list-breaking functions that take two arguments, a
predicate that determines where the list is to be broken and the list to
be broken.

Here we look at Prelude functions \texttt{takeWhile} and
\texttt{dropWhile}. As you would expect, function \texttt{takeWhile}
``takes'' elements from the beginning of the list ``while'' the elements
satisfy the predicate and \texttt{dropWhile} ``drops'' elements from the
beginning of the list ``while'' the elements satisfy the predicate. The
Prelude definitions are similar to the following:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    takeWhile'::}\NormalTok{ (a }\OtherTok{->} \DataTypeTok{Bool}\NormalTok{) }\OtherTok{->}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ [a] }\CommentTok{-- takeWhile in Prelude}
\NormalTok{    takeWhile'  p []  }\FunctionTok{=}\NormalTok{ [] }
\NormalTok{    takeWhile'  p (x}\FunctionTok{:}\NormalTok{xs) }
        \FunctionTok{|}\NormalTok{ p x        }\FunctionTok{=}\NormalTok{ x }\FunctionTok{:}\NormalTok{ takeWhile' p xs }
        \FunctionTok{|}\NormalTok{ otherwise  }\FunctionTok{=}\NormalTok{ [] }

\OtherTok{    dropWhile' ::}\NormalTok{ (a }\OtherTok{->} \DataTypeTok{Bool}\NormalTok{) }\OtherTok{->}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ [a] }\CommentTok{-- dropWhile in Prelude}
\NormalTok{    dropWhile'  p []  }\FunctionTok{=}\NormalTok{ [] }
\NormalTok{    dropWhile'  p xs}\FunctionTok{@}\NormalTok{(x}\FunctionTok{:}\NormalTok{xs') }
        \FunctionTok{|}\NormalTok{ p x        }\FunctionTok{=}\NormalTok{ dropWhile' p xs' }
        \FunctionTok{|}\NormalTok{ otherwise  }\FunctionTok{=}\NormalTok{ xs}
\end{Highlighting}
\end{Shaded}

Note the use of the pattern \texttt{xs@(x:xs’)} in
\texttt{dropWhile\textquotesingle{}}. This pattern matches a non-nil
list with \texttt{x} and \texttt{xs’} binding to the head and tail,
respectively, as usual. Variable \texttt{xs} binds to the entire list.

As an example, suppose we want to remove the leading blanks from a
string. We can do that with the expression:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    dropWhile ((}\FunctionTok{==}\NormalTok{) }\CharTok{' '}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

As with \texttt{take} and \texttt{drop}, the above functions can also be
related by a ``law''. For all finite lists \texttt{xs} and predicates
\texttt{p} on the same type:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    takeWhile p xs }\FunctionTok{++}\NormalTok{ dropWhile p xs }\FunctionTok{=}\NormalTok{ xs}
\end{Highlighting}
\end{Shaded}

Prelude function \texttt{span} combines the functionality of
\texttt{takeWhile} and \texttt{dropWhile} into one function. It takes a
predicate \texttt{p} and a list \texttt{xs} and returns a tuple where
the first element is the longest prefix (possibly empty) of \texttt{xs}
that satisfies \texttt{p} and the second element is the remainder of the
list.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    span' ::}\NormalTok{ (a }\OtherTok{->} \DataTypeTok{Bool}\NormalTok{) }\OtherTok{->}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ ([a],[a]) }\CommentTok{-- span in Prelude}
\NormalTok{    span' _ xs}\FunctionTok{@}\NormalTok{[]      }\FunctionTok{=}\NormalTok{  (xs, xs)}
\NormalTok{    span' p xs}\FunctionTok{@}\NormalTok{(x}\FunctionTok{:}\NormalTok{xs')}
        \FunctionTok{|}\NormalTok{ p x          }\FunctionTok{=}  \KeywordTok{let}\NormalTok{ (ys,zs) }\FunctionTok{=}\NormalTok{ span' p xs' }\KeywordTok{in}\NormalTok{ (x}\FunctionTok{:}\NormalTok{ys,zs)}
        \FunctionTok{|}\NormalTok{ otherwise    }\FunctionTok{=}\NormalTok{  ([],xs)}
\end{Highlighting}
\end{Shaded}

Thus the following ``law'' holds for all finite lists \texttt{xs} and
predicates \texttt{p} on same type:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    span p xs }\FunctionTok{==}\NormalTok{ (takeWhile p xs, dropWhile p xs)}
\end{Highlighting}
\end{Shaded}

The Prelude also includes the function \texttt{break}, defined as
follows:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    break' ::}\NormalTok{ (a }\OtherTok{->} \DataTypeTok{Bool}\NormalTok{) }\OtherTok{->}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ ([a],[a]) }\CommentTok{-- break in Prelude}
\NormalTok{    break' p }\FunctionTok{=}\NormalTok{  span (not }\FunctionTok{.}\NormalTok{ p)}
\end{Highlighting}
\end{Shaded}

\subsubsection{List-combining
operations}\label{list-combining-operations}

In a previous chapter, we also looked at the function \texttt{zip},
which takes two lists and returns a list of pairs of the corresponding
elements. Function \texttt{zip} applies an operation, in this case
\emph{tuple-construction}, to the corresponding elements of two lists.

We can generalize this pattern of computation with the function
\texttt{zipWith} in which the operation is an argument to the function.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    zipWith' ::}\NormalTok{ (a}\OtherTok{->}\NormalTok{b}\OtherTok{->}\NormalTok{c) }\OtherTok{->}\NormalTok{ [a]}\OtherTok{->}\NormalTok{[b]}\OtherTok{->}\NormalTok{[c] }\CommentTok{-- zipWith in Prelude}
\NormalTok{    zipWith' z  (x}\FunctionTok{:}\NormalTok{xs)  (y}\FunctionTok{:}\NormalTok{ys) }\FunctionTok{=}\NormalTok{ z x y }\FunctionTok{:}\NormalTok{ zipWith' z xs ys }
\NormalTok{    zipWith' _  _     _        }\FunctionTok{=}\NormalTok{ []}
\end{Highlighting}
\end{Shaded}

Using a lambda expression to state the tuple-forming operation, the
Prelude defines \texttt{zip} in terms of \texttt{zipWith}:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    zip'' ::}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ [b] }\OtherTok{->}\NormalTok{ [(a,b)]  }\CommentTok{-- zip}
\NormalTok{    zip'' }\FunctionTok{=}\NormalTok{ zipWith' (\textbackslash{}x y }\OtherTok{->}\NormalTok{ (x,y)) }
\end{Highlighting}
\end{Shaded}

Or can be written more simply as:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    zip''' ::}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ [b] }\OtherTok{->}\NormalTok{ [(a,b)]  }\CommentTok{-- zip}
\NormalTok{    zip''' }\FunctionTok{=}\NormalTok{ zipWith' (,) }
\end{Highlighting}
\end{Shaded}

The \texttt{zipWith} function also enables us to define operations such
as the scalar product of two vectors in a concise way.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    sp ::} \DataTypeTok{Num}\NormalTok{ a }\OtherTok{=>}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ a }
\NormalTok{    sp xs ys }\FunctionTok{=}\NormalTok{ sum' (zipWith' (}\FunctionTok{*}\NormalTok{) xs ys) }
\end{Highlighting}
\end{Shaded}

The Prelude includes versions of \texttt{zipWith} that take up to seven
input lists: \texttt{zipWith3} \(\cdots\) \texttt{zipWith7}.

\subsection{Rational Arithmetic
Revisited}\label{rational-arithmetic-revisited}

Remember the rational number arithmetic package developed in an earlier
chapter. In that package's \texttt{Rational} module, we defined a
function \texttt{eqRat} to compare two rational numbers for equality
using the appropriate set of integer comparisons.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    eqRat ::} \DataTypeTok{Rat} \OtherTok{->} \DataTypeTok{Rat} \OtherTok{->} \DataTypeTok{Bool} 
\NormalTok{    eqRat x y }\FunctionTok{=}\NormalTok{ (numer x) }\FunctionTok{*}\NormalTok{ (denom y) }\FunctionTok{==}\NormalTok{ (numer y) }\FunctionTok{*}\NormalTok{ (denom x)}
\end{Highlighting}
\end{Shaded}

We could have implemented the other comparison operations similarly.

Because the comparison operations are similar, they are good candidates
for us to use a higher-order function. We can abstract out the common
pattern of comparisons into a function that takes the corresponding
integer comparison as an argument.

To compare two rational numbers, we can express their values in terms of
a common denominator (e.g., \texttt{denom\ x\ *\ denom\ y}) and then
compare the numerators using the integer comparisons. We can thus
abstract the comparison into a higher-order function \texttt{compareRat}
that takes an appropriate integer relational operator and the two
rational numbers.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    compareRat ::}\NormalTok{ (}\DataTypeTok{Int} \OtherTok{->} \DataTypeTok{Int} \OtherTok{->} \DataTypeTok{Bool}\NormalTok{) }\OtherTok{->} \DataTypeTok{Rat} \OtherTok{->} \DataTypeTok{Rat} \OtherTok{->} \DataTypeTok{Bool} 
\NormalTok{    compareRat r x y }\FunctionTok{=}\NormalTok{ r (numer x }\FunctionTok{*}\NormalTok{ denom y) (denom x }\FunctionTok{*}\NormalTok{ numer y) }
\end{Highlighting}
\end{Shaded}

Then we can define the rational number comparisons in terms of
\texttt{compareRat}. (Note that we redefine function \texttt{eqRat} from
the package in the earlier chapter.)

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    eqRat,neqRat,ltRat,leqRat,gtRat,}\OtherTok{geqRat ::} \DataTypeTok{Rat} \OtherTok{->} \DataTypeTok{Rat} \OtherTok{->} \DataTypeTok{Bool} 
\NormalTok{    eqRat   }\FunctionTok{=}\NormalTok{ compareRat (}\FunctionTok{==}\NormalTok{) }
\NormalTok{    neqRat  }\FunctionTok{=}\NormalTok{ compareRat (}\FunctionTok{/=}\NormalTok{) }
\NormalTok{    ltRat   }\FunctionTok{=}\NormalTok{ compareRat (}\FunctionTok{<}\NormalTok{)}
\NormalTok{    leqRat  }\FunctionTok{=}\NormalTok{ compareRat (}\FunctionTok{<=}\NormalTok{) }
\NormalTok{    gtRat   }\FunctionTok{=}\NormalTok{ compareRat (}\FunctionTok{>}\NormalTok{)}
\NormalTok{    geqRat  }\FunctionTok{=}\NormalTok{ compareRat (}\FunctionTok{>=}\NormalTok{) }
\end{Highlighting}
\end{Shaded}

\subsection{Merge Sort}\label{merge-sort}

We defined the insertion sort in a previous chapter. It has an
average-case time complexity of O(\(n^{2}\)) where \(n\) is the length
of the input list.

We now consider a more efficient function to sort the elements of a list
into ascending order: \emph{merge sort}. Merge sort works as follows:

\begin{itemize}
\item
  If the list has fewer than two elements, then it is already sorted.
\item
  If the list has two or more elements, then we split it into two
  sublists, each with about half the elements, and sort each
  recursively.
\item
  We merge the two ascending sublists into an ascending list.
\end{itemize}

We define function \texttt{msort} to be a polymorphic, higher-order
function that has two parameters. The first (\texttt{less}) is the
comparison operator and the second (\texttt{xs}) is the list to be
sorted. Function \texttt{less} must be defined for every element that
appears in the list to be sorted.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    msort ::} \DataTypeTok{Ord}\NormalTok{ a }\OtherTok{=>}\NormalTok{ (a }\OtherTok{->}\NormalTok{ a }\OtherTok{->} \DataTypeTok{Bool}\NormalTok{) }\OtherTok{->}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ [a]}
\NormalTok{    msort _    [] }\FunctionTok{=}\NormalTok{ []}
\NormalTok{    msort less xs }\FunctionTok{=}\NormalTok{ merge (msort less ls) (msort less rs)}
        \KeywordTok{where}\NormalTok{  n       }\FunctionTok{=}\NormalTok{ (length xs) }\OtherTok{`div`} \DecValTok{2} 
\NormalTok{               (ls,rs) }\FunctionTok{=}\NormalTok{ splitAt n xs}
\NormalTok{               merge [] ys     }\FunctionTok{=}\NormalTok{ ys}
\NormalTok{               merge xs []     }\FunctionTok{=}\NormalTok{ x}
\NormalTok{               merge ls}\FunctionTok{@}\NormalTok{(x}\FunctionTok{:}\NormalTok{xs) rs}\FunctionTok{@}\NormalTok{(y}\FunctionTok{:}\NormalTok{ys) }
                   \FunctionTok{|}\NormalTok{ less x y  }\FunctionTok{=}\NormalTok{ x }\FunctionTok{:}\NormalTok{ merge xs rs}
                   \FunctionTok{|}\NormalTok{ otherwise }\FunctionTok{=}\NormalTok{ y }\FunctionTok{:}\NormalTok{ merge ls ys}
\end{Highlighting}
\end{Shaded}

By nesting the definition of \texttt{merge}, we enabled it to directly
access the the parameters of \texttt{msort}. In particular, we did not
need to pass the comparison function to \texttt{merge}.

Assuming that \texttt{less} evaluates in constant time, the time
complexity of \texttt{msort} is O(\(n \log(n)\)), where \(n\) is the
length of the input list.

\begin{itemize}
\item
  Each call level requires splitting of the list in half and merging of
  the two sorted lists. This takes time proportional to the length of
  the list argument.
\item
  Each call of \texttt{msort} for lists longer than one results in two
  recursive calls of \texttt{msort}.
\item
  But each successive call of \texttt{msort} halves the number of
  elements in its input, so there are O(\(\log(n)\)) recursive calls.
\end{itemize}

So the total cost is O(\(n \log(n)\)). The cost is independent of
distribution of elements in the original list.

We can apply \texttt{msort} as follows:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    msort (}\FunctionTok{<}\NormalTok{) [}\DecValTok{5}\NormalTok{, }\DecValTok{7}\NormalTok{, }\DecValTok{1}\NormalTok{, }\DecValTok{3}\NormalTok{]}
\end{Highlighting}
\end{Shaded}

Function \texttt{msort} is defined in curried form with the comparison
function first. This enables us to conveniently specialize
\texttt{msort} with a specific comparison function. For example,

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    descendSort ::} \DataTypeTok{Ord}\NormalTok{ a }\OtherTok{=>}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ [a]}
\NormalTok{    descendSort }\FunctionTok{=}\NormalTok{ msort (\textbackslash{} x y }\OtherTok{->}\NormalTok{ x }\FunctionTok{>}\NormalTok{ y)}
\end{Highlighting}
\end{Shaded}

\subsection{Exercises}\label{exercises}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Suppose you need a Haskell function \texttt{times} that takes a list
  of integers (type \texttt{Integer}) and returns the product of the
  elements (e.g, \texttt{times\ {[}2,3,4{]}} returns \texttt{24}).
  Define the following Haskell functions.

  \begin{enumerate}
  \def\labelenumii{\alph{enumii}.}
  \item
    Function \texttt{times1} that uses the Prelude function
    \texttt{foldr}(or \texttt{foldr\textquotesingle{}} from this
    chapter).
  \item
    Function \texttt{times2} that uses backward recursion to compute the
    product. (Use recursion directly. Do not use the list-folding
    Prelude functions such as \texttt{foldr} or \texttt{product}.)
  \item
    Function \texttt{times3} that uses forward recursion to compute the
    product. (Hint: use a tail-recursive auxiliary function with an
    accumulating parameter.)
  \item
    Function \texttt{times4} that uses function
    \texttt{foldl\textquotesingle{}} from the Haskell library
    \texttt{Data.List}.
  \end{enumerate}
\item
  For each of the following specifications, define a Haskell function
  that has the given arguments and result. Use the higher order library
  functions (from this chapter) such as \texttt{map}, \texttt{filter},
  \texttt{foldr}, and \texttt{foldl} as appropriate.

  \begin{enumerate}
  \def\labelenumii{\alph{enumii}.}
  \item
    Function \texttt{numof} takes a value and a list and returns the
    number of occurrences of the value in the list.
  \item
    Function \texttt{ellen} takes a list of character strings and
    returns a list of the lengths of the corresponding strings.
  \item
    Function \texttt{ssp} takes a list of integers and returns the sum
    of the squares of the positive elements of the list.
  \end{enumerate}
\item
  Suppose you need a Haskell function \texttt{sumSqNeg} that takes a
  list of integers (type \texttt{Integer}) and returns the sum of the
  squares of the negative values in the list.

  Define the following Haskell functions. Use the higher order library
  functions (from this chapter) such as \texttt{map}, \texttt{filter},
  \texttt{foldr}, and \texttt{foldl} as appropriate.

  \begin{enumerate}
  \def\labelenumii{\alph{enumii}.}
  \item
    Function \texttt{sumSqNeg1} that is backward recursive. (Use
    recursion directly. Do not use the list-folding Prelude functions
    such as \texttt{foldr} or \texttt{sum}.)
  \item
    Function \texttt{sumSqNeg2} that is tail recursive. (Use recursion
    directly. Do not use the list-folding Prelude functions such as
    \texttt{foldr} or \texttt{sum}.)
  \item
    Function \texttt{sumSqNeg3} that uses standard prelude functions
    such as \texttt{map}, \texttt{filter}, \texttt{foldr}, and
    \texttt{foldl}.
  \item
    Function \texttt{sumSqNeg4} that uses list comprehensions (Chapter
    7).
  \end{enumerate}
\item
  Define a Haskell function

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    total ::}\NormalTok{ (}\DataTypeTok{Integer} \OtherTok{->} \DataTypeTok{Integer}\NormalTok{) }\OtherTok{->} \DataTypeTok{Integer} \OtherTok{->} \DataTypeTok{Integer}
\end{Highlighting}
\end{Shaded}

  so that \texttt{total\ f\ n} gives
  \texttt{f\ 0\ +\ f\ 1\ +\ f\ 2\ +\ ...\ +\ f\ n}.
\item
  Define a Haskell function

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    removeFirst ::}\NormalTok{ (a }\OtherTok{->} \DataTypeTok{Bool}\NormalTok{) }\OtherTok{->}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ [a\} }
\end{Highlighting}
\end{Shaded}

  so that \texttt{removeFirst\ p\ xs} removes the first element of
  \texttt{xs} that does has the property \texttt{p}.
\item
  Define a Haskell function

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    removeLast ::}\NormalTok{ (a }\OtherTok{->} \DataTypeTok{Bool}\NormalTok{) }\OtherTok{->}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ [a]}
\end{Highlighting}
\end{Shaded}

  so that \texttt{removeLast\ p\ xs} removes the last occurrence of
  element of \texttt{xs} that has the property \texttt{p}.

  How could you define it using \texttt{removeFirst}?
\item
  Define a Haskell function \texttt{map2} that takes a list of functions
  and a list of values and returns the list of results of applying each
  function in the first list to the corresponding value in the second
  list.
\item
  Define a Haskell function \texttt{fmap} that takes a value and a list
  of functions and returns the list of results from applying each
  function to the argument value. (For example,
  \texttt{fmap\ 3\ {[}((*)\ 2),\ ((+)\ 2){]}} yields
  \texttt{{[}6,5{]}}.)
\item
  Define a Haskell function \texttt{composeList} that takes a list of
  functions and composes them into a single function. (Be sure to give
  the type signature.)
\item
  A list \texttt{s} is a \emph{prefix} of a list \texttt{t} if there is
  some list \texttt{u} (perhaps nil) such that \texttt{s\ ++\ u\ ==\ t}.
  For example, the prefixes of string \texttt{abc} are
  `\texttt{,}a\texttt{,}ab\texttt{,}abc`.

  A list \texttt{s} is a \emph{suffix} of a list \texttt{t} if there is
  some list \texttt{u} (perhaps nil) such that \texttt{u\ ++\ s\ ==\ t}.
  For example, the suffixes of \texttt{abc} are \texttt{abc},
  \texttt{bc}, \texttt{c}, and ``.

  A list \texttt{s} is a \emph{segment} of a list \texttt{t} if there
  are some (perhaps nil) lists \texttt{u} and \texttt{v} such that . For
  example, the segments of string \texttt{abc} consist of the prefixes
  and the suffixes plus \texttt{b}.

  Define the following Haskell functions. You may use functions
  appearing early in the list to implement later ones.

  \begin{enumerate}
  \def\labelenumii{\alph{enumii}.}
  \item
    Define a function \texttt{prefix} such that \texttt{prefix\ xs\ ys}
    returns \texttt{True} if \texttt{xs} is a prefix of \texttt{ys} and
    returns \texttt{False} otherwise.
  \item
    Define a function \texttt{suffixes} such that \texttt{suffixes\ xs}
    returns the list of all suffixes of list \texttt{xs}. (Hint:
    Generate them in the order given in the example of \texttt{abc}
    above.)
  \item
    Define a function \texttt{indexes} such that
    \texttt{indexes\ xs\ ys} returns a list of all the positions at
    which list \texttt{xs} appears in list \texttt{ys}. Consider the
    first character of \texttt{ys} as being at position 0. For example,
    \texttt{indexes\ ab\ abaabbab} returns \texttt{{[}1,4,7{]}}. (Hint:
    Remember functions like \texttt{map}, \texttt{filter}, \texttt{zip},
    and the functions you just defined?)
  \item
    Define a function \texttt{sublist} such that
    \texttt{sublist\ xs\ ys} returns \texttt{True} if list \texttt{xs}
    appears as a segment of list \texttt{ys} and returns \texttt{False}
    otherwise.
  \end{enumerate}
\item
  Assume that the following Haskell type synonyms have been defined:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{type} \DataTypeTok{Word} \FunctionTok{=} \DataTypeTok{String} \CommentTok{-- word, characters left-to-right}
    \KeywordTok{type} \DataTypeTok{Line} \FunctionTok{=}\NormalTok{ [}\DataTypeTok{Word}\NormalTok{] }\CommentTok{-- line, words left-to-right}
    \KeywordTok{type} \DataTypeTok{Page} \FunctionTok{=}\NormalTok{ [}\DataTypeTok{Line}\NormalTok{] }\CommentTok{-- page, lines top-to-bottom}
    \KeywordTok{type} \DataTypeTok{Doc}  \FunctionTok{=}\NormalTok{ [}\DataTypeTok{Page}\NormalTok{] }\CommentTok{-- document, pages front-to-back}
\end{Highlighting}
\end{Shaded}

  Further assume that values of type \texttt{Word} do not contain any
  space characters. Implement the following Haskell text-handling
  functions:

  \begin{enumerate}
  \def\labelenumii{\alph{enumii}.}
  \item
    \texttt{npages} that takes a \texttt{Doc} and returns the number of
    \texttt{Page}s in the document.
  \item
    \texttt{nlines} that takes a \texttt{Doc} and returns the number of
    \texttt{Line}s in the document.
  \item
    \texttt{nwords} that takes a \texttt{Doc} and returns the number of
    \texttt{Word}s in the document.
  \item
    \texttt{nchars} that takes a \texttt{Doc} and returns the number of
    \texttt{Char}s in the document (not including spaces of course).
  \item
    \texttt{deblank} that takes a \texttt{Doc} and returns the
    \texttt{Doc} with all blank lines removed. A blank line is a line
    that contains no words.
  \item
    \texttt{linetext} that takes a \texttt{Line} and returns the line as
    a \texttt{String} with the words appended together in left-to-right
    order separated by space characters and with a newline character
    '\texttt{\textbackslash{}n}' appended to the right end of the line.
    (For example, \texttt{linetext\ {[}Robert,\ Khayat{]}} yields
    \texttt{"Robert\ Khayat\textbackslash{}n"}.)
  \item
    \texttt{pagetext} that takes a \texttt{Page} and returns the page as
    a \texttt{String}--applies \texttt{linetext} to its component lines
    and appends the result in a top-to-bottom order.
  \item
    \texttt{doctext} that takes a \texttt{Doc} and returns the document
    as a \texttt{String}--applies \texttt{pagetext} to its component
    lines and appends the result in a top-to-bottom order.
  \item
    \texttt{wordeq} that takes a two \texttt{Doc}s and returns
    \texttt{True} if the two documents are \emph{word equivalent} and
    \texttt{False} otherwise. Two documents are word equivalent if they
    contain exactly the same words in exactly the same order regardless
    of page and line structure. For example,
    \texttt{{[}{[}{[}"Robert"{]},{[}"Khayat"{]}{]}{]}} is word
    equivalent to \texttt{{[}{[}{[}"Robert","Khayat"{]}{]}{]}}.
  \end{enumerate}
\end{enumerate}

\subsection{References}\label{references}

\begin{description}
\tightlist
\item[{[}Abelson-Sussman 1996{]}]
Harold Abelson and Gerald Jay Sussman. \emph{Structure and
Interpretation of Computer Programs}
(\href{http://mitpress.mit.edu/sicp/}{SICP}), Second Edition, MIT Press,
1996.
\item[{[}Bird 2015{]}]
Richard Bird. \emph{Thinking Functionally with Haskell} Cambridge
University Press, 2015.
\item[{[}Bird-Wadler 1998{]}]
Richard Bird and Philip Wadler. \emph{Introduction to Functional
Programming}, Second Edition, Addison Wesley, 1998.
{[}\href{https://usi-pl.github.io/lc/sp-2015/doc/Bird_Wadler.\%20Introduction\%20to\%20Functional\%20Programming.1ed.pdf}{First
Edition, 1988}{]}
\item[{[}Chiusano-Bjarnason 2015{]}]
Paul Chiusano and Runar Bjarnason, \emph{Functional Programming in
Scala}, Manning, 2015.
\item[{[}Cunningham 2014{]}]
H. Conrad Cunningham.
\href{https://john.cs.olemiss.edu/~hcc/csci450/notes/haskell_notes.pdf}{\emph{Notes
on Functional Programming with Haskell}}, 1994-2014.
\item[{[}Thompson 2011{]}]
Simon Thompon. \emph{Haskell: The Craft of Programming, Third Edition},
Pearson, 2011.
\item[{[}Wikipedia 2017{]}]
\emph{Wikipedia} articles on ``Polymorphism'', ``Ad Hoc Polymorphism'',
``Parametric Polymorphism'', ``Subtyping'', and ``Function
Overloading'', 2017.
\end{description}

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

Procedural abstraction, functions (first-class, higher-order),
modularity, interface, function generalization and specialization,
scope-commonality-variability (SCV) analysis, hot and frozen spots,
think like a functional programmer, common functional programming
patterns (map, filter, fold, concatMap), duality theorem, strict and
nonstrict functions, bottom, strictness analysis, currying, partial
application, operator sections, combinators, functional composition,
property of extensionality, pointful and point-free styles, plumbing,
function pipeline, lambda expression, application operator \texttt{\$},
eager evaluation operators \texttt{seq} and \texttt{\$!}, head-normal
form, merge sort

\end{document}
