\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 More List Processing and Problem Solving},
            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}
\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\\
More List Processing and Problem Solving}
\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
module from chapters 7 and 10 of my \emph{Notes on Functional
Programming with Haskell}.

In Spring 2017, I continued to develop this module. This included adding
discussion of the tupling technique from chapter 12 of my \emph{Notes on
Functional Programming with Haskell} and referring to examples used in
other chapers.

I continue to develop this module in Summer and Fall 2017.

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
  Add chapter goals and outcomes
\item
  Make problem solving section less dependent on external references
  such as the classic Bird and Wadler textbook. (Probably need to add
  new examples to this and other chapters)
\item
  Add exercises
\end{itemize}

\setcounter{section}{6}

\section{More List Processing and Problem
Solving}\label{more-list-processing-and-problem-solving}

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

TODO

\subsection{Sequences}\label{sequences}

Haskell provides a compact notation for expressing arithmetic sequences.

An arithmetic sequence (or progression) is a sequence of elements from
an enumerated type (i.e., a member of class \texttt{Enum}) such that
consecutive elements have a fixed difference. \texttt{Int},
\texttt{Integer}, \texttt{Float}, \texttt{Double}, and \texttt{Char} are
all predefined members of this class.

\begin{itemize}
\item
  \texttt{{[}m..n{]}} produces the list of elements from \texttt{m} up
  to \texttt{n} in steps of one if \texttt{m\ \textless{}=\ n}. It
  produces the nil list otherwise.

  Examples:

  \begin{itemize}
  \tightlist
  \item
    \texttt{{[}1..5{]}} \(\Longrightarrow\) \texttt{{[}1,2,3,4,5{]}}
  \item
    \texttt{{[}5..1{]}} \(\Longrightarrow\) \texttt{{[}{]}}
  \end{itemize}

  This feature is implemented with Prelude function \texttt{enumFromTo}
  applied as \texttt{enumFromTo\ m\ n}.
\item
  \texttt{{[}m,m’..n{]}} produces the list of elements from \texttt{m}
  in steps of \texttt{m’-m}. If \texttt{m’\ \textgreater{}\ m} then the
  list is increasing up to \texttt{n}. If \texttt{m’\ \textless{}\ m},
  then it is decreasing.

  Examples:

  \begin{itemize}
  \tightlist
  \item
    \texttt{{[}1,3..9{]}} \(\Longrightarrow\) \texttt{{[}1,3,5,7,9{]}}
  \item
    \texttt{{[}9,8..5{]}} \(\Longrightarrow\) \texttt{{[}9,8,7,6,5{]}}
  \item
    \texttt{{[}9,8..11{]}} \(\Longrightarrow\) \texttt{{[}{]}}
  \end{itemize}

  This feature is implemented with Prelude function
  \texttt{enumFromThenTo} applied as \texttt{enumFromThenTo\ m’\ m\ n}.
\item
  \texttt{{[}m..{]}} and \texttt{{[}m,m’..{]}} produce potentially
  infinite lists beginning with \texttt{m} and having steps 1 and
  \texttt{m’-m} respectively.

  These features are implemented with Prelude functions
  \texttt{enumFrom} applied as \texttt{enumFrom\ m} and
  \texttt{enumFromThen} applied as \texttt{enumFromThen\ m\ m’}.
\end{itemize}

Of course, we can provide our own functions for sequences. Consider the
following function to generate a geometric sequence.

A geometric sequence (or progression) is a sequence of elements from an
ordered, numeric type (i.e., a member of both classes \texttt{Ord} and
\texttt{Num}) such that consecutive elements have a fixed ratio.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    geometric ::}\NormalTok{ (}\DataTypeTok{Ord}\NormalTok{ a, }\DataTypeTok{Num}\NormalTok{ a) }\OtherTok{=>}\NormalTok{ a }\OtherTok{->}\NormalTok{ a }\OtherTok{->}\NormalTok{ a }\OtherTok{->}\NormalTok{ [a]}
\NormalTok{    geometric r m n }\FunctionTok{|}\NormalTok{ m }\FunctionTok{>}\NormalTok{ n     }\FunctionTok{=}\NormalTok{ []}
                    \FunctionTok{|}\NormalTok{ otherwise }\FunctionTok{=}\NormalTok{ m }\FunctionTok{:}\NormalTok{ geometric r (m}\FunctionTok{*}\NormalTok{r) n}
\end{Highlighting}
\end{Shaded}

Example: \texttt{geometric\ 2\ 1\ 10} \(\Longrightarrow\)
\texttt{{[}1,2,4,8{]}}

\subsection{List Comprehensions}\label{list-comprehensions}

\subsubsection{Syntax and semantics}\label{syntax-and-semantics}

The \emph{list comprehension} is another powerful and compact notation
for describing lists. A list comprehension has the form

\begin{quote}
\texttt{\{} \emph{expression} \texttt{\textbar{}} \emph{qualifiers}
\texttt{\}}
\end{quote}

where \emph{expression} is any Haskell expression.

The \emph{expression} and the \emph{qualifiers} in a comprehension may
contain variables that are local to the comprehension. The values of
these variables are bound by the \emph{qualifiers}.

For each group of values bound by the qualifiers, the comprehension
generates an element of the list whose value is the \emph{expression}
with the values substituted for the local variables.

There are three kinds of \emph{qualifiers}that can be used in Haskell:
generators, filters, and local definitions.

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  A \emph{generator} is a qualifier of the form

  \begin{quote}
  \emph{pat} \texttt{\textless{}-} \emph{exp}
  \end{quote}

  where \emph{exp} is a list-valued expression. The generator extracts
  each element of \emph{exp} that matches the pattern \emph{pat} in the
  order that the elements appear in the list; elements that do not match
  the pattern are skipped.

  Example: \texttt{{[}\ n*n\ \textbar{}\ n\ \textless{}-\ {[}1..5{]}{]}}
  \(\Longrightarrow\) \texttt{{[}1,4,9,16,25{]}}
\item
  A \emph{filter} is a Boolean-valued expression used as a
  \emph{qualifier} in a list comprehension. These expressions work like
  the \texttt{filter} function; only values that make the expression
  \texttt{True} are used to form elements of the list comprehension.

  Example:

  \begin{itemize}
  \tightlist
  \item
    \texttt{{[}\ n*n\ \textbar{}\ even\ n\ {]}} \(\Longrightarrow\)
    \texttt{(if\ even\ n\ then\ {[}n*n{]}\ else\ {[}{]})}
  \end{itemize}

  Above variable \texttt{n} is global to this expression, not local to
  the comprehension.
\item
  A \emph{local definition} is a qualifier of the form

  \begin{quote}
  \texttt{let} \emph{pat} \texttt{=} \emph{expr}
  \end{quote}

  introduces a local definition into the list comprehension.

  Example:

  \begin{itemize}
  \tightlist
  \item
    \texttt{{[}\ n*n\ \textbar{}\ let\ n\ =\ 2\ {]}} \(\Longrightarrow\)
    \texttt{{[}4{]}}
  \end{itemize}
\end{enumerate}

The real power of list comprehensions come from using several qualifiers
separated by commas on the right side of the vertical bar
\texttt{\textbar{}}.

\begin{itemize}
\item
  Generators appearing later in the list of qualifiers vary more quickly
  than those that appear earlier. Speaking operationally, the generation
  ``loop'' for the later generator is nested within the ``loop'' for the
  earlier.

  Example:

  \begin{itemize}
  \tightlist
  \item
    \texttt{{[}\ (m,n)\ \textbar{}\ m\textless{}-{[}1..3{]},\ n\textless{}-{[}4,5{]}\ {]}}
    \(\Longrightarrow\)
    \texttt{{[}(1,4),(1,5),(2,4),(2,5),(3,4),(3,5){]}}
  \end{itemize}
\item
  Qualifiers appearing later in the list of qualifiers may use values
  generated by qualifiers appearing earlier, but not vice versa.

  Examples:

  \begin{itemize}
  \item
    \texttt{{[}\ n*n\ \textbar{}\ n\textless{}-{[}1..10{]},\ even\ n\ {]}}
    \(\Longrightarrow\) \texttt{{[}4,16,36,64,100{]}}
  \item
    \texttt{{[}\ (m,n)\ \textbar{}\ m\textless{}-{[}1..3{]},\ n\textless{}-{[}1..m{]}\ {]}}
    \(\Longrightarrow\)
    \texttt{{[}\ (1,1),\ (2,1),\ (2,2),\ (3,1),\ (3,2),\ (3,3){]}}
  \end{itemize}
\item
  The generated values may or may not be used in the \emph{expression}.

  Examples:

  \begin{itemize}
  \item
    \texttt{{[}\ 27\ \textbar{}\ n\textless{}-{[}1..3{]}{]}}
    \(\Longrightarrow\) \texttt{{[}27,27,27{]}}
  \item
    \texttt{{[}\ x\ \textbar{}\ x\textless{}-{[}1..3{]},\ y\textless{}-{[}1..2{]}{]}}
    \(\Longrightarrow\) \texttt{{[}1,1,2,2,3,3{]}}
  \end{itemize}
\end{itemize}

\subsubsection{Translating list
comprehensions}\label{translating-list-comprehensions}

List comprehensions are syntactic sugar. We can translate them into core
Haskell features by applying the following identities.

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  For any expression \texttt{e},

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    [ e }\FunctionTok{|} \DataTypeTok{True}\NormalTok{ ]}
\end{Highlighting}
\end{Shaded}

  is equivalent to:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    [ e ]}
\end{Highlighting}
\end{Shaded}
\item
  For any expression \texttt{e} and qualifier \texttt{q},

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    [ e }\FunctionTok{|}\NormalTok{ q ]}
\end{Highlighting}
\end{Shaded}

  is equivalent to:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    [ e }\FunctionTok{|}\NormalTok{ q, }\DataTypeTok{True}\NormalTok{ ]}
\end{Highlighting}
\end{Shaded}
\item
  For any expression \texttt{e}, boolean \texttt{b}, and and sequence of
  qualifiers \texttt{Q},

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    [ e }\FunctionTok{|}\NormalTok{ b, }\DataTypeTok{Q}\NormalTok{ ]}
\end{Highlighting}
\end{Shaded}

  is equivalent to:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{if}\NormalTok{ b }\KeywordTok{then}\NormalTok{ [ e }\FunctionTok{|} \DataTypeTok{Q}\NormalTok{ ] }\KeywordTok{else}\NormalTok{ []}
\end{Highlighting}
\end{Shaded}
\item
  For any expression \texttt{e}, pattern \texttt{p}, list-valued
  expression \texttt{l}, sequence of qualifiers \texttt{Q}, and fresh
  variable \texttt{ok},

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    [ e }\FunctionTok{|}\NormalTok{ p }\OtherTok{<-}\NormalTok{ l, }\DataTypeTok{Q}\NormalTok{ ]}
\end{Highlighting}
\end{Shaded}

  is equivalent to:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{let}\NormalTok{ ok p }\FunctionTok{=}\NormalTok{ [ e }\FunctionTok{|} \DataTypeTok{Q}\NormalTok{ ] }\CommentTok{-- p is a pattern}
\NormalTok{        ok _ }\FunctionTok{=}\NormalTok{ []}
    \KeywordTok{in}\NormalTok{ concatMap ok l}
\end{Highlighting}
\end{Shaded}
\item
  For any expression \texttt{e}, declaration list \texttt{D}, and
  sequence of qualifiers \texttt{Q},

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    [ e }\FunctionTok{|} \KeywordTok{let} \DataTypeTok{D}\NormalTok{, }\DataTypeTok{Q}\NormalTok{ ]}
\end{Highlighting}
\end{Shaded}

  is equivalent to:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{let} \DataTypeTok{D} \KeywordTok{in}\NormalTok{ [ e }\FunctionTok{|} \DataTypeTok{Q}\NormalTok{ ]}
\end{Highlighting}
\end{Shaded}
\end{enumerate}

Function \texttt{concatMap} and boolean value \texttt{True} are as
defined in the Prelude.

As we saw in a previous chapter, \texttt{concatMap} applies a
list-returning function to each element of an input list and then
concatenates the resulting list of lists into a single list. Both
\texttt{map} and \texttt{filter} can be defined in terms of
\texttt{concatMap}.

Consider the list comprehension:

\begin{verbatim}
~~~{.haskell}
    [ n*n | n<-[1..10], even n ]
~~~
\end{verbatim}

\begin{enumerate}
\def\labelenumi{\alph{enumi}.}
\item
  Apply identity 4:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{let}\NormalTok{ ok n }\FunctionTok{=}\NormalTok{ [ n}\FunctionTok{*}\NormalTok{n }\FunctionTok{|}\NormalTok{ even n ]}
\NormalTok{        ok _ }\FunctionTok{=}\NormalTok{ []}
    \KeywordTok{in}\NormalTok{ concatMap ok [}\DecValTok{1}\FunctionTok{..}\DecValTok{10}\NormalTok{]}
\end{Highlighting}
\end{Shaded}
\item
  Apply identity 2:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{let}\NormalTok{ ok n }\FunctionTok{=}\NormalTok{ [ n}\FunctionTok{*}\NormalTok{n }\FunctionTok{|}\NormalTok{ even n, }\DataTypeTok{True}\NormalTok{ ]}
\NormalTok{        ok _ }\FunctionTok{=}\NormalTok{ []}
    \KeywordTok{in}\NormalTok{ concatMap ok [}\DecValTok{1}\FunctionTok{..}\DecValTok{10}\NormalTok{]}
\end{Highlighting}
\end{Shaded}
\item
  Apply identity 3:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{let}\NormalTok{ ok n }\FunctionTok{=} \KeywordTok{if}\NormalTok{ (even n) }\KeywordTok{then}\NormalTok{ [ n}\FunctionTok{*}\NormalTok{n }\FunctionTok{|} \DataTypeTok{True}\NormalTok{ ]}
\NormalTok{        ok _ }\FunctionTok{=}\NormalTok{ []}
    \KeywordTok{in}\NormalTok{ concatMap ok [}\DecValTok{1}\FunctionTok{..}\DecValTok{10}\NormalTok{]}
\end{Highlighting}
\end{Shaded}
\item
  Apply identity 1:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{let}\NormalTok{ ok n }\FunctionTok{=} \KeywordTok{if}\NormalTok{ (even n) }\KeywordTok{then}\NormalTok{ [ n}\FunctionTok{*}\NormalTok{n ]}
\NormalTok{        ok _ }\FunctionTok{=}\NormalTok{ []}
    \KeywordTok{in}\NormalTok{ concatMap ok [}\DecValTok{1}\FunctionTok{..}\DecValTok{10}\NormalTok{]}
\end{Highlighting}
\end{Shaded}
\end{enumerate}

\subsubsection{Strings of spaces}\label{strings-of-spaces}

Consider a function \texttt{spaces} that takes a number and generates a
string with that many spaces.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    spaces ::} \DataTypeTok{Int} \OtherTok{->} \DataTypeTok{String}
\NormalTok{    spaces n }\FunctionTok{=}\NormalTok{ [ }\CharTok{' '} \FunctionTok{|}\NormalTok{ i}\OtherTok{<-}\NormalTok{[}\DecValTok{1}\FunctionTok{..}\NormalTok{n]]}
\end{Highlighting}
\end{Shaded}

Note that when \texttt{n\ \textless{}\ 1} the result is the empty
string.

\subsubsection{Prime number test}\label{prime-number-test}

Consider a Boolean function \texttt{isPrime} that takes a nonzero
natural number and determines whether the number is \emph{prime}.
(Remember that a prime number is a natural number whose only natural
number factors are 1 and itself.)

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    isPrime ::} \DataTypeTok{Int} \OtherTok{->} \DataTypeTok{Bool}
\NormalTok{    isPrime n }\FunctionTok{|}\NormalTok{ n }\FunctionTok{>} \DecValTok{1} \FunctionTok{=}\NormalTok{ (factors n }\FunctionTok{==}\NormalTok{ [])}
        \KeywordTok{where}\NormalTok{ factors m }\FunctionTok{=}\NormalTok{ [ x }\FunctionTok{|}\NormalTok{ x}\OtherTok{<-}\NormalTok{[}\DecValTok{2}\FunctionTok{..}\NormalTok{(m}\FunctionTok{-}\DecValTok{1}\NormalTok{)], m }\OtherTok{`mod`}\NormalTok{ x }\FunctionTok{==} \DecValTok{0}\NormalTok{ ]}
\NormalTok{    isPrime   _       }\FunctionTok{=}  \DataTypeTok{False}
\end{Highlighting}
\end{Shaded}

\subsubsection{Squares of primes}\label{squares-of-primes}

Consider a function \texttt{sqPrimes} that takes two natural numbers and
returns the list of squares of the prime numbers in the inclusive range
from the first up to the second.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    sqPrimes ::} \DataTypeTok{Int} \OtherTok{->} \DataTypeTok{Int} \OtherTok{->}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{]}
\NormalTok{    sqPrimes m n }\FunctionTok{=}\NormalTok{ [ x}\FunctionTok{*}\NormalTok{x }\FunctionTok{|}\NormalTok{ x}\OtherTok{<-}\NormalTok{[m}\FunctionTok{..}\NormalTok{n], isPrime x ]}
\end{Highlighting}
\end{Shaded}

Alternatively, this function could be defined using \texttt{map} and
\texttt{filter} as follows:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    sqPrimes' ::} \DataTypeTok{Int} \OtherTok{->} \DataTypeTok{Int} \OtherTok{->}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{]}
\NormalTok{    sqPrimes' m n }\FunctionTok{=}\NormalTok{ map (\textbackslash{}x }\OtherTok{->}\NormalTok{ x}\FunctionTok{*}\NormalTok{x) (filter isPrime [m}\FunctionTok{..}\NormalTok{n])}
\end{Highlighting}
\end{Shaded}

\subsubsection{Doubling positive
elements}\label{doubling-positive-elements}

We can use a list comprehension to define (our, by now, old and dear
friend) the function \texttt{doublePos}, which doubles the positive
integers in a list.

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

\subsubsection{Concatenating a list of lists of
lists}\label{concatenating-a-list-of-lists-of-lists}

Consider a program \texttt{superConcat} that takes a list of lists of
lists and concatenates the elements into a single list.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    superConcat ::}\NormalTok{ [[[a]]] }\OtherTok{->}\NormalTok{ [a]}
\NormalTok{    superConcat xsss }\FunctionTok{=}\NormalTok{ [ x }\FunctionTok{|}\NormalTok{ xss}\OtherTok{<-}\NormalTok{xsss, xs}\OtherTok{<-}\NormalTok{xss, x}\OtherTok{<-}\NormalTok{xs ]}
\end{Highlighting}
\end{Shaded}

Alternatively, this function could be defined using Prelude functions
\texttt{concat} and \texttt{map} and functional composition as follows:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    superConcat' ::}\NormalTok{ [[[a]]] }\OtherTok{->}\NormalTok{ [a]}
\NormalTok{    superConcat' }\FunctionTok{=}\NormalTok{ concat }\FunctionTok{.}\NormalTok{ map concat}
\end{Highlighting}
\end{Shaded}

\subsubsection{First occurrence in a
list}\label{first-occurrence-in-a-list}

Consider a function \texttt{position} that takes a list and a value of
the same type. If the value occurs in the list, \texttt{position}
returns the position of the value's first occurrence; if the value does
not occur in the list, \texttt{position} returns 0.

\textbf{Strategy:} \emph{Solve a more general problem first, then use it
to get the specific solution desired.}

In this problem, we generalize the problem to finding \emph{all}
occurrences of a value in a list. This more general problem is actually
easier to solve.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    positions ::} \DataTypeTok{Eq}\NormalTok{ a }\OtherTok{=>}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ a }\OtherTok{->}\NormalTok{ [}\DataTypeTok{Int}\NormalTok{]}
\NormalTok{    positions xs x }\FunctionTok{=}\NormalTok{ [ i }\FunctionTok{|}\NormalTok{ (i,y)}\OtherTok{<-}\NormalTok{zip [}\DecValTok{1}\FunctionTok{..}\NormalTok{length xs] xs, x }\FunctionTok{==}\NormalTok{ y]}
\end{Highlighting}
\end{Shaded}

Function \texttt{zip} is useful in pairing an element of the list with
its position within the list. The subsequent filter removes those pairs
not involving the value \texttt{x}. The ``zipper'' functions can be very
useful within list comprehensions.

Now that we have the positions of all the occurrences, we can use
\texttt{head} to get the first occurrence. Of course, we need to be
careful that we return 0 when there are no occurrences of \texttt{x} in
\texttt{xs}.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    position ::} \DataTypeTok{Eq}\NormalTok{ a }\OtherTok{=>}\NormalTok{ [a] }\OtherTok{->}\NormalTok{ a }\OtherTok{->} \DataTypeTok{Int} 
\NormalTok{    position xs x }\FunctionTok{=}\NormalTok{ head ( positions xs x }\FunctionTok{++}\NormalTok{ [}\DecValTok{0}\NormalTok{] )}
\end{Highlighting}
\end{Shaded}

Because of lazy evaluation, this implementation of \texttt{position} is
not as inefficient as it first appears. The function \texttt{positions}
will, in actuality, only generate the head element of its output list.

Also because of lazy evaluation, the upper bound \texttt{length\ xs} can
be left off the generator in \texttt{positions}. In fact, the function
is more efficient to do so.

\subsection{Problem Solving}\label{problem-solving}

I approach computing science with the following philosophy:

\begin{itemize}
\item
  Programming is the essence of computing science.
\item
  Problem solving is the essence of programming.
\end{itemize}

Here I consider programming as the process of analyzing a problem and
formulating a solution suitable for execution on a computer. The
solution should be correct, elegant, efficient, and robust. It should be
expressed in a manner that is understandable, maintainable, and
reusable. The solution should balance generality and specificity,
abstraction and concreteness.

In my view, programming is far more than just coding. It subsumes the
concerns of algorithms, data structures, and software engineering. It
uses programming languages and software development tools. It uses the
intellectual tools of mathematics, logic, linguistics, and computing
science theory. Etc.

\subsubsection{Polya's insights}\label{polyas-insights}

The mathematician George Polya (1887--1985), a Professor of Mathematics
at Stanford University, said the following in the preface to his book
\emph{Mathematical Discovery: On Understanding, Learning and Teaching
Problem Solving}.

\begin{quote}
Solving a problem means finding a way out of a difficulty, a way around
an obstacle, attaining an aim which was not immediately attainable.
Solving problems is the specific achievement of intelligence, and
intelligence is the specific gift of mankind: solving problems can be
regarded as the most characteristically human activity. \ldots{}

Solving problems is a practical art, like swimming, or skiing, or
playing the piano: you learn it only by imitation and practice.
\ldots{}~ if you wish to learn swimming you have to go into the water,
and if you wish to become a problem solver you have to solve problems.

If you wish to derive the most profit from your effort, look out for
such features of a problem at hand as may be useful in handling the
problems to come. A solution that you have obtained by your own effort
or one that you have read or heard, but have followed with real interest
and insight, may become a \emph{pattern} for you, a model that you can
imitate with advantage in solving similar problems. \ldots{}

Our knowledge about any subject consists of \emph{information} and
\emph{know-how}. If you have genuine \emph{bona fide} experience of
mathematical work on any level, elementary or advanced, there will be no
doubt in your mind that, in mathematics, know-how is much more important
than mere possession of information. \ldots{}~

What is know-how in mathematics? The ability to solve problems---not
merely routine problems but problems requiring some degree of
independence, judgment, originality, creativity. Therefore, the first
and foremost duty \ldots{}~ in teaching mathematics is to emphasize
\emph{methodical work in problem solving.}
\end{quote}

What Polya says for mathematics holds just as much for computing
science.

In his book \emph{How to Solve It}, Polya states four phases of problem
solving. These steps are important for programming as well.

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Understand the problem.
\item
  Devise a plan.
\item
  Carry out the plan, checking each step.
\item
  Reexamine and reconsider the solution. (And, of course, reexamine the
  understanding of the problem, the plan, and the way the plan was
  carried out.)
\end{enumerate}

\subsubsection{Problem-solving
strategies}\label{problem-solving-strategies}

There are many problem-solving strategies applicable to programming in
general and functional programming in particular. We have seen some of
these in the earlier chapters and will see others in later chapters. In
this section, we highlight some of the general techniques.

\paragraph{Solve a more general problem
first}\label{solve-a-more-general-problem-first}

That is, we solve a ``harder'' problem than the specific problem at
hand, then use the solution of the ``harder'' problem to get the
specific solution desired.

Sometimes a solution of the more general problem is actually easier to
find because the problem is simpler to state or more symmetrical or less
obscured by special conditions. The general solution can often be used
to solve other related problems.

Often the solution of the more general problem can actually lead to a
more efficient solution of the specific problem.

We have already seen one example of this technique: finding the first
occurrence of an item in a list.

First, we devised a program to find all occurrences in a list. Then we
selected the first occurrence from the set of all occurrences. (Lazy
evaluation of Haskell programs means that this use of a more general
solution differs very little in efficiency from a specialized version.)

We have also seen several cases where we have generalized problems by
adding one or more \emph{accumulating parameters}. These ``harder''
problems can lead to more efficient tail recursive solutions.

For example, consider the tail recursive Fibonacci program we developed
in a previous chapter. We added two extra arguments to the function.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    fib2 ::} \DataTypeTok{Int} \OtherTok{->} \DataTypeTok{Int}
\NormalTok{    fib2 n }\FunctionTok{|}\NormalTok{ n }\FunctionTok{>=} \DecValTok{0} \FunctionTok{=}\NormalTok{ fibIter n }\DecValTok{0} \DecValTok{1} 
        \KeywordTok{where} 
\NormalTok{            fibIter }\DecValTok{0}\NormalTok{ p q         }\FunctionTok{=}\NormalTok{ p}
\NormalTok{            fibIter m p q }\FunctionTok{|}\NormalTok{ m }\FunctionTok{>} \DecValTok{0} \FunctionTok{=}\NormalTok{ fibIter (m}\FunctionTok{-}\DecValTok{1}\NormalTok{) q (p}\FunctionTok{+}\NormalTok{q)}
\end{Highlighting}
\end{Shaded}

Another approach is to use the \emph{tupling} technique. Instead of
adding extra arguments, we add extra results.

For example, in the Fibonacci program \texttt{fastfib} below, we compute
\texttt{(fib\ n,\ fib\ (n+1))} instead of just \texttt{fib\ n}. This is
a harder problem, but it actually gives us more information to work with
and, hence, provides more opportunity for optimization. (We formally
derive this solution in a later chapter.)

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    fastfib ::} \DataTypeTok{Int} \OtherTok{->} \DataTypeTok{Int}
\NormalTok{    fastfib n }\FunctionTok{|}\NormalTok{ n }\FunctionTok{>=} \DecValTok{0} \FunctionTok{=}\NormalTok{ fst (twofib n)}

\OtherTok{    twofib ::} \DataTypeTok{Int} \OtherTok{->}\NormalTok{ (}\DataTypeTok{Int}\NormalTok{,}\DataTypeTok{Int}\NormalTok{) }
\NormalTok{    twofib }\DecValTok{0} \FunctionTok{=}\NormalTok{ (}\DecValTok{0}\NormalTok{,}\DecValTok{1}\NormalTok{) }
\NormalTok{    twofib n }\FunctionTok{=}\NormalTok{ (b,a}\FunctionTok{+}\NormalTok{b) }
        \KeywordTok{where}\NormalTok{ (a,b) }\FunctionTok{=}\NormalTok{ twofib (n}\FunctionTok{-}\DecValTok{1}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

\paragraph{Solve a simpler problem
first}\label{solve-a-simpler-problem-first}

After solving the simpler problem, we then adapt or extend the solution
to solve the original problem.

Often the mass of details in a problem description makes seeing a
solution difficult. In the previous technique we made the problem easier
by finding a more general problem to solve. In this technique, we move
in the other direction: we find a more specific problem that is similar
and solve it.

At worst, by solving the simpler problem we should get a better
understanding of the problem we really want to solve. The more familiar
we are with a problem, the more information we have about it, and,
hence, the more likely we will be able to solve it.

At best, by solving the simpler problem we will find a solution that can
be easily extended to build a solution to the original problem.

Consider a program to convert a positive integer of up to six digits to
a string consisting of the English words for that number. For example,
\texttt{369027} yields the string:

\begin{verbatim}
    three hundred and sixty-nine thousand and twenty-seven
\end{verbatim}

To deal with the complexity of this problem, we can work as follows:

\begin{enumerate}
\def\labelenumi{\alph{enumi}.}
\tightlist
\item
  Solve the problem of converting a two-digit number to words. (The
  single digit numbers and numbers in teens are special cases.)
\item
  Then extend the two-digit solution to three digits.
\item
  Then extend three-digit solution to to six digits.
\end{enumerate}

See Section 4.1 of the classic Bird/Wadler textbook for the details of
this problem and a solution.

The process of generalizing first-order functions into higher-order
functions is another example of this ``solve a simpler problem first''
strategy. Recall how we motivated the development of the higher-order
library functions such as \texttt{map}, \texttt{filter}, and
\texttt{foldr}. Also consider the function generalization approach used
in the cosequential processing case study.

\paragraph{Reuse off-the-shelf solutions to standard
subproblems}\label{reuse-off-the-shelf-solutions-to-standard-subproblems}

We have been doing this all during this semester, especially since we
began began studying polymorphism and higher-order functions.

The basic idea is to identify standard patterns of computation (e.g.,
standard prelude functions such as \texttt{length}, \texttt{take},
\texttt{zip}, \texttt{map}, \texttt{filter}, \texttt{foldr}) that will
solve some aspects of the problem and then combine (e.g., using function
composition) these standard patterns with your own specialized functions
to construct a solution to the problem.

We have seen several examples of this in these notes and the homework
assignments.

See section 4.2 of the classic Bird/Wadler textbook for a case study
that develops a package of functions to do arithmetic on variable length
integers. The functions take advantage of several of the standard
prelude functions.

\paragraph{Solve a related problem}\label{solve-a-related-problem}

After solving the related problem, we then transform the solution of the
related problem to get a solution to the original problem.

Perhaps we can find an entirely different problem formulation (i.e.,
stated in different terms) for which we can readily find a solution.
Then that solution can be converted into a solution to the problem at
hand.

For example, we can recast a problem in terms of mathematical or logical
frameworks (e.g., sets, relations, graphs, finite state machines,
grammars, or algebraic structures), solve the corresponding problem in
those terms, and then interpret the result for the original problem. The
simplification provided by the frameworks may reveal solutions that are
obscured in the details of the problem. We can also take advantage of
the theory and techniques that have been found previously for the
mathematical frameworks.

Consider the problem of breaking a string of text into the list of its
component lines.

This is not trivial. However, the ``inverse'' problem is trivial. All
that is needed to convert a list of lines to a string of text is to
insert linefeed characters between the lines.

We can first solve the inverse problem (line-folding) and then use it to
calculate what the line-breaking program must be. (See Section 4.3 of
the Bird/Wadler textbook and a later chapter in this course.)

\paragraph{Separate concerns}\label{separate-concerns}

That is, we partition the problem into logically separate problems,
solve each problem separately, then combine the solutions to the
subproblems to construct a solution to the problem at hand.

As we have seen in the above strategies, when a problem is complex and
difficult to attack directly, we search for simpler, but related,
problems to solve, then build a solution to the complex problem from the
simpler problems.

We have seen examples of this approach in earlier chapters and homework
assignments. We separated concerns when we used stepwise refinement to
develop a square root function, data abstraction in the rational number
case study, and function pipelines.

Consider the development of a program to print a calendar for any year
in various formats. We can approach this problem by first separating it
into two independent subproblems:

\begin{enumerate}
\def\labelenumi{\alph{enumi}.}
\tightlist
\item
  building a calendar
\item
  formatting the output
\end{enumerate}

After solving each of these simpler problems, the more complex problem
can be solved easily by combining the two solutions. (See Section 4.5 of
the classic Bird/Wadler textbook for the details of this problem and a
solution.)

\paragraph{Divide and conquer}\label{divide-and-conquer}

This is a special case of the ``solve a simpler problem first''
strategy. In this technique, we must divide the problem into subproblems
that are the same as the original problem except that the size of the
input is smaller.

This process of division continues recursively until we get a problem
that can be solved trivially, then we combined we reverse the process by
combining the solutions to subproblems to form solutions to larger
problems.

Examples of divide and conquer from earlier chapters include the
logarithmic exponentiation function \texttt{expt3} and the merge sort
function \texttt{msort}.

Another common example of the divide and conquer approach is binary
search. (See Section 6.4 of the classic Bird/Wadler textbook.)

There are, of course, other strategies that can be used to approach
problem solving.

\subsection{Exercises}\label{exercises}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Show the list (or string) yielded by each of the following Haskell
  list expressions. Display it using fully specified list bracket
  notation, e.g., expression \texttt{{[}1..5{]}} yields
  \texttt{{[}1,2,3,4,5{]}}.

  \begin{enumerate}
  \def\labelenumii{\alph{enumii}.}
  \item
    \texttt{{[}7..11{]}}
  \item
    \texttt{{[}11..7{]}}
  \item
    \texttt{{[}3,6..12{]}}
  \item
    \texttt{{[}12,9..2{]}}
  \item
    \texttt{{[}\ n*n\ \textbar{}\ n\ \textless{}-\ {[}1..10{]},\ even\ n\ {]}}
  \item
    \texttt{{[}\ 7\ \textbar{}\ n\ \textless{}-\ {[}1..4{]}\ {]}}
  \item
    \texttt{{[}\ x\ \textbar{}\ (x:xs)\ \textless{}-\ {[}Did,\ you,\ study?{]}\ {]}}
  \item
    \texttt{{[}\ (x,y)\ \textbar{}\ x\ \textless{}-\ {[}1..3{]},\ y\ \textless{}-\ {[}4,7{]}\ {]}}
  \item
    \texttt{{[}\ (m,n)\ \textbar{}\ m\ \textless{}-\ {[}1..3{]},\ n\ \textless{}-\ {[}1..m{]}\ {]}}
  \item
    \texttt{take\ 3\ {[}\ {[}1..n{]}\ \textbar{}\ n\ \textless{}-\ {[}1..{]}\ {]}}
  \end{enumerate}
\item
  Translate the following expressions into expressions that use list
  comprehensions. For example, \texttt{map\ (*2)\ xs} could be
  translated to \texttt{{[}\ x*2\ \textbar{}\ x\ \textless{}-\ xs\ {]}}.

  \begin{enumerate}
  \def\labelenumii{\alph{enumii}.}
  \item
    \texttt{map\ (\textbackslash{}x\ -\textgreater{}\ 2*x-1)\ xs}
  \item
    \texttt{filter\ p\ xs}
  \item
    \texttt{map\ (\^{}2)\ (filter\ even\ {[}1..5{]})}
  \item
    \texttt{foldr\ (++)\ {[}{]}\ xss}
  \item
    \texttt{map\ snd\ (filter\ (p\ .\ \ fst)\ (zip\ xs\ {[}1..{]}))}
  \end{enumerate}
\end{enumerate}

\subsection{References}\label{references}

\begin{description}
\tightlist
\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[{[}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[{[}Polya 1945{]}]
George Polya, \emph{How to Solve It}, Princeton University Press, 1945.
\item[{[}Polya 1981{]}]
George Polya, \emph{Mathematical Discovery: On Understanding, Learning
and Teaching Problem Solving}, Wiley, 1981.
\item[{[}Thompson 2011{]}]
Simon Thompon. \emph{Haskell: The Craft of Programming, Third Edition},
Pearson, 2011.
\end{description}

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

TODO

\end{document}
