\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 Basic Haskell Functional Programming},
            pdfauthor={H. Conrad Cunningham},
            pdfborder={0 0 0},
            breaklinks=true}
\urlstyle{same}  % don't use monospace font for urls
\usepackage{graphicx,grffile}
\makeatletter
\def\maxwidth{\ifdim\Gin@nat@width>\linewidth\linewidth\else\Gin@nat@width\fi}
\def\maxheight{\ifdim\Gin@nat@height>\textheight\textheight\else\Gin@nat@height\fi}
\makeatother
% Scale images if necessary, so that they will not overflow the page
% margins by default, and it is still possible to overwrite the defaults
% using explicit options in \includegraphics[width, height, ...]{}
\setkeys{Gin}{width=\maxwidth,height=\maxheight,keepaspectratio}
\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\\
Basic Haskell Functional Programming}
\author{H. Conrad Cunningham}
\date{26 October 2017}

\begin{document}
\maketitle

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

\textbf{Acknowledgements:} I adapted and revised much of this work in
Summer and Fall 2016 from my previous materials.

\begin{itemize}
\item
  Defining Our First Haskell Functions from chapter 3 of my \emph{Notes
  on Functional Programming with Haskell}
\item
  Surveying the Basic Types from chapter 5 of my \emph{Notes on
  Functional Programming with Haskell}
\item
  Using Top-Down Stepwise Refinement (square root module) from my
  earlier implementations of this algorithm in Scala, Elixir, and Lua
  and from section 1.1.7 of Abelson and Sussman's
  \href{http://mitpress.mit.edu/sicp/}{\emph{Structure and
  Interpretation of Computer Programs}}.
\item
  Using Data Abstraction (rational arithmetic module) mostly from
  chapter 5 of my \emph{Notes on Functional Programming with Haskell},
  from my Lua-based implementations, and from section 2.1 of Abelson and
  Sussman's \href{http://mitpress.mit.edu/sicp/}{\emph{Structure and
  Interpretation of Computer Programs}}.
\item
  Modular Design and Programming from my Data Abstraction and Modular
  Design notes
\end{itemize}

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
  Discuss Haskell modules along with Factorial, give links to code
\item
  Discuss testing along with Factorial, give links to code
\item
  Perhaps move introductory discussion of module back to the Factorial
  subsection
\item
  Better integrate the general discussion of data abstraction and
  modular design
\item
  Add more examples
\item
  Edit and add more exercises
\end{itemize}

\setcounter{section}{1}

\section{Basic Haskell Functional
Programming}\label{basic-haskell-functional-programming}

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

This chapter introduces the basic features of the Haskell language
needed for programming using first-order functions, primitive data
types, and tuples. The goal is for the students to be able to use these
features to develop small Haskell programs.

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

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  describe the basic syntax and semantics of first-order Haskell
  functions
\item
  describe the basic Haskell data types
\item
  execute Haskell programs from the REPL
\item
  develop first-order Haskell functional programs using recursion and
  the primitive data types and tuples
\item
  apply top-down refinement and data abstraction to develop Haskell
  modules
\item
  relate the basic Haskell features to similar features in other
  languages
\end{enumerate}

\subsection{Defining Our First Haskell
Functions}\label{defining-our-first-haskell-functions}

Let's look at our first function definition in the Haskell language, a
program to implement the factorial function for natural numbers.

The Haskell source file \href{code02/Fact.hs}{\texttt{Fact.hs}} holds
the Haskell function definitions for this section. The source file
\href{code02/TestFact.hs}{\texttt{TestFact.hs}} gives a simple test
script.

\subsubsection{Factorial function
specification}\label{factorial-function-specification}

We can give two mathematical definitions of factorial, \emph{fact} and
\emph{fact'}, that are equivalent for all natural number arguments. We
can define \emph{fact} using the product operator as follows:

\begin{quote}
\emph{fact}\((n) = \prod_{i=1}^{i=n}\,i\)
\end{quote}

For example,

\begin{quote}
\emph{fact}\((4) = 1 \times 2 \times 3 \times 4\).
\end{quote}

By definition

\begin{quote}
\emph{fact}\((0) = 1\)
\end{quote}

which is the \emph{identity} element of the multiplication operation.

We can also define the factorial function \emph{fact'} with a
\emph{recursive} definition (or \emph{recurrence relation}) as follows:

\begin{quote}
\emph{fact'\((n) = 1\), if \(n = 0\)}\\
\emph{fact'\((n) = n \times\) fact'\((n-1)\), if \(n \geq 1\)}
\end{quote}

Since the domain of \emph{fact'} is the set of natural numbers, a set
over which induction is defined, we can easily see that this recursive
definition is well defined.

\begin{itemize}
\item
  For \(n = 0\), the base case, the value is simply \(1\).
\item
  For \(n \geq 1\), the value of \emph{fact'}\((n)\) is recursively
  defined in terms of \emph{fact'}\((n-1)\). The argument of the
  recursive application decreases toward the base case.
\end{itemize}

In a previous chapter, we proved that \emph{fact}\((n)\) \(=\)
\emph{fact'}\((n)\) by mathematical induction.

The Haskell functions defined in the following subsections must compute
\emph{fact}\((n)\) when applied to argument value \(n\).

\subsubsection{\texorpdfstring{Factorial function using if-then-else:
\texttt{fact1}}{Factorial function using if-then-else: fact1}}\label{factorial-function-using-if-then-else-fact1}

One way to translate the recursive definition \emph{fact'} into Haskell
is the following:

\begin{verbatim}
    fact1 :: Int -> Int 
    fact1 n = if n == 0 then 
                  1 
              else 
                  n * fact1 (n-1) 
\end{verbatim}

\begin{itemize}
\item
  The first line above is the \emph{type signature} for function
  \texttt{fact1}. In general, type signatures have the syntax
  \emph{object} \texttt{::} \emph{type}.

  Haskell type names begin with an uppercase letter.

  The above defines object \texttt{fact1} as a function (denoted by the
  \texttt{-\textgreater{}} symbol) that takes one argument of type
  integer (denoted by the first \texttt{Int}) and returns a value of
  type integer (denoted by the last \texttt{Int}).

  Haskell does not have a built-in natural number type. Thus we choose
  type \texttt{Int} for the argument and result of \texttt{fact1}.

  The \texttt{Int} data type is a bounded integer type, usually the
  integer data type supported directly by the host processor (e.g., 32-
  or 64-bits on most current processors), but it is guaranteed to have
  the range of at least a 30-bit, two's complement integer (\(-2^{29}\)
  to \(2^{29}\)).
\item
  The declaration for the function \texttt{fact1} begins on the second
  line. Note that it is an equation of the form

  \begin{quote}
  \emph{fname parms \texttt{=} body}
  \end{quote}

  where \emph{fname} is the function's name, \emph{parms} are the
  function's parameters, and \emph{body} is an expression defining the
  function's result.

  Function and variable names begin with lowercase letters optionally
  followed by a sequence of characters each of which is a letter, a
  digit, an apostrophe (\texttt{\textquotesingle{}}) (sometimes
  pronounced ``prime''), or an underscore (\texttt{\_}).

  A function may have zero or more parameters. The parameters are listed
  after the function name without being enclosed in parentheses and
  without commas separating them.

  The parameter names may appear in the \emph{body} of the function. In
  the evaluation of a function \emph{application} the actual argument
  values are substituted for parameters in the \emph{body}.
\item
  Above we define the \emph{body} function \texttt{fact1} to be an
  \texttt{if-then-else} \emph{expression}. This kind of expression has
  the form

  \begin{quote}
  \emph{\texttt{if} condition \texttt{then} expression1 \texttt{else}
  expression2}
  \end{quote}

  where

  \begin{quote}
  \emph{condition} is a Boolean expression, that is, an expression of
  Haskell type \texttt{Bool}, which has either \texttt{True} or
  \texttt{False} as its value
  \end{quote}

  \begin{quote}
  \emph{expression1} is the expression that is returned when the
  condition is \texttt{True}
  \end{quote}

  \begin{quote}
  \emph{expression2} is the expression (with the same type as
  \emph{expression1}) that is returned when the condition is
  \texttt{False}
  \end{quote}

  Evaluation of the \texttt{if-then-else} expression in \texttt{fact1}
  yields the value \texttt{1} if argument \texttt{n} has the value
  \texttt{0} (i.e., \texttt{n\ ==\ 0}) and yields the value
  \texttt{n\ *\ fact1\ (n-1)} otherwise.
\item
  The \texttt{else} clause includes a recursive application of
  \texttt{fact1}. The whole expression \texttt{(n-1)} is the argument
  for the recursive application, so we enclose it in parenthesis.

  The value of the argument for the recursive application is less than
  the value of the original argument. For each recursive application of
  \texttt{fact} to a natural number, the argument's value thus moves
  closer to the termination value \texttt{0}.
\item
  Unlike most conventional languages, the \emph{indentation is
  significant} in Haskell. The indentation indicates the nesting of
  expressions.

  For example, in \texttt{fact1} the \texttt{n\ *\ fact1\ (n-1)}
  expression is nested inside the \texttt{else} clause of the
  \texttt{if-then-else} expression.
\item
  This Haskell function does not match the mathematical definition given
  above. What is the difference?

  Notice the domains of the functions. The evaluation of \texttt{fact1}
  will go into an ``infinite loop'' and eventually abort when it is
  applied to a negative value.
\end{itemize}

In Haskell there is \emph{only} one way to form more complex expressions
from simpler ones: \emph{apply} a function.

Neither parentheses nor special operator symbols are used to denote
function application; it is denoted by simply listing the argument
expressions following the function name. For example, a function
\texttt{f} applied to argument expressions \texttt{x} and \texttt{y} is
written in the following \emph{prefix} form:

\begin{verbatim}
    f x y
\end{verbatim}

However, the usual prefix form for a function application is not a
convenient or natural way to write many common expressions. Haskell
provides a helpful bit of syntactic sugar, the \emph{infix} expression.
Thus instead of having to write the addition of \texttt{x} and
\texttt{y} as

\begin{verbatim}
    add x y
\end{verbatim}

we can write it as

\begin{verbatim}
    x + y
\end{verbatim}

as we have since elementary school. Here the symbol \texttt{+}
represents the addition function.

Function application (i.e., juxtaposition of function names and argument
expressions) has higher precedence than other operators. Thus the
expression \texttt{f\ x\ +\ y} is the same as \texttt{(f\ x)\ +\ y}.

\subsubsection{\texorpdfstring{Factorial function using guards:
\texttt{fact2}}{Factorial function using guards: fact2}}\label{factorial-function-using-guards-fact2}

An alternative way to differentiate the two cases in the recursive
definition is to use a different equation for each case. If the Boolean
\emph{guard} (e.g., \texttt{n\ ==\ 0}) for an equation evaluates to
true, then that equation is used in the evaluation of the function. A
guard is written following the \texttt{\textbar{}} symbol as follows:

\begin{verbatim}
    fact2 :: Int -> Int 
    fact2 n 
      | n == 0    = 1 
      | otherwise = n * fact2 (n-1)
\end{verbatim}

Function \texttt{fact2} is equivalent to the \texttt{fact1}. Haskell
evaluates the guards in a top-to-bottom order. The \texttt{otherwise}
guard always succeeds; thus it's use above is similar to the trailing
\texttt{else} clause on the \texttt{if-then-else} expression used in
\texttt{fact1}.

\subsubsection{\texorpdfstring{Factorial function using pattern
matching: \texttt{fact3} and
\texttt{fact4}}{Factorial function using pattern matching: fact3 and fact4}}\label{factorial-function-using-pattern-matching-fact3-and-fact4}

Another equivalent way to differentiate the two cases in the recursive
definition is to use \emph{pattern matching} as follows:

\begin{verbatim}
    fact3 :: Int -> Int 
    fact3 0 = 1 
    fact3 n = n * fact3 (n-1)
\end{verbatim}

The parameter pattern \texttt{0} in the first \emph{leg} of the
definition only matches arguments with value 0. Since Haskell checks
patterns and guards in a top-to-bottom order, the \texttt{n} pattern
matches all nonzero values. Thus \texttt{fact1}, \texttt{fact2}, and
\texttt{fact3} are equivalent.

To stop evaluation from going into an ``infinite loop'' for negative
arguments, we can remove the negative integers from the function's
domain. One way to do this is by using guards to narrow the domain to
the natural numbers as in the definition of \texttt{fact4} below:

\begin{verbatim}
    fact4 :: Int -> Int 
    fact4 n 
        | n == 0 =  1 
        | n >= 1 =  n * fact4 (n-1) 
\end{verbatim}

Function \texttt{fact4} is undefined for negative arguments. If
\texttt{fact4} is applied to a negative argument, the evaluation of the
program encounters an error quickly and returns without going into an
infinite loop. It prints an error and halts further evaluation.

We can define our own error message for the negative case using an
\texttt{error} call as in \texttt{fact4\textquotesingle{}} below.

\begin{verbatim}
    fact4' :: Int -> Int 
    fact4' n 
      | n == 0    =  1 
      | n >= 1    =  n * fact4' (n-1)
      | otherwise = error "fact4' called with negative argument"
\end{verbatim}

In addition to displaying the custom error message, this also displays a
stack trace of the active function calls.

\subsubsection{\texorpdfstring{Factorial function using a built-in
library function:
\texttt{fact5}}{Factorial function using a built-in library function: fact5}}\label{factorial-function-using-a-built-in-library-function-fact5}

The four definitions we have looked at so far use recursive patterns
similar to the recurrence relation \emph{fact'}. Another alternative is
to use the library function \texttt{product} and the list-generating
expression \texttt{{[}1..n{]}} to define a solution that is like the
function \emph{fact}:

\begin{verbatim}
    fact5 :: Int -> Int 
    fact5 n = product [1..n]
\end{verbatim}

The list expression \texttt{{[}1..n{]}} generates a \emph{list} of
consecutive integers beginning with \texttt{1} and ending with
\texttt{n}. We study lists in a later chapter.

The library function \texttt{product} computes the product of the
elements of a finite list.

If we apply \texttt{fact5} to a negative argument, the expression
\texttt{{[}1..n{]}} generates an empty list. Applying \texttt{product}
to this empty list yields 0, which is the identity element for
multiplication. Defining \texttt{fact5} to return 0 is consistent with
the function \emph{fact} upon which it is based.

Which of the above definitions for the factorial function is better?

Most people in the functional programming community would consider
\texttt{fact4} (or \texttt{fact4\textquotesingle{}}) and \texttt{fact5}
as being better than the others. The choice between them depends upon
whether we want to trap the application to negative numbers as an error
or to return the value 1.

\subsection{Using the Glasgow Haskell Compiler
(GHC)}\label{using-the-glasgow-haskell-compiler-ghc}

See the
\href{https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/}{Glasgow
Haskell Compiler Users Guide} for information on the Glasgow Haskell
Compiler (GHC) and its use.

GHCi is an environment for using GHC interactively. That is, it is a
REPL (Read-Evaluate-Print-Loop) command line interface using Haskell.
The
\href{https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/ghci.html}{``Using
GHCi''} chapter of the User Guide describes its usage.

Below, we show a GHCi session where we load source code file (module)
\href{code02/Fact.hs}{\texttt{Fact.hs}} and apply the factorial
functions to various inputs. The instructor ran this in a Terminal
session on an iMac running macOS 10.12.6 (Sierra) with \texttt{ghc}
8.2.1 installed.

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Start the REPL.

\begin{verbatim}
bash-3.2$ ghci
GHCi, version 8.2.1: http://www.haskell.org/ghc/  :? for help
\end{verbatim}
\item
  Load module \texttt{Fact} that holds the factorial function
  definitions. This assumes the \texttt{Fact.hs} file is in the current
  directory. The \texttt{load} command can be abbreviated as just
  \texttt{:l}.

\begin{verbatim}
Prelude> :load Fact
[1 of 1] Compiling Fact             ( Fact.hs, interpreted )
Ok, 1 module loaded.
\end{verbatim}
\item
  Inquire about the type of \texttt{fact1}.

\begin{verbatim}
*Fact> :type fact1
fact1 :: Int -> Int
\end{verbatim}
\item
  Apply function \texttt{fact1} to 7, 0, 20, and 21. Note that the
  factorial of 21 exceeds the \texttt{Int} range.

\begin{verbatim}
*Fact> fact1 7
5040
*Fact> fact1 0
1
*Fact> fact1 20
2432902008176640000
*Fact> fact1 21
-4249290049419214848
\end{verbatim}
\item
  Apply functions \texttt{fact2}, \texttt{fact3}, \texttt{fact4} and
  \texttt{fact5} to 7.

\begin{verbatim}
*Fact> fact2 7
5040
*Fact> fact3 7
5040
*Fact> fact4 7
5040
*Fact> fact5 7 
5040 
\end{verbatim}
\item
  Apply functions \texttt{fact1}, \texttt{fact2}, and \texttt{fact3} to
  -1. All go into an infinite recursion, eventually terminating with an
  error when the runtime stack overflows its allocated space.

\begin{verbatim}
*Fact> fact1 (-1)
*** Exception: stack overflow
*Fact> fact2 (-1)
*** Exception: stack overflow
*Fact> fact3 (-1)
*** Exception: stack overflow
\end{verbatim}
\item
  Apply functions \texttt{fact4} and \texttt{fact4\textquotesingle{}} to
  -1. They quickly return with an error.

\begin{verbatim}
*Fact> fact4 (-1)
*** Exception: Fact.hs:(33,1)-(35,29): Non-exhaustive patterns 
    in function fact4
*Fact> fact4' (-1)
*** Exception: fact4' called with negative argument
CallStack (from HasCallStack):
  error, called at Fact.hs:50:17 in main:Fact
\end{verbatim}
\item
  Apply function \texttt{fact5} to -1. It returns a 1 because it is
  defined for negative integers.

\begin{verbatim}
*Fact> fact5 (-1)
1
\end{verbatim}
\item
  Set the \texttt{+s} option to get information about the time and space
  required and the \texttt{+t} option to get the type of the returned
  value.

\begin{verbatim}
*Fact> :set +s
*Fact> fact1 20
2432902008176640000
(0.00 secs, 80,672 bytes)
*Fact> :set +t
*Fact> fact1 20
2432902008176640000
it :: Int
(0.00 secs, 80,720 bytes)
*Fact> :unset +s +t
*Fact> fact1 20
2432902008176640000
\end{verbatim}
\item
  Exit GHCi.

\begin{verbatim}
:quit
Leaving GHCi.
\end{verbatim}
\end{enumerate}

Suppose we had set the environment variable \texttt{EDITOR} to our
favorite text editor in the Terminal window. For example, on a Mac OS
system, your instructor might give the following command in shell (or in
a startup script such as \texttt{.bash\_profile}):

\begin{verbatim}
    export EDITOR=Aquamacs
\end{verbatim}

Then the \texttt{:edit} command within GHCi allows us to edit the source
code. We can give a filename or default to the last file loaded.

\begin{verbatim}
    :edit
\end{verbatim}

Or we could also use a \texttt{:set} command to set the editor within
GHCi.

\begin{verbatim}
    :set editor Aquamacs
    ...
    :edit
\end{verbatim}

See the
\href{https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/}{Glasgow
Haskell Compiler Users Guide} for more information about use of GHC and
GHCi.

\subsection{Surveying the Basic Types}\label{surveying-the-basic-types}

The type system is an important part of Haskell; the compiler or
interpreter uses the type information to detect errors in expressions
and function definitions. To each expression Haskell assigns a
\emph{type} that describes the kind of value represented by the
expression.

Haskell has both built-in types (defined in the language or its standard
libraries) and facilities for defining new types. In the following we
discuss the primary built-in types. As we have seen, a Haskell type name
begins with a capital letter.

In these notes, we sometimes refer to the types \texttt{Int},
\texttt{Float}, \texttt{Double}, \texttt{Bool}, and \texttt{Char} as
being \emph{primitive} because they likely have direct support in the
host processor's hardware.

\subsubsection{\texorpdfstring{Integers: \texttt{Int} and
\texttt{Integer}}{Integers: Int and Integer}}\label{integers-int-and-integer}

The \texttt{Int} data type is usually an integer data type supported
directly by the host processor (e.g., 32- or 64-bits on most current
processors), but it is guaranteed to have the range of at least a
30-bit, two's complement integer.

The type \texttt{Integer} is an unbounded precision integer type. Unlike
\texttt{Int}, host processors usually do not support this type directly.
The Haskell library or runtime system typically supports this type in
software.

Haskell supports the usual integer literals (i.e., constants) and
operations such as \texttt{+}, \texttt{-}, \texttt{*},
\texttt{\textless{}}, etc.

For integer division, Haskell provides functions \texttt{div} and
\texttt{rem} such that \texttt{div\ m\ n} returns the integral quotient
from dividing \texttt{m} by \texttt{n} and \texttt{rem\ m\ n} returns
the remainder.

\subsubsection{\texorpdfstring{Floating point numbers: \texttt{Float}
and
\texttt{Double}}{Floating point numbers: Float and Double}}\label{floating-point-numbers-float-and-double}

The \texttt{Float} and \texttt{Double} data types are usually the single
and double precision floating point numbers supported directly by the
host processor.

Haskell floating point literals must include a decimal point; they may
be signed or in scientific notation: \texttt{3.14159}, \texttt{2.0},
\texttt{-2.0}, \texttt{1.0e4}, \texttt{5.0e-2}, \texttt{-5.0e-2}.

Haskell supports the usual operations on floating point numbers.
Division is denoted by \texttt{/} as usual.

\subsubsection{\texorpdfstring{Booleans:
\texttt{Bool}}{Booleans: Bool}}\label{booleans-bool}

The \texttt{Bool} data type is usually supported directly by the host
processor as one or more contiguous bits.

The Boolean literals are \texttt{True} and \texttt{False} (note
capitals). Haskell supports Boolean operations such as \texttt{\&\&}
(and), \texttt{\textbar{}\textbar{}} (or), and \texttt{not}.

Functions can match against patterns using the Boolean constants. For
example, we could define a function \texttt{myAnd} as follows:

\begin{verbatim}
    myAnd :: Bool -> Bool -> Bool
    myAnd True  b = b
    myAnd False _ = False
\end{verbatim}

Above the pattern \texttt{\_} is a wildcard that matches any value but
does not bind a value that can be used on the right-hand-side of the
definition.

\subsubsection{\texorpdfstring{Characters:
\texttt{Char}}{Characters: Char}}\label{characters-char}

The \texttt{Char} data type is usually supported directly by the host
processor by one or more contiguous bytes.

Haskell uses Unicode for its character data type. Haskell supports
character literals enclosed in single quotes---including both the
graphic characters (e.g., \texttt{’a’}, \texttt{’0’}, and \texttt{’Z’})
and special codes entered following the escape character backslash
\texttt{\textbackslash{}} (e.g.,
\texttt{\textquotesingle{}\textbackslash{}n\textquotesingle{}} for
newline, \texttt{\textquotesingle{}\textbackslash{}t\textquotesingle{}}
for horizontal tab, and
\texttt{\textquotesingle{}\textbackslash{}\textbackslash{}\textquotesingle{}}
for backslash itself).

In addition, a backslash character \texttt{\textbackslash{}} followed by
a number generates the corresponding Unicode character code. If the
first character following the backslash is \texttt{o}, then the number
is in octal representation; if followed by \texttt{x}, then in
hexadecimal notation; and otherwise in decimal notation.

For example, the exclamation point character can be represented in any
of the following ways: \texttt{’!’},
\texttt{\textquotesingle{}\textbackslash{}33\textquotesingle{}},
\texttt{\textquotesingle{}\textbackslash{}o41\textquotesingle{}},
\texttt{\textquotesingle{}\textbackslash{}x21\textquotesingle{}}

\subsubsection{\texorpdfstring{Functions:
\texttt{t1\ -\textgreater{}\ t2}}{Functions: t1 -\textgreater{} t2}}\label{functions-t1---t2}

If \texttt{t1} and \texttt{t2} are types then
\texttt{t1\ -\textgreater{}\ t2} is the type of a function that takes an
argument of type \texttt{t1} and returns a result of type \texttt{t2}.

Function and variable names begin with lowercase letters optionally
followed by a sequences of characters each of which is a letter, a
digit, an apostrophe (\texttt{\textquotesingle{}}) (sometimes pronounced
``prime''), or an underscore (\texttt{\_}).

Haskell functions are \emph{first-class} objects. They can be arguments
or results of other functions or be components of data structures.
Multi-argument functions are \emph{curried}---that is, treated as if
they take their arguments one at a time.

For example, consider the integer addition operation \texttt{(+)}.
(Surrounding the binary operator symbol with parentheses refers to the
corresponding function.) In mathematics, we normally consider addition
as an operation that takes a \emph{pair} of integers and yields an
integer result, which would have the type signature

\begin{verbatim}
    (+) :: (Int,Int) -> Int
\end{verbatim}

In Haskell, we give the addition operation the type

\begin{verbatim}
    (+) :: Int -> (Int -> Int) 
\end{verbatim}

or just

\begin{verbatim}
    (+) :: Int -> Int -> Int
\end{verbatim}

since Haskell binds \texttt{-\textgreater{}} from the right.

Thus \texttt{(+)} is a one argument function that takes some
\texttt{Int} argument and returns a function of type
\texttt{Int\ -\textgreater{}\ Int}. Hence, the expression
\texttt{((+)\ 5)} denotes a function that takes one argument and returns
that argument plus \texttt{5}.

We sometimes speak of this \texttt{(+)} operation as being
\emph{partially applied} (i.e., to one argument instead of two).

This process of replacing a structured argument by a sequence of simpler
ones is called \emph{currying}, named after American logician Haskell B.
Curry who first described it.

The Haskell library, called the \emph{standard prelude} (or just
Prelude), contains a wide range of predefined functions including the
usual arithmetic, relational, and Boolean operations. Some of these
operations are predefined as \emph{infix} operations.

\subsubsection{\texorpdfstring{Tuples:
\texttt{(t1,t2,...,tn)}}{Tuples: (t1,t2,...,tn)}}\label{tuples-t1t2...tn}

If \texttt{t1}, \texttt{t2}, \(\cdots\), \texttt{tn} are types, where
\texttt{n} is finite and \texttt{n\ \textgreater{}=\ 2}, then is a type
consisting of \emph{n-tuples} where the various components have the type
given for that position.

Each element in a tuple may have different types. The number of elements
in a tuple is fixed.

Examples of tuple values with their types include the following:

\begin{verbatim}
    ('a',1) :: (Char,Int)
    (0.0,0.0,0.0) :: (Double,Double,Double) 
    (('a',False),(3,4)) :: ((Char, Bool), (Int, Int))
    
\end{verbatim}

We can also define a \emph{type synonym} using the \texttt{type}
declaration and the use the synonym in further declarations as follows:

\begin{verbatim}
    type Complex = (Float,Float)
    makeComplex :: Float -> Float -> Complex
    makeComplex r i = (r,i)`
\end{verbatim}

A type synonym does not define a new type, but it introduces an alias
for an existing type. We can use \texttt{Complex} in declarations, but
it has the same effect as using \texttt{(Float,Float)} expect that
\texttt{Complex} provides better documentation of the intent.

\subsubsection{\texorpdfstring{Lists:
\texttt{{[}t{]}}}{Lists: {[}t{]}}}\label{lists-t}

The primary built-in data structure in Haskell is the \emph{list}, a
sequence of values. All the elements in a list must have the same type.
Thus we declare lists with notation such as \texttt{{[}t{]}} to denote a
list of zero or more elements of type \texttt{t}.

A list literal is a comma-separated sequence of values enclosed between
\texttt{{[}} and \texttt{{]}}. For example, \texttt{{[}{]}} is an empty
list and \texttt{{[}1,2,3{]}} is a list of the first three positive
integers in increasing order.

We will look at programming with lists in a later chapter.

\subsubsection{\texorpdfstring{Strings:
\texttt{String}}{Strings: String}}\label{strings-string}

In Haskell, a \emph{string} is just a list of characters. Thus Haskell
defines the data type \texttt{String} as a \emph{type synonym} :

\begin{verbatim}
    type String = [Char]
\end{verbatim}

We examine lists and strings in a later chapter, but, because we use
strings in a few examples in this subsection, let's consider them
briefly.

A \texttt{String} literal is a sequence of zero or more characters
enclosed in double quotes, for example, \texttt{"Haskell\ programming"}.

Strings can contain any graphic character or any special character given
as escape code sequence (using backslash). The special escape code
\texttt{\textbackslash{}\&} is used to separate any character sequences
that are otherwise ambiguous.

For example, the string literal
\texttt{"Hotty\textbackslash{}nToddy!\textbackslash{}n"} is a string
that has two newline characters embedded.

Also the string literal \texttt{"\textbackslash{}12\textbackslash{}\&3"}
represents the two-element list
\texttt{{[}\textquotesingle{}\textbackslash{}12\textquotesingle{},\textquotesingle{}3\textquotesingle{}{]}}.

Because strings are represented as lists, all of the Prelude functions
for manipulating lists also apply to strings. We look at manipulating
lists and strings in later chapters of these notes.

\subsection{Using Top-Down Stepwise
Refinement}\label{using-top-down-stepwise-refinement}

As we saw in a previous chapter, there are two processes of abstraction
in program design and implementation.

\begin{description}
\tightlist
\item[Procedural abstraction:]
the separation of the logical properties of an \emph{action} from the
details of how the action is implemented.
\item[Data abstraction:]
the separation of the logical properties of \emph{data} from the details
of how the data are represented.
\end{description}

This section focuses on procedural abstraction. Later sections focus on
data abstraction.

A useful and intuitive design process for a small program is to begin
with a high-level solution and incrementally fill in the details. We
call this process top-down stepwise refinement. Here we introduce it
with an example.

\subsubsection{Developing a square root
package}\label{developing-a-square-root-package}

Consider the problem of computing the nonnegative square root of a
nonnegative number \(x\). Mathematically, we want to find the number
\(y\) such that

\begin{quote}
\(y \geq 0\) and \(y^{2} = x\).
\end{quote}

A common algorithm in mathematics for computing the above \(y\) is to
use Newton's method of successive approximations, which has the
following steps for square root:

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\tightlist
\item
  Guess at the value of \(y\).
\item
  If the current approximation (guess) is sufficiently close (i.e.~good
  enough), return it and stop; otherwise, continue.
\item
  Compute an improved guess by averaging the value of the guess \(y\)
  and \(x/y\), then go back to step 2.
\end{enumerate}

To encode this algorithm in Haskell, we work top down to decompose the
problem into smaller parts until each part can be solved easily. We
begin this \emph{top-down stepwise refinement} by defining a function
with the type signature:

\begin{verbatim}
    sqrtIter :: Double -> Double -> Double 
\end{verbatim}

We choose type \texttt{Double} (double precision floating point) to
approximate the real numbers. Thus we can encode step 2 of the above
algorithm in Haskell as follows:

\begin{verbatim}
    sqrtIter guess x 
        | goodEnough guess x = guess 
        | otherwise          = sqrtIter (improve guess x) x 
\end{verbatim}

We define \texttt{sqrtIter} to take two arguments--the current
approximation \texttt{guess} and number \texttt{x} for which we need the
square root. We have two cases:

\begin{itemize}
\item
  When the current approximation \texttt{guess} is sufficiently close to
  \texttt{x}, we return \texttt{guess}.

  We abstract this decision into a separate function \texttt{goodEnough}
  with type signature:

\begin{verbatim}
    goodEnough :: Double -> Double -> Bool 
\end{verbatim}
\item
  When the approximation is not yet close enough, we reduce the problem
  to another application of \texttt{sqrtIter} itself to an improved
  approximation.

  We abstract the improvement process into a separate function
  \texttt{improve} with type signature:

\begin{verbatim}
    improve :: Double -> Double -> Double
\end{verbatim}

  To ensure termination of \texttt{sqrtIter}, the argument
  \texttt{(improve\ guess\ x)} on the recursive call must get closer to
  a value that satisfies its base case.
\end{itemize}

The function \texttt{improve} takes the current \texttt{guess} and
\texttt{x} and carries out step 3 of the algorithm, thus averaging
\texttt{guess} and \texttt{x/guess}, as follows:

\begin{verbatim}
    improve :: Double -> Double -> Double 
    improve guess x = average guess (x/guess)
\end{verbatim}

Here we abstract \texttt{average} into a separate function as follows:

\begin{verbatim}
    average :: Double -> Double -> Double
    average x y = (x + y) / 2
\end{verbatim}

The new guess is closer to the square root than the previous guess. Thus
the algorithm will terminate assuming a good choice for function
\texttt{goodEnough}, which guards the base case of the \texttt{sqrtIter}
recursion.

How should we define \texttt{goodEnough}? Given that we are working with
the limited precision of computer floating point arithmetic, it is not
easy to choose an appropriate test for all situations. Here we simplify
this and use a tolerance of 0.001.

We thus postulate the following definition for \texttt{goodEnough}:

\begin{verbatim}
    goodEnough :: Double -> Double -> Bool 
    goodEnough guess x = abs (square guess - x) < 0.001 
\end{verbatim}

In the above, \texttt{abs} is the built-in absolute value function
defined in the standard Prelude library. We define square as the
following simple function (but could replace it by just
\texttt{guess\ *\ guess}):

\begin{verbatim}
    square :: Double -> Double 
    square x = x * x 
\end{verbatim}

What is a good initial guess? It is sufficient to just use 1. So we can
define an overall square root function \texttt{sqrt\textquotesingle{}}
as follows:

\begin{verbatim}
    sqrt' :: Double -> Double
    sqrt' x | x >= 0 = sqrtIter 1 x
\end{verbatim}

(A square root function \texttt{sqrt} is defined in the Prelude library,
so a different name is needed to avoid the name clash.)

\subsubsection{Making the package a Haskell
module}\label{making-the-package-a-haskell-module}

We can make this package into a Haskell module by putting the
definitions in a file (e.g., named \texttt{Sqrt.hs}) and adding a module
header at the beginning as follows:

\begin{verbatim}
    module Sqrt
        (sqrt')
    where
      -- give the definitions above for functions sqrt',
      --   sqrtIter, improve, average, and goodEnough, 
\end{verbatim}

The header gives the module the name \texttt{Sqrt} and defines the names
in parenthesis as being \emph{exported} to other modules that
\emph{import} this module. The other symbols (e.g., \texttt{sqrtIter},
\texttt{goodEnough}) are local to (i.e., hidden inside) the module.

In the above Haskell code, the symbol ``\texttt{-\/-}'' denotes the
beginning of an end-of-line comment. All text after that symbol is text
ignored by the Haskell compiler.

The Haskell module for the Square root case study is in file
\href{code02/Sqrt.hs}{\texttt{Sqrt.hs}}. Limited testing code is in
module \href{code02/TestSqrt.hs}{\texttt{TestSqrt.hs}}.

\subsubsection{Top-down stepwise
refinement}\label{top-down-stepwise-refinement}

The program design strategy known as \emph{top-down stepwise refinement}
is a relatively intuitive design process that has long been applied in
the design of structured programs in imperative procedural languages. It
is also useful in the functional setting.

In Haskell, we can apply top-down stepwise refinement as follows.

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Start with a high-level solution to the problem consisting of one or
  more functions. For each function, identify its type signature and
  functional requirements (i.e., its inputs, outputs, and termination
  condition).

  Some parts of each function are abstracted as ``pseudocode''
  expressions or as-yet-undefined function calls.
\item
  Choose one of the incomplete parts. Consider its type signature and
  functional requirements. Refine the incomplete part by breaking it
  into subparts or, if simple, defining it directly in terms of Haskell
  expressions (including calls to the Prelude or other available library
  functions).

  When refining an incomplete part, consider the various options
  according to the relevant design criteria (e.g., time, space,
  generality, understandability, elegance, etc.)

  The refinement of the function may require a refinement of the data
  being passed. If so, back up in the refinement process and readdress
  previous design decisions as needed.

  If it not possible to design an appropriate refinement, back up in the
  refinement process and readdress previous design decisions.
\item
  Continue step 2 until all parts are fully defined in terms of Haskell
  code and data and the resulting set of functions meets all required
  criteria.
\end{enumerate}

For as long as possible, we should stay with terminology and notation
that is close to the problem being solved. We can do this by choosing
appropriate function names and signatures and data types. (In later
chapters, we examine Haskell's rich set of builtin and user-defined
types.)

For stepwise refinement to work well, we must be willing to back up to
earlier design decisions when appropriate. We should keep good
documentation of the intermediate design steps.

The stepwise refinement method can work well for small programs, but it
may not scale well to large, long-lived, general purpose programs. In
particular, stepwise refinement may lead to a module structure in which
modules are tightly coupled and not robust with respect to changes in
requirements. A combination of techniques may be needed to develop
larger software systems.

\subsection{Using Data Abstraction}\label{using-data-abstraction}

A design technique that can help make a program robust with respect to
change in the data is to use data abstraction. As in the previous
subsection, let's begin with an example.

\subsubsection{Rational number
arithmetic}\label{rational-number-arithmetic}

For this example, let's implement a group of Haskell functions to
perform rational number arithmetic, assuming that the Haskell library
does not contain such a data type.

In mathematics we usually write rational numbers in the form
\(\frac{\texttt{x}}{\texttt{y}}\) where \texttt{x} and \texttt{y} are
integers and \texttt{y} \(\neq\) \texttt{0}.

For now, let's assume we have a special type \texttt{Rat} to represent
rational numbers and a constructor function

\begin{verbatim}
    makeRat :: Int -> Int -> Rat
\end{verbatim}

to create a rational number instance from its numerator \texttt{x} and
denominator \texttt{y}. That is, \texttt{makeRat\ x\ y} constructs
rational number \(\frac{\texttt{x}}{\texttt{y}}\).

Further, let us assume we have selector functions \texttt{numer} and
\texttt{denom} with signatures

\begin{verbatim}
    numer, denom :: Rat -> Int
\end{verbatim}

that each take a \texttt{Rat} argument and return the numerator and
denominator, respectively. That is, they satisfy the equalities:

\begin{verbatim}
    numer (makeRat x y) == x
    denom (makeRat x y) == y
\end{verbatim}

We consider how to implement rational numbers in Haskell later, but for
now let's look at rational arithmetic using the constructor and selector
functions above.

Given the knowledge of rational arithmetic from mathematics, we can
define the operations for unary negation, addition, subtraction,
multiplication, division, and equality.

\begin{verbatim}
    negRat :: Rat -> Rat
    negRat x = makeRat (- numer x) (denom x)

    addRat, subRat, mulRat, divRat :: Rat -> Rat -> Rat 
    addRat x y = makeRat (numer x * denom y + numer y * denom x) 
                         (denom x * denom y)   -- x + y
    subRat x y = makeRat (numer x * denom y - numer y * denom x) 
                         (denom x * denom y)   -- x - y
    mulRat x y = makeRat (numer x * numer y)
                         (denom x * denom y)   -- x * y
    divRat x y = makeRat (numer x * denom y)
                         (denom x * numer y)   -- x / y

    eqRat :: Rat -> Rat -> Bool 
    eqRat x y = (numer x) * (denom y) == (numer y) * (denom x)
\end{verbatim}

Above we give the type signatures for all four functions in the same
type declaration by listing them separated by commas.

These functions all use the type \texttt{Rat}, constructor function
\texttt{makeRat}, and selector functions \texttt{numer} and
\texttt{denom} assumed above. They do not depend upon any specific
representation for rational numbers.

The above six functions work on rational numbers as a \emph{data
abstraction} defined by the type \texttt{Rat}, constructor function
\texttt{makeRat}, and selector functions \texttt{numer} and
\texttt{denom}.

The goal of a data abstraction is to separate the logical properties of
\emph{data} from the details of how the data are represented.

\subsubsection{Rational number data
representation}\label{rational-number-data-representation}

Now, how can we represent rational numbers?

For this package, we define a type synonym \texttt{Rat} to denote this
type:

\begin{verbatim}
    type Rat = (Int, Int) 
\end{verbatim}

For example, \texttt{(1,7)}, \texttt{(-1,-7)}, \texttt{(3,21)}, and
\texttt{(168,1176)} all represent \(\frac{\texttt{1}}{\texttt{7}}\).

As with any value that can be expressed in many different ways, it is
useful to define a single \emph{canonical} (or \emph{normal}) form for
representing values in the rational number type \texttt{Rat}.

It is convenient for us to choose a rational number representation
\texttt{(x,y)} that satisfies the following property, which we call an
\emph{invariant}:

\begin{quote}
\texttt{y\ \textgreater{}\ 0}, \texttt{x} and \texttt{y} are relatively
prime, and zero is denoted uniquely by \texttt{(0,1)}.
\end{quote}

By \emph{relatively prime}, we mean that the two integers have no common
divisors except 1.

By \emph{invariant}, we mean that the logical assertion always holds for
every rational number created by \texttt{makeRat} and manipulated only
by the operations in the \texttt{RationalCore} and \texttt{Rational}
modules.

This representation has the advantage that the magnitudes of the
numerator \texttt{x} and denominator \texttt{y} are kept small, thus
reducing problems with overflow arising during arithmetic operations.

We thus provide a function for constructing rational numbers in this
canonical form. We define constructor \texttt{makeRat} as follows.

\begin{verbatim}
    makeRat :: Int -> Int -> Rat
    makeRat x 0 = error ( "Cannot construct a rational number "
                           ++ showRat (x,0) ++ "\n" ) 
    makeRat 0 _ = (0,1) 
    makeRat x y = (x' `div` d, y' `div` d) 
        where x' = (signum' y) * x 
              y' = abs' y 
              d  = gcd' x' y'
\end{verbatim}

Above we use features of Haskell we have not used in the previous
examples:

\begin{itemize}
\item
  Instead of leaving the \texttt{(x,0)} case undefined, we define an
  explicit \texttt{error} call that returns a custom error message as a
  \texttt{String}.
\item
  To concatenate two strings, we use the infix \texttt{++} (read
  ``append'') operator. (We discuss \texttt{++} in the chapter on
  lists.)
\item
  Putting backticks (\texttt{\textasciigrave{}}) around an alphanumeric
  function name enables us to use that function as an infix operator.
  The function \texttt{div} denotes integer division. Above the
  \texttt{\textasciigrave{}div\textasciigrave{}} operator denotes the
  integer division function used in an infix manner.
\item
  The \texttt{where} clause introduces \texttt{x\textquotesingle{}},
  \texttt{y\textquotesingle{}}, and \texttt{d} as a local definitions
  within the body of \texttt{makeRat}. It can be called from within
  \texttt{makeRat} but not from outside the function. In contrast,
  \texttt{sqrtIter} in the Square Root example is at the same level as
  \texttt{sqrt\textquotesingle{}}, so it can be called by other
  functions (in the same Haskell module at least).

  The \texttt{where} feature allows us to introduce new definitions in a
  top-down manner--first using a symbol and then defining it.
\item
  Instead of defining the types of the local definitions
  \texttt{x\textquotesingle{}}, \texttt{y\textquotesingle{}}, and
  \texttt{d}, we use \emph{type inference}.

  These parameterless functions could be declared

\begin{verbatim}
    x', y', d :: Int
\end{verbatim}

  but it was not necessary because Haskell can infer the types from the
  types involved in their defining expressions.

  Type inference can be used more broadly in Haskell, but explicit type
  declarations should be used for any function called from outside.
\end{itemize}

The function \texttt{signum\textquotesingle{}} (similar to the more
general function \texttt{signum} in the Prelude) takes an integer and
returns the integer \texttt{-1}, \texttt{0}, or \texttt{1} when the
number is negative, zero, or positive, respectively.

\begin{verbatim}
    signum' :: Int -> Int 
    signum' n | n == 0 =  0 
              | n > 0  =  1 
              | n < 0  = -1 
\end{verbatim}

The function \texttt{abs\textquotesingle{}} (similar to the more general
function \texttt{abs} in the Prelude) takes an integer and returns its
absolute value.

\begin{verbatim}
    abs' :: Int -> Int
    abs' n | n >= 0 =  n
           | n <  0 = -n
\end{verbatim}

The function \texttt{gcd\textquotesingle{}} (similar to the more general
function \texttt{gcd} in the Prelude) takes two integers and returns
their greatest common divisor.

\begin{verbatim}
    gcd' :: Int -> Int -> Int 
    gcd' x y = gcd'' (abs' x) (abs' y) 
             where gcd'' x 0 = x 
                   gcd'' x y = gcd'' y (x `rem` y) 
\end{verbatim}

Prelude operation \texttt{rem} returns the remainder from dividing its
first operand by its second.

Given \texttt{makeRat} defined as above, we can define \texttt{numer}
and \texttt{denom} as follows:

\begin{verbatim}
    numer, denom :: Rat -> Int
    numer (x,_) = x
    denom (_,y) = y
\end{verbatim}

Finally, to allow rational numbers to be displayed in the normal
fractional representation, we include function \texttt{showRat} in the
package. We use function \texttt{show}, found in the Prelude, here to
convert an integer to the usual string format and use the list operator
\texttt{++} to concatenate the two strings into one.

\begin{verbatim}
    showRat :: Rat -> String
    showRat x = show (numer x) ++ "/" ++ show (denom x)
\end{verbatim}

Unlike \texttt{Rat}, \texttt{makeRat}, \texttt{numer}, and
\texttt{denom}, function \texttt{showRat} (as implemented) does not use
knowledge of the data representation, but it is used by
\texttt{makeRat}. We could optimize it slightly by allowing it to access
the structure of the tuple directly.

\subsubsection{Modularization}\label{modularization}

There are three groups of functions in this package:

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  the six public rational arithmetic functions \texttt{negRat},
  \texttt{addRat}, \texttt{subRat}, \texttt{mulRat}, \texttt{divRat},
  and \texttt{eqRat}
\item
  the public type \texttt{Rat}, public constructor function
  \texttt{makeRat}, public selector functions \texttt{numer} and
  \texttt{denom}, and string conversion function \texttt{showRat}
\item
  the private utility functions called only by the second group, but
  just reimplementations of Prelude functions anyway
\end{enumerate}

As we have seen, \texttt{Rat}, \texttt{makeRat}, \texttt{numer},
\texttt{denom}, and \texttt{showRat} are the \emph{interface} to the
\emph{data abstraction} that hides the information about the
representation of the data. We can \emph{encapsulate} this group of
functions in a Haskell module as follows. This source code must also be
in a file named \href{code02/RationalCore.hs}{\texttt{RationalCore.hs}}.

\begin{verbatim}
    module RationalCore
        (Rat, makeRat, numer, denom, showRat)
    where
        -- Rat, makeRat, numer, denom, showRat definitions
\end{verbatim}

We can encapsulate the utility functions in a separate module, which
would enable them to be used by several other modules.

However, given that the only use of the utility functions is within the
data representation module, we choose not to separate them at this time.
We leave them in the data abstraction module. Of course, we could also
eliminate them and use the corresponding Prelude functions directly.

Similarly, \texttt{negRat}, \texttt{addRat}, \texttt{subRat},
\texttt{mulRat}, \texttt{divRat}, and \texttt{eqRat} use the core data
abstraction and, in turn, extend the interface to include rational
number arithmetic operations. We can encapsulate these in another
Haskell module that imports the module giving the data representation.
This module must be in a file named
\href{code02/Rational.hs}{\texttt{Rational.hs}}.

\begin{verbatim}
    module Rational 
      ( Rat, makeRat, numer, denom, showRat, -- from RatioalCore
        negRat, addRat, subRat, mulRat, divRat, eqRat )
    where
      import RationalCore
      -- negRat, addRat, subRat, mulRat, divRat, eqRat definitions 
\end{verbatim}

Other modules that use the rational number package can import module
\texttt{Rational}.

This modular approach to program design and implementation offers the
potential of scalability and robustness with respect to change.

The key to this \emph{information-hiding} approach to design is to
identify the aspects of a software system that are most likely to change
from one version to another and make each a design \emph{secret} of some
module.

The secret of the \texttt{RationalCore} module is the rational number
data representation used. The secret of the \texttt{Rational} module
itself is the methods used for rational number arithmetic.

\subsubsection{Alternative rational number data
representation}\label{alternative-rational-number-data-representation}

In the rational number data representation above, constructor
\texttt{makeRat} creates pairs in which the two integers are relatively
prime and the sign is on the numerator. Selector functions
\texttt{numer} and \texttt{denom} just return these stored values.

An alternative representation is to reverse this approach, as shown in
the following module (in file
\href{code02/RationalDeferGCD.hs}{\texttt{RationalDeferGCD.hs}}.)

\begin{verbatim}
    module RationalDeferGCD
      (Rat, makeRat, numer, denom, showRat)
    where

    type Rat = (Int,Int)

    makeRat :: Int -> Int -> Rat
    makeRat x 0 = error ( "Cannot construct a rational number "
                           ++ showRat (x,0) ++ "\n" ) 
    makeRat 0 y = (0,1) 
    makeRat x y = (x,y)

    numer :: Rat -> Int
    numer (x,y) = x' `div` d
        where x' = (signum' y) * x 
              y' = abs' y 
              d  = gcd' x' y'

    denom :: Rat -> Int
    denom (x,y) = y' `div` d
        where x' = (signum' y) * x 
              y' = abs' y 
              d  = gcd' x' y'

    showRat :: Rat -> String
    showRat x = show (numer x) ++ "/" ++ show (denom x)
\end{verbatim}

This approach defers the calculation of the greatest common divisor
until a selector is called.

The invariant for this rational number representation requires that, for
\texttt{(x,y)},

\begin{quote}
\texttt{y} \(\neq\) \texttt{0} and zero is represented uniquely by
\texttt{(0,1)}.
\end{quote}

Furthermore, function \texttt{numer} and \texttt{denom} satisfy the
equalities

\begin{verbatim}
    numer (makeRat x y) == x'
    denom (makeRat x y) == y'
\end{verbatim}

where \texttt{y\textquotesingle{}\ \textgreater{}\ 0},
\texttt{x\textquotesingle{}} and \texttt{y\textquotesingle{}} are
relatively prime, and
\(\frac{\texttt{x}}{\texttt{y}} = \frac{\texttt{x'}}{\texttt{y'}}\).

Question:

\begin{quote}
What are the advantages and disadvantages of the two data
representations?
\end{quote}

Like module \texttt{RationalCore}, the design secret for module
\texttt{RationalDeferGCD} is the rational number data representation.

Regardless of which approach is used, the definitions of the arithmetic
and comparison functions do not change. Thus the \texttt{Rational}
module can import data representation module \texttt{RationalCore} or
\texttt{RationalDeferGCD}.

The figure below shows the dependencies among the modules we have
examined in the rational arithmetic case study.

\begin{figure}
\centering
\includegraphics{Rational_Mod_Dep01.png}
\caption{\textbf{Module Dependency Diagram for Rational Arithmetic Case
Study}}
\end{figure}

We can consider the \texttt{RationalCore} and \texttt{RationalDeferGCD}
modules as two concrete instances (Haskell \texttt{module}s) of a more
abstract module we call ``RationalRep'' in the diagram.

The abstract module ``Rational'' relies on the abstract module
``RationalRep'' for an implemenation of rational numbers. In the Haskell
code above, there are really two versions of the Haskell module
\texttt{Rational} that differ only in whether they import
\texttt{RationalCore} or \texttt{RationalDeferGCD}.

We could also replace alias \texttt{Rat} by a user-defined type to get
another alternative definition of ``RationalRep'', as long as the
interface functions do not have to work with types other than
\texttt{Int}.

\subsection{Modular Design and
Programming}\label{modular-design-and-programming}

Now let's step back from the rational arithmetic case study and consider
the general issues of data abstraction and modular design and
programming.

Software engineering pioneer David Parnas defines a \emph{module} as ``a
work assignment given to a programmer or group of programmers''
{[}Parnas 1978{]}. This is a \emph{software engineering} view of module.

In a programming language like Haskell, a \texttt{module} is also a
program unit defined with a construct or convention. This is a
\emph{programming language} view of a module.

Ideally, a language's module features should support the software
engineering module methods.

\subsubsection{Information-hiding
modules}\label{information-hiding-modules}

According to Parnas, the goals of \emph{modular design} are to {[}Parnas
1972{]}:

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  enable programmers to understand the system by focusing on one module
  at a time (i.e., \emph{comprehensibility}).
\item
  shorten development time by minimizing required communication among
  groups (i.e., \emph{independent development}).
\item
  make the software system flexible by limiting the `number of modules
  affected by significant changes (i.e., \emph{changeability}).
\end{enumerate}

Parnas advocates the use of a principle called \emph{information hiding}
to guide decomposition of a system into appropriate modules (i.e.~work
assignments). He points out that the connections among the modules
should have as few information requirements as possible {[}Parnas
1972{]}.

In the Parnas approach, an information-hiding module:

\begin{itemize}
\item
  forms a \emph{cohesive} unit of functionality \emph{separate} from
  other modules
\item
  \emph{hides} a design decision (its \emph{secret}) from other modules
\item
  \emph{encapsulates} an aspect of system likely to change (its secret)
\end{itemize}

Aspects likely to change independently of each other become secrets of
separate modules. Aspects unlikely to change can become interactions
(connections) among modules.

This approach supports the goal of changeability (goal 2). When care is
taken to design the modules as clean abstractions with well-defined and
documented interfaces, the approach also supports the goals of
independent development (goal 1) and comprehensibility (goal 3).

Information hiding has been absorbed into the dogma of contemporary
object-oriented programming. However, information hiding is often
oversimplified as merely hiding the data and their representations
{[}Weiss 2001{]}.

The secret of a well-designed module may be much more than that. It may
include such knowledge as a specific functional requirement stated in
the requirements document, the processing algorithm used, the nature of
external devices accessed, or even the presence or absence of other
modules or programs in the system {[}Parnas 1972, 1979, 1985{]}. These
are important aspects that may change as the system evolves.

\subsubsection{Interfaces}\label{interfaces}

It is important for information-hiding modules to have well-defined and
stable interfaces.

According to Britton et al, an \emph{interface} is a ``set of
assumptions \ldots{} each programmer needs to make about the other
program \ldots{} to demonstrate the correctness of his own program''
{[}Britton 1981{]}.

An interface includes the type signature of each function (i.e., name,
arguments, and return value) and the constraints on the environment and
argument values (e.g., the invariants).

An \emph{abstract interface} is an interface that does not change when
one module implementation is substituted for another {[}Britton 1981;
Parnas 1978{]}. It concentrates on module's essential aspects and
obscures incidental aspects that vary among implementations.

Information-hiding modules and abstract interfaces enable us to design
and build software systems with multiple versions. The
information-hiding approach seeks to identify aspects of a software
design that might change from one version to another and to hide them
within independent modules behind well-defined abstract interfaces.

We can reuse the software design across several similar systems. We can
reuse an existing module implementation when appropriate. When we need a
new implementation, we can create one by following the specification of
the module's abstract interface.

\subsubsection{Haskell information-hiding
modules}\label{haskell-information-hiding-modules}

As we have seen, in Haskell the \texttt{module} construct can be used to
encapsulate an information-hiding module. The features exported form
part of the interface to the module. One module can \texttt{import}
another module, specifying its dependence on the interface of the other
module.

We define each Haskell module in a separate file. The Haskell compiler
can compile a module independently of others except that the modules it
depends on must be previously compiled. The Haskell build and package
management tools \texttt{cabal-install} and \texttt{stack} support
Haskell modules as their primary units.

The interface of a Haskell module consists of the names and type
signatures of its exported types and functions plus the constraints on
the functions and the expected properties of the ``objects''
manipulated.

In the Rational Arithmetic case study, we defined two information-hiding
modules:

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  ``RationalRep'', whose secret is how to represent the rational number
  data and whose interface consists of the data type \texttt{Rat},
  operations (functions) \texttt{makeRat}, \texttt{numer},
  \texttt{denom}, and \texttt{showRat}, and the constraints on these
  types and functions
\item
  ``Rational'', whose secret is how to implement the rational number
  arithmetic and whose interface consists of operations (functions)
  \texttt{negRat}, \texttt{addRat}, \texttt{subRat}, \texttt{mulRat},
  \texttt{divRat}, and \texttt{eqRat}, the other module's interface, and
  the constraints on these types and functions
\end{enumerate}

We developed two distinct Haskell modules, \texttt{RationalCore} and
\texttt{RationalDeferGCD}, to implement the ``RationalRep''
information-hiding module. We developed one distinct Haskell module,
\texttt{Rational}, to implement the ``Rational'' information-hiding
module. Haskell module \texttt{Rational} can be paired (i.e., by chaning
the \texttt{import} statement) either of the other two variants of
``RationalRep''.

Unfortunately, Haskell 2010 has a relatively weak module system that
does not support multiple implementations as well as we might like.
There is no way to declare that multiple Haskell modules have the same
interface other than copying the common code into each module and
documenting the interface carefully. We must also have multiple versions
of \texttt{Rational} that differ only in which other module is imported.

Together the Glasgow Haskell Compiler (GHC) release 8.2 (July 2017) and
the Cabal-Install package manager release 2.0 (August 2017) support a
new extension, the Backpack mixin package system. This new system
remedies the above shortcoming. In this new approach, we would define
the abstract module ``RationalRep'' as a signature file and require that
\texttt{RationalCore} and \texttt{RationalDeferGCD} conform to it.

Further discussion of this new module system is beyond the scope of this
chapter.

\subsubsection{Invariants}\label{invariants}

As we saw in the Rational Arithmetic case study, a module that provides
a data abstraction must ensure that the objects it creates and
manipulates maintain their integrity--always have a valid structure and
state. An invariant for the data abstraction can help us design and
implement such objects.

\begin{description}
\item[\textbf{Invariant}:]
A logical assertion that must always true for every ``object'' created
by the public constructors and manipulated only by the public operations
of the data abstraction.
\end{description}

Often, we separate an invariant into two parts.

\begin{description}
\item[\textbf{Interface invariant}:]
An invariant stated in terms of the public features and abstract
properties of the ``object''.
\item[\textbf{Implementation (representation) invariant}:]
A detailed invariant giving the required relationships among the
internal features of the implementation of an ``object''
\end{description}

An interface invariant is a key aspect of the abstract interface of a
module. It is useful to the users of the module, as well to the
developers.

In the Rational Arithmetic case study, the interface invariant for the
``RationalRep'' abstract module is the following.

\begin{quote}
For all integers \texttt{x} and nonzero integers \texttt{y},
\end{quote}

\begin{verbatim}
        numer (makeRat x y) == x' 
        denom (makeRat x y) == y' 
\end{verbatim}

\begin{quote}
where \texttt{y\textquotesingle{}\ \textgreater{}\ 0},
\texttt{x\textquotesingle{}} and \texttt{y\textquotesingle{}} are
relatively prime,
\(\frac{\texttt{x}}{\texttt{y}} = \frac{\texttt{x'}}{\texttt{y'}}\) and
if \texttt{x\textquotesingle{}} = 0, then \texttt{y\textquotesingle{}} =
1.
\end{quote}

An implementation invariant guides the developers in the design and
implementation of the internal details of a module. It relates the
internal details to the interface invariant.

We can state an implementation invariant for the \texttt{RationalCore}
module as follows.

\begin{quote}
For all integers \texttt{x} and nonzero integers \texttt{y},
\end{quote}

\begin{verbatim}
        makeRat x y == (x',y')
\end{verbatim}

\begin{quote}
where \texttt{y\textquotesingle{}\ \textgreater{}\ 0},
\texttt{x\textquotesingle{}} and \texttt{y\textquotesingle{}} are
relatively prime,
\(\frac{\texttt{x}}{\texttt{y}} = \frac{\texttt{x'}}{\texttt{y'}}\) and
if \texttt{x\textquotesingle{}} = 0, then \texttt{y\textquotesingle{}} =
1.
\end{quote}

The implementation invariant implies the interface invariant. Although
\texttt{makeRat} does quite a bit of work, \texttt{numer} and
\texttt{denom} are simple.

We can state an implementation invariant for the
\texttt{RationalDeferGCD} module as follows.

\begin{quote}
For all integers \texttt{x} and nonzero integers \texttt{y},
\end{quote}

\begin{verbatim}
        makeRat x y == (x,y)
\end{verbatim}

In this module implementation, \texttt{makeRat} is trivial, thus
\texttt{numer} and \texttt{denom} must do most of the work to establish
the interface invariant.

We will return to the invariant concepts in later chapters.

\subsubsection{Design criteria for
interfaces}\label{design-criteria-for-interfaces}

What makes a good interface for an information-hiding module?

In designing an interface for a module, we should also consider the
following criteria. Of course, some of these criteria conflict with one
another; a designer must carefully balance the criteria to achieve a
good interface design.

Note: These are general principles; they are not limited to Haskell or
functional programming. In object-oriented languages, these criteria
apply to class interfaces.

\begin{itemize}
\item
  \textbf{Cohesion:} All operations must logically fit together to
  support a single, coherent purpose. The module should describe a
  single abstraction.
\item
  \textbf{Simplicity:} Avoid needless features. The smaller the
  interface the easier it is to use the module.
\item
  \textbf{No redundancy:} Avoid offering the same service in more than
  one way; eliminate redundant features.
\item
  \textbf{Atomicity:} Do not combine several operations if they are
  needed individually. Keep independent features separate. All
  operations should be \emph{primitive}, that is, not be decomposable
  into other operations also in the public interface.
\item
  \textbf{Completeness:} All primitive operations that make sense for
  the abstraction should be supported by the module.
\item
  \textbf{Consistency:} Provide a set of operations that are internally
  consistent in

  \begin{itemize}
  \tightlist
  \item
    naming convention (e.g., in use of prefixes like ``set'' or ``get'',
    in capitalization, in use of verbs/nouns/adjectives),
  \item
    use of arguments and return values (e.g., order and type of
    arguments),
  \item
    behavior (i.e., make operations work similarly).
  \end{itemize}

  Avoid surprises and misunderstandings. Consistent interfaces make it
  easier to understand the rest of a system if part of it is already
  known.

  The operations should be consistent with good practices for the
  specific language being used.
\item
  \textbf{Reusability:} Do not customize modules to specific clients,
  but make them general enough to be reusable in other contexts.
\item
  \textbf{Robustness with respect to modifications:} Design the
  interface of an module so that it remains stable even if the
  implementation of the module changes. (That is, it should be an
  abstract interface for an information-hiding module as we discussed
  above.)
\item
  \textbf{Convenience:} Where appropriate, provide additional operations
  (e.g., beyond the complete primitive set) for the convenience of users
  of the module. Add convenience operations only for frequently used
  combinations after careful study.
\end{itemize}

We must trade off conflicts among the criteria. For example, we must
balance:

\begin{itemize}
\tightlist
\item
  completeness versus simplicity
\item
  reusability versus simplicity
\item
  convenience versus consistency, simplicity, no redundancy, and
  atomicity
\end{itemize}

We must also balance these design criteria against efficiency and
functionality.

\subsection{Exercises}\label{exercises}

TODO: Add more exercises for the techniques and features introduced in
this section. Make sure what is here still make sense.

For each of the following exercises, develop and test a Haskell function
or set of functions.

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Develop a Haskell function \texttt{sumsqbig} that takes three numbers
  as arguments and returns the sum of the squares of the two larger
  numbers. That is \texttt{sumsqbig\ 2.0\ 1.0\ 3.0} yields \texttt{13}.
\item
  Develop a Haskell function \texttt{xor} that takes two Booleans and
  returns the ``exclusive-or'' of the two values. An exclusive-or
  operation returns \texttt{True} when exactly one of its arguments is
  \texttt{True} and returns \texttt{False} otherwise.
\item
  Develop a Haskell Boolean function \texttt{div23n5} such that
  \texttt{div23n5\ n} returns \texttt{True} if and only if \texttt{n} is
  divisible by 2 or divisible by 3 but not divisible by 5. That is,
  \texttt{div23n5\ 6} yields \texttt{True} and \texttt{div23n5\ 30}
  yields \texttt{False}.
\item
  Develop a Haskell function \texttt{notDiv} such that
  \texttt{notDiv\ n\ d} returns \texttt{True} if and only if integer
  \texttt{n} is not divisible by \texttt{d}. That is,
  \texttt{notDiv\ 10\ 5} yields \texttt{False} and
  \texttt{notDiv\ 11\ 5} yields \texttt{True}.
\item
  Develop a Haskell function \texttt{mult} that takes two \emph{natural
  numbers} (i.e., nonnegative integers) and returns their product. The
  function must not use the multiplication (\texttt{*}) or division
  (\texttt{div}) operators. Hint: Multiplication can be done by repeated
  addition.
\item
  Develop a Haskell function \texttt{addTax} that takes two
  \texttt{Double} values such that \texttt{addTax\ c\ p} returns
  \texttt{c} with a sales tax of \texttt{p} \emph{percent} added. For
  example, \texttt{addTax\ 2.0\ 9.0} returns \texttt{2.18}.

  Also develop a function \texttt{subTax} that is the inverse of
  \texttt{addTax}. That is, \texttt{subTax\ (addTax\ c\ p)\ p} yields
  \texttt{c}.
\item
  The time of day can be represented by a tuple
  \texttt{(hours,minutes,m)} where \texttt{m} indicates either ``AM'' or
  ``PM''. Develop a Boolean Haskell function \texttt{comesBefore} that
  takes two time-of-day tuples and determines whether the first is an
  earlier time than the second.
\item
  Develop a Haskell function

\begin{verbatim}
minf :: (Int -> Int) -> Int
\end{verbatim}

  such that \texttt{minf\ g} returns the smallest integer \texttt{m}
  such that \texttt{0\ \textless{}=\ m\ \textless{}=\ 10000000} and
  \texttt{g\ m\ ==\ 0} (if such an integer exists).
\item
  Develop a Haskell module (or modules) for line segments on the
  two-dimensional coordinate plane using the \emph{rectangular
  coordinate} system.

  We can represent a line segment with two points--the starting point
  and the ending point. Develop the following Haskell functions:

  \begin{itemize}
  \item
    constructor \texttt{newSeg} that takes two points and returns a new
    line segment
  \item
    selectors \texttt{startPt} and \texttt{endPt} that each take a
    segment and return its starting and ending points, respectively
  \end{itemize}

  We normally represent the plane with a \emph{rectangular coordinate}
  system. That is, we use two axes--an \texttt{x} \emph{axis} and a
  \texttt{y} \emph{axis}--intersecting at a right angle. We call the
  intersection point the \emph{origin} and label it with 0 on both axes.
  We normally draw the \texttt{x} axis horizontally and label it with
  increasing numbers to the right and decreasing numbers to the left. We
  also draw the \texttt{y} axis vertically with increasing numbers
  upward and decreasing numbers downward. Any point in the plane is
  uniquely identified by its \texttt{x}-coordinate and
  \texttt{y}-coordinate.

  Define a data representation for points in the rectangular coordinate
  system and develop the following Haskell functions:

  \begin{itemize}
  \item
    constructor \texttt{newPtFromRect} that takes the \texttt{x} and
    \texttt{y} coordinates of a point and returns a new point
  \item
    selectors \texttt{getx} and \texttt{gety} that takes a point and
    returns the \texttt{x} and \texttt{y} coordinates, respectively
  \item
    display function \texttt{showPt} that takes a point and returns an
    appropriate \texttt{String} representation for the point
  \end{itemize}

  Now, using the various constructors and selectors, also develop the
  Haskell functions for line segments:

  \begin{itemize}
  \item
    \texttt{midPt} that takes a line segment and returns the point at
    the middle of the segment
  \item
    display function \texttt{showSeg} that takes a line segment and
    returns an appropriate \texttt{String} representation
  \end{itemize}

  Note that \texttt{newSeg}, \texttt{startPt}, \texttt{endPt},
  \texttt{midPt}, and \texttt{showSeg} can be implemented independently
  from how the points are represented.
\item
  Develop a Haskell module (or modules) for line segments that
  represents points using the \emph{polar coordinate} system instead of
  the rectangular coordinate system used in the previous exercise.

  A polar coordinate system represents a point in the plane by its
  \emph{radial coordinate} \texttt{r} (i.e., the distance from the
  \emph{pole}) and its \emph{angular coordinate} \texttt{t} (i.e., the
  angle from the \emph{polar axis} in the reference direction). We
  sometimes call \texttt{r} the \emph{magnitude} and \texttt{t} the
  \emph{angle}.

  By convention, we align the rectangular and polar coordinate systems
  by making the origin the pole, the positive portion of the \texttt{x}
  axis the polar axis, and let the first quadrant (where both \texttt{x}
  and \texttt{y} are positive) be the smallest positive angles in the
  reference direction. That is, with a traditional drawing of the
  coordinate systems, we measure and the radial coordinate \texttt{r} as
  the distance from the origin measure the angular coordinate \texttt{t}
  counterclockwise from the positive \texttt{x} axis.

  Using knowledge of trigonometry, we can convert among rectangular
  coordinates \texttt{(x,y)} and polar coordinates \texttt{(r,t)} using
  the equations:

\begin{verbatim}
    x = r * cos(t)
    y = r * sin(t)
    r = sqrt(x^2 + y^2)
    t = arctan2(y,x)
\end{verbatim}

  Define a data representation for points in the polar coordinate system
  and develop the following Haskell functions:

  \begin{itemize}
  \item
    constructor \texttt{newPtFromPolar} that takes the magnitude
    \texttt{r} and angle \texttt{t} as the polar coordinates of a point
    and returns a new point
  \item
    selectors \texttt{getMag} and \texttt{getAng} that each take a point
    and return the magnitude \texttt{r} and angle \texttt{t}
    coordinates, respectively
  \item
    selectors \texttt{getx} and \texttt{gety} that return the \texttt{x}
    and \texttt{y} components of the points (represented here in polar
    coordinates)
  \item
    display functions \texttt{showPtAsRect} and \texttt{showPtAsPolar}
    to convert the points to strings using rectangular and polar
    coordinates, respectively,
  \end{itemize}

  Functions \texttt{newSeg}, \texttt{startPt}, \texttt{endPt},
  \texttt{midPt}, and \texttt{showSeg} should work as in the previous
  exercise.
\item
  Modify the solutions to the previous two line-segment module exercises
  to enable the line segment functions to be in one module that works
  properly if composed with either of the two data representation
  modules. (The solutions may have already done this.)
\item
  Modify the solution to the previous line-segment exercise to use the
  Backpack module system.
\item
  Modify the modules in the previous exercise to enable the line segment
  module to work with both data representations in the same program.
\item
  Modify the solution to the Rational Arithmetic case study to use the
  Backpack module system.
\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-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[{[}Britton 1981{]}]
K. H. Britton, R. A. Parker, and D. L. Parnas. ``A Procedure for
Designing Abstract Interfaces for Device Interface Modules,'' In
\emph{Proceedings of the 5th International Conference on Software
Engineering}, pp.~195-204, March 1981.
\item[{[}Chiusano-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[{[}Dale-Walker 1996{]}]
Nell Dale and Henry M. Walker. \emph{Abstract Data Types:
Specifications, Implementations, and Applications}, D. C. Heath, 1996.
(Especially chapter 1 on ``Abstract Specification Techniques'')
\item[{[}Horstmann 1995{]}]
Cay S. Horstmann. \emph{Mastering Object-Oriented Design in C++}, Wiley,
1995. (Especially chapters 3-6 on ``Implementing Classes'',
``Interfaces'', ``Object-Oriented Design'', and ``Invariants'')
\item[{[}Meyer 1997{]}]
Bertrand Meyer. \emph{Object-Oriented Program Construction}, Second
Edition, Prentice Hall, 1997. (Especially chapter 6 on ``Abstract Data
Types'' and chapter 11 on ``Design by Contract'')
\item[{[}Mossenbock 1995{]}]
Hanspeter Mossenbock. \emph{Object-Oriented Programming in Oberon-2},
Springer-Verlag, 1995. (Especially chapter 3 on ``Data Abstraction'')
\item[{[}Parnas 1972{]}]
D. L. Parnas. ``On the Criteria to Be Used in Decomposing Systems into
Modules,'' \emph{Communications of the ACM}, Vol. 15, No. 12,
pp.1053-1058, 1972.
\item[{[}Parnas 1976{]}]
D. L. Parnas. ``On the Design and Development of Program Families,''
\emph{IEEE Transactions on Software Engineering}, Vol. SE-2, No. 1,
pp.~1-9, March 1976.
\item[{[}Parnas 1978{]}]
D. L. Parnas. ``Some Software Engineering Principles,'' \emph{Infotech
State of the Art Report on Structured Analysis and Design}, Infotech
International, 10 pages, 1978. Reprinted in \emph{Software Fundamentals:
Collected Papers by David L. Parnas}, D. M. Hoffman and D. M. Weiss,
editors, Addison-Wesley, 2001.
\item[{[}Parnas 1979{]}]
D. L. Parnas. ``Designing Software for Ease of Extension and
Contraction,'' \emph{IEEE Transactions on Software Engineering}, Vol.
SE-5, No. 1, pp.~128-138, March 1979.
\item[{[}Parnas 1985{]}]
D. L. Parnas, P. C. Clements, and D. M. Weiss. ``The Modular Structure
of Complex Systems,'' \emph{IEEE Transactions on Software Engineering},
Vol. SE-11, No. 3, pp.~259-266, March 1985.
\item[{[}Thompson 2011{]}]
Simon Thompon. \emph{Haskell: The Craft of Programming, Third Edition},
Pearson, 2011.
\item[{[}Weiss 2001{]}]
D. M. Weiss. ``Introduction: On the Criteria to Be Used in Decomposing
Systems into Modules,'' In \emph{Software Fundamentals: Collected Papers
by David L. Parnas}, D. M. Hoffman and D. M. Weiss, editors,
Addison-Wesley, 2001.
\end{description}

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

Factorials, function definition and application, recursion, function
domains, \texttt{error}, \texttt{if}, guards, basic types (\texttt{Int},
\texttt{Integer}, \texttt{Bool}, \texttt{Char}, functions, tuples,
lists, \texttt{String}), \texttt{type} aliases, library (Prelude)
functions, REPL, \texttt{ghci} commands and use, procedural abstraction,
top-down stepwise refinement, abstract code, termination condition for
recursion, Newton's method, Haskell \texttt{module}, module exports and
imports, rational number arithmetic, data abstraction, properties of
data, data representation, invariant, interface invariant,
implementation or representation invariant, canonical or normal forms,
information hiding, module secret, encapsulation, interface, abstract
interface, design criteria for interfaces, software reuse, Haskell
\texttt{where} local definition, type inference, use of Haskell modules
to implement information-hiding modules rational number arithmetic, data
abstraction, abstract properties of data, data representation,
invariant, interface invariant, implementation or representation
invariant, canonical or normal forms, information hiding, module secret,
encapsulation, interface, abstract interface, design criteria for
interfaces, software reuse, Haskell \texttt{where} local definition,
type inference, use of Haskell modules to implement information-hiding
modules

\end{document}
