\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: Organization of Programming Languages Developing Functional Programs},
            pdfauthor={H. Conrad Cunningham},
            pdfborder={0 0 0},
            breaklinks=true}
\urlstyle{same}  % don't use monospace font for urls
\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: Organization of Programming Languages\\
Developing Functional Programs}
\author{H. Conrad Cunningham}
\date{16 September 2017}

\begin{document}
\maketitle

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

\textbf{Acknowledgements:} In Summer 2016, I adapted and revised the
discussion of function generalization from my and Pallavi Tadepalli's
paper ``Using Function Generalization to Design a Cosequential
Processing Framework'' (\emph{Proceedings of the 39th Hawaii
International Conference on System Sciences}, January 2006),

In 2017, I continue to develop this module.

I maintain these notes as text in Pandoc's dialect of MarkDown using
embedded LaTeX markup for the mathematical formulas and translate them
to HTML and PDF

\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
Septeber 2017 is a recent version of Firefox from Mozilla.

TODO:

\begin{itemize}
\tightlist
\item
  Add chapter goals and outcomes
\item
  Cleanup function generalization
\item
  Add eager evaluated version of \texttt{merge4b}, perhaps rename
  \texttt{coseq}
\item
  Add sequential file update example
\item
  Add more content -- e.g., function pipeline?
\item
  Add Exercises
\item
  Add Terms and Concepts
\end{itemize}

\setcounter{section}{5}

\section{Developing Functional
Programs}\label{developing-functional-programs}

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

TODO

\subsection{Developing a Cosequential Processing
Family}\label{developing-a-cosequential-processing-family}

\subsubsection{Function generalization}\label{function-generalization}

In a previous chapter, we examined \emph{families} of related functions
to define generic, higher-order functions to capture the computational
pattern for each family. In this chapter, we approach \emph{function
generalization} more systematically.

The function generalization approach begins with a prototype member of
the family. As in similar techniques for building object-oriented
software frameworks, we apply Scope-Commonality-Variability (SCV)
analysis to the family represented by this prototype. We identify the:

\begin{itemize}
\item
  \emph{scope} -- what is in the family and what is not.
\item
  \emph{commonalities} -- the common, reusable aspects of the family. We
  call these the \emph{frozen spots}.
\item
  \emph{variabilities} -- the aspects that are likely to vary among the
  different members of the family. We call these the \emph{hot spots}.
\end{itemize}

Once we have the above, we incrementally transform the prototype
function for each of the hot spots.

A generalizing transformation may replace specific values or data types
at a hot spot by parameters. We may make a type more abstract, perhaps
making it polymorphic. Or we may break a type into several types if it
plays potentially different roles.

Similarly, a generalizing transformation may replace fixed, specialized
operations at a hot spot by abstract operations. We may make an abstract
operation a higher-order parameter of the generalized function.

We ensure that the new, more general function can implement the
previous, more specialized function.

\subsubsection{Scope}\label{scope}

\emph{Cosequential processing} concerns the coordinated processing of
two ordered sequences to produce some result, often a third ordered
sequence. Key requirements include:

\begin{itemize}
\item
  Both input sequences must be ordered according to the same total
  ordering.
\item
  The processing should be incremental, where only a few elements of
  each sequence (perhaps just one) are examined at a time.
\end{itemize}

This important family includes the ascending merge needed in merge sort,
set and bag operations, and sequential file update applications.

Consider a function \texttt{merge0} that takes two ascending sequences
of integers and merges them together to form a third ascending sequence.

\begin{verbatim}
    merge0 :: [Int] -> [Int] -> [Int]  -- xs, ys
    merge0 [] ys = ys 
    merge0 xs [] = xs 
    merge0 xs@(x:xs') ys@(y:ys') 
      | x < y    = x : merge0 xs' ys 
      | x == y   = x : merge0 xs' ys' 
      | x > y    = y : merge0 xs  ys' 
\end{verbatim}

This function takes two lists of integers and returns a list of
integers.

The \texttt{merge0} function must satisfy a number of properties:

\begin{itemize}
\item
  \emph{Precondition}: The two input lists must be in ascending order.
\item
  \emph{Postcondition}: The output list must also be in ascending order.
  The number of times an element appears in the output list is the
  maximum number of times it appears within one of the two input lists.
\item
  \emph{Termination}: The sum of the lengths of the two input sequences
  must decrease by at least one for each call of the recursive function.
\end{itemize}

For the cosequential processing family, let take function
\texttt{merge0} as the prototype member.

Aside: The \texttt{merge0} function differs from the merge function we
used in merge sort in a previous chapter. For merge sort, the
\texttt{x\ ==\ y} leg would need to remove the head of only one of the
input lists, i.e., be defined as either
\texttt{x\ :\ merge0\ xs\textquotesingle{}\ ys} or
\texttt{x\ :\ merge0\ xs\ ys\textquotesingle{}}.

\subsubsection{Frozen spots}\label{frozen-spots}

Considering the scope and examining the prototype function
\texttt{merge0}, we identify the following frozen spots for the family
of functions:

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  The input consists of two sequences ordered by the same total
  ordering.
\item
  The output consists of a sequence ordered by the same total ordering
  as the input sequences.
\item
  The processing is incremental. Each step examines the current element
  from each input sequence and advances at least one of the input
  sequences for subsequent steps.
\item
  Each step compares the current elements from the input sequences to
  determine what action to take at that step.
\end{enumerate}

The merge function represents the frozen spots of the family. It gives
the common behavior of family members and the relationships among the
various elements of the hot spot subsystems. A hot spot subsystem
consists of a set of Haskell functions, types, and class definitions
that add the desired variability into the merge function.

\subsubsection{Hot spots}\label{hot-spots}

Again considering the scope and examining the prototype function
\texttt{merge0}, we can identify the following hot spots:

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Variability in the total ordering used for the input and output
  sequences, i.e., of the comparison operators and input sequence type.
\item
  The ability to have more complex data entities in the input and output
  sequences, i.e., variability in ``record'' format.
\item
  The ability to vary the input and output sequence structures
  independently of each other.
\item
  Variability in the transformations applied to the data as it passes
  into the output.
\item
  Variability in the sources of the input sequences and destination of
  the output sequence.
\end{enumerate}

We need to be careful to avoid enumerating hot spots that are unlikely
to be needed in an application.

Now let's analyze each hot spot, design a hot spot subsystem, and carry
out the appropriate transformations to generalize the Haskell program.

\subsubsection{Hot spot \#1: Variability in total
ordering}\label{hot-spot-1-variability-in-total-ordering}

In the function \texttt{merge0}, the input and output sequences are
restricted to elements of type \texttt{Int} and the comparison
operations, hence, to the integer comparisons.

The responsibility associated with hot spot \#1 is to enable the base
type of the sequences to be any type upon which an appropriate ordering
is defined. In this transformation, we still consider all three
sequences as containing simple values of the same type.

We can generalize the function to take and return sequences of any
ordered type by making the type of the list polymorphic. Using a type
variable \texttt{a}, we can redefine the type signature to be
\texttt{{[}a{]}}. However, we need to constrain type \texttt{a} to be a
type for which an appropriate total ordering is defined. We do this by
requiring that the type be restricted to those in the predefined Haskell
type class \texttt{Ord}. This class consists of the group of types for
which all six relational operators are defined.

The function resulting from generalization step is \texttt{merge1}.

\begin{verbatim}
    merge1 :: Ord a => [a] -> [a] -> [a]  -- xs, ys
    merge1 []  ys = ys 
    merge1 xs  [] = xs 
    merge1 xs@(x:xs') ys@(y:ys') 
      | x <  y    = x : merge1 xs' ys 
      | x == y    = x : merge1 xs' ys' 
      | x >  y    = y : merge1 xs  ys' 
\end{verbatim}

This function represents the frozen spots of the cosequential processing
framework. The implementation of class \texttt{Ord} used in a program is
hot spot \#1. To satisfy the requirement represented by frozen spot \#1,
we require that the two lists \texttt{xs} and \texttt{ys} be in
ascending order.

Note that, if we restrict \texttt{merge1} polymorphic type \texttt{a} to
\texttt{Int}, then:

\begin{verbatim}
    merge1 xs ys == merge0 xs ys
\end{verbatim}

That is, the generic function \texttt{merge1} can be specialized to be
equivalent to \texttt{merge0}.

\subsubsection{Hot spot \#2: Variability in record
format}\label{hot-spot-2-variability-in-record-format}

The \texttt{merge1} function works with sequences of any type that have
appropriate comparison operators defined. This allows the elements to be
of some built-in type such as \texttt{Int} or \texttt{String} or some
user-defined type that has been declared as an instance of the
\texttt{Ord} class. Thus each individual data item is of a single type.

In general, however, applications in this family will need to work with
data elements that have more complex structures. We refer to these more
complex structures as \emph{records} in the general sense, not just the
Haskell data structure by that name.

The responsibility associated with hot spot \#2 is to enable the
elements of the sequences to be values with more complex structures,
i.e., records. Each record is composed of one or more fields of which
some subset defines the key. The value of the key provides the
information for ordering the records within that sequence.

In this transformation, we still consider all three sequences as
containing simple values of the same type. We abstract the \texttt{key}
as a function on the record type that returns a value of some
\texttt{Ord} type to enable the needed comparisons. We transform the
\texttt{merge1} function by adding \texttt{key} as a higher-order
parameter.

The function resulting from this generalization is \texttt{merge2}.

\begin{verbatim}
    merge2 :: Ord b => (a -> b) -> [a] -> [a] -> [a]  -- key, xs, ys
    merge2 key []  ys  = ys 
    merge2 key xs  []  = xs 
    merge2 key xs@(x:xs') ys@(y:ys') 
      | key x <  key y = x : merge2 key xs' ys 
      | key x == key y = x : merge2 key xs' ys' 
      | key x >  key y = y : merge2 key xs  ys'
\end{verbatim}

The higher-order parameter \texttt{key} represents hot spot \#2 in the
generalized function design.

Hot spot \#1 is the implementation of Haskell class \texttt{Ord} for
values of type \texttt{b}.

To satisfy the requirement represented by frozen spot \#1, the sequence
of keys corresponding to each input sequence, i.e.,
\texttt{map\ key\ xs} and \texttt{map\ key\ ys}, must be in ascending
order.

Also note that

\begin{verbatim}
    merge2 id xs ys == merge1 xs ys
\end{verbatim}

where \texttt{id} is the identity function. Thus \texttt{merge1} is a
specialization of \texttt{merge2}.

\subsubsection{Hot spot \#3: Independent variability of
sequences}\label{hot-spot-3-independent-variability-of-sequences}

In \texttt{merge2}, the records are of the same type in all three
sequences. The key extraction function is also the same for all
sequences.

Some cosequential processing applications, however, require that the
record structure vary among the sequences. For example, the sequential
file update application usually involves a master file and a transaction
file as the inputs and a new master file as the output. The master
records and transaction records usually carry different information.

The responsibility associated with hot spot \#3 is to enable the three
sequences to be varied independently. That is, the records in one
sequence may differ in structure from the records in the others.

This requires separate key extraction functions for the two input
sequences. These must, however, still return key values from the same
total ordering. Because the data types for the two input sequences may
differ and both may differ from the output data type, we must introduce
record transformation functions that convert the input data types to the
output types.

The function resulting from the transformation is \texttt{merge3}.

\begin{verbatim}
    merge3 :: Ord d => (a -> d) -> (b -> d)    -- kx, ky
                       -> (a -> c) -> (b -> c) -- tx, ty
                       -> [a] -> [b] -> [c]    -- xs, ys
    merge3 kx ky tx ty xs ys   = mg xs ys 
        where 
            mg [] ys         = map ty ys 
            mg xs []         = map tx xs 
            mg xs@(x:xs') ys@(y:ys') 
              | kx x <  ky y = tx x : mg xs' ys 
              | kx x == ky y = tx x : mg xs' ys' 
              | kx x >  ky y = ty y : mg xs  ys' 
\end{verbatim}

Higher-order parameters \texttt{kx} and \texttt{ky} are the \emph{key}
extraction functions for the first and second inputs, respectively.
Similarly, \texttt{tx} and \texttt{ty} are the corresponding functions
to \emph{transform} those inputs to the output.

Hot spot \#3 consists of these four functions. In some sense, this
transformation subsumes hot spot \#2.

To avoid repetition of the many unchanging arguments in the recursive
calls, the definition of \texttt{merge3} uses an auxiliary function
definition \texttt{mg}.

The nonrecursive legs use the higher-order library function
\texttt{map}. To satisfy the requirement represented by frozen spot \#1,
the sequence of keys corresponding to each input sequence, i.e.,
\texttt{map\ kx\ xs} and \texttt{map\ ky\ ys}, must be in ascending
order.

If \texttt{xs} and \texttt{ys} are of the same type, then it is true
that:

\begin{verbatim}
    merge3 key key id id xs ys ==  merge2 key xs ys
\end{verbatim}

Thus \texttt{merge2} is a specialization of \texttt{merge3}.

\subsubsection{Hot spot \#4: Variability in sequence
transformations}\label{hot-spot-4-variability-in-sequence-transformations}

Function \texttt{merge3} enabled simple one-to-one, record-by-record
transformations of the input sequences to create the output sequence.
Such simple transformations are not sufficient for practical situations.

For example, in the sequential file update application, each key may be
associated with no more than one record in the master file. However,
there may be any number of update transactions that must be performed
against a master record before the new master record can be output.
Thus, there needs to be some local state maintained throughout the
processing of all the transaction records associated with one master
record.

Before we address the issue of this variation directly, let us
generalize the merge function to make the state that currently exists
(i.e., the evolving output list) explicit in the parameter list.

To do this, we replace the backward linear recursive \texttt{merge3}
function by its \emph{tail recursive} generalization. That is, we add an
\emph{accumulating parameter} \texttt{ss} that is used to collects the
output during the recursive calls and then to generate the final output
when the end of an input sequence is reached.

The initial value of this argument is normally a nil list, but it does
enable some other initial value to be prepended to the output list. This
transformation is shown as function \texttt{merge4a} below.

\begin{verbatim}
    merge4a :: Ord d => (a -> d) -> (b -> d)        -- kx, ky
                        -> (a -> c) -> (b -> c)     -- tx, ty
                        -> [c] -> [a] -> [b] -> [c] -- ss, xs, ys
    merge4a kx ky tx ty ss xs ys = mg ss xs ys 
        where 
            mg ss [] ys      = ss ++ map ty ys 
            mg ss xs []      = ss ++ map tx xs 
            mg ss xs@(x:xs') ys@(y:ys')
              | kx x <  ky y = mg (ss ++ [tx x]) xs' ys 
              | kx x == ky y = mg (ss ++ [tx x]) xs' ys' 
              | kx x >  ky y = mg (ss ++ [ty y]) xs  ys' 
\end{verbatim}

Note that the following holds:

\begin{verbatim}
    merge4a kx ky tx ty ss xs ys == ss ++ merge3 kx ky tx ty xs ys 
\end{verbatim}

Thus function \texttt{merge3} is a specialization of \texttt{merge4a}.

Unfortunately, building up the state \texttt{ss} requires a relatively
expensive appending to the end of a list (e.g.,
\texttt{ss\ ++\ {[}tx\ x{]}} in the third leg).

Now consider hot spot \#4 more explicitly. The responsibility associated
with the hot spot is to enable the use of more general transformations
on the input sequences to produce the output sequence.

To accomplish this, we introduce an explicit \emph{state} to record the
relevant aspects of the computation to some position in the two input
sequences. Each call of the merge function can examine the current
values from the input sequences and update the value of the state
appropriately for the next call.

In some sense, the merge function ``folds'' together the values from the
two input sequences to compute the state. At the end of both input
sequences, the merge function then transforms the state into the output
sequence.

To accomplish this, we can generalize \texttt{merge4a}. We generalize
the accumulating parameter \texttt{ss} in \texttt{merge4a} to be a
parameter \texttt{s} that represents the state. We also replace the two
simple record-to-record transformation functions \texttt{tx} and
\texttt{ty} by more flexible transformation functions \texttt{tl},
\texttt{te}, and \texttt{tg}, that update the state in the three guards
of the recursive leg and functions \texttt{tty} and \texttt{ttx} that
update the state when the first and second input sequences,
respectively, become empty.

For the ``equals'' guard, the amount that the input sequences are
advanced also becomes dependent upon the state of the computation. This
is abstracted as functions \texttt{nex} on the first input sequence and
\texttt{ney} on the second. To satisfy the requirement represented by
frozen spot \#3, the pair of functions \texttt{nex} and \texttt{ney}
must make the following progress requirement true for each call of
\texttt{mg}:

\begin{verbatim}
    if (kx x == ky y) then
      (length (nex s xs) < length xs) || 
      (length (ney s ys) < length ys)
    else True
\end{verbatim}

That is, the client of the framework must ensure that at least one of
the input sequences will be advanced by at least one element. We also
introduce the new function \texttt{res} to take the final state of the
computation and return the output sequence.

The above transformation results in function \texttt{merge4b}.

\begin{verbatim}
    merge4b :: Ord d => (a -> d) -> (b -> d) -> -- kx, ky 
                        (e -> a -> b -> e) ->   -- tl
                        (e -> a -> b -> e) ->   -- te 
                        (e -> a -> b -> e) ->   -- tg
                        (e -> [a] -> [a])  ->   -- nex
                        (e -> [b] -> [b]) ->    -- ney
                        (e -> a -> e) ->        -- ttx
                        (e -> b -> e) ->        -- tty
                        (e -> [c]) -> e ->      -- res, s
                        [a] -> [b] -> [c]       -- xs, ys
    merge4b kx ky tl te tg nex ney ttx tty res s xs ys 
            =  mg s xs ys 
        where 
            mg s [] ys       = res (foldl tty s ys)
            mg s xs []       = res (foldl ttx s xs)
            mg s xs@(x:xs') ys@(y:ys') 
              | kx x <  ky y = mg (tl s x y) xs' ys
              | kx x == ky y = mg (te s x y) (nex s xs) (ney s ys)
              | kx x >  ky y = mg (tg s x y) xs ys 
\end{verbatim}

The function uses the Prelude function \texttt{foldl} in the first two
legs. This function continues the computation beginning with the state
computed by the recursive leg and processes the remainder of the
nonempty input sequence by ``folding'' the remaining elements as defined
in the functions \texttt{ttx} and \texttt{tty}.

As was the case for \texttt{merge3}, frozen spot \#1 requires that
\texttt{map\ kx\ xs} and \texttt{map\ ky\ ys} be in ascending order for
calls to \texttt{merge4b}

Hot spot \#4 consists of the eight functions \texttt{tl}, \texttt{te},
\texttt{tg}, \texttt{ttx}, \texttt{tty}, \texttt{nex} \texttt{ney}, and
\texttt{res}.\\
The following property also holds:

\begin{verbatim}
    merge4b kx ky 
       (\ss x y -> ss ++ [tx x])  -- tl
       (\ss x y -> ss ++ [tx x])  -- te
       (\ss x y -> ss ++ [ty y])  -- tg
       (\ss xs -> tail xs)        -- nex
       (\ss ys -> tail ys)        -- ney
       (\ss x -> ss ++ [x])       -- ttx
       (\ss y -> ss ++ [y])       -- tty
       id ss xs ys                -- res, ss, xs, ys
    == merge4a kx ky tx ty ss xs ys
    == ss ++ merge3 kx ky tx ty xs ys 
\end{verbatim}

That is, we can define the general transformation functions so that they
have the same effect as the record-to-record transformations of
\texttt{merge4a}. The statement of this property uses anonymous
functions. (lambda expression) feature of Haskell.

Thus function \texttt{merge3} is a specialization of \texttt{merge4a},
which in turn is a specialization of function \texttt{merge4b}.

A problem with the above ``implementation'' of \texttt{merge3} is that
the \texttt{merge4b} parameters \texttt{tl}, \texttt{te}, \texttt{tg},
\texttt{ttx}, and \texttt{tty} all involve an expensive operation to
append to the end of the list \texttt{ss}.

An alternative would be to build the state sequence in reverse order and
then reverse the result as shown below.

\begin{verbatim}
    merge4b kx ky 
       (\ss x y -> reverse (tx x) ++ ss)  -- tl
       (\ss x y -> reverse (tx x) ++ ss)  -- tl 
       (\ss x y -> reverse (ty y) ++ ss)  -- tg
       (\ss xs -> tail xs)                -- nex
       (\ss ys -> tail ys)                -- ney
       (\ss x -> x : ss)                  -- ttx
       (\ss y -> y : ss)                  -- tty
       reverse ss xs ys                   -- res, ss, xs, ys
    == merge4a kx ky tx ty ss xs ys
    == ss ++ merge3 kx ky tx ty xs ys 
\end{verbatim}

TODO: Possibly include a version with selective eager evaluation
(similar to below) and rename coseq.

\begin{verbatim}
    merge4c :: Ord d => (a -> d) -> (b -> d) -> -- kx, ky 
                        (e -> a -> b -> e) ->   -- tl
                        (e -> a -> b -> e) ->   -- te 
                        (e -> a -> b -> e) ->   -- tg
                        (e -> [a] -> [a])  ->   -- nex
                        (e -> [b] -> [b]) ->    -- ney
                        (e -> a -> e) ->        -- ttx
                        (e -> b -> e) ->        -- tty
                        (e -> [c]) -> e ->      -- res, s
                        [a] -> [b] -> [c]       -- xs, ys
    merge4b kx ky tl te tg nex ney ttx tty res s xs ys 
            =  mg s xs ys 
        where 
            mg s [] ys       = res (foldl tty s ys)
            mg s xs []       = res (foldl ttx s xs)
            mg s xs@(x:xs') ys@(y:ys') 
              | kx x <  ky y = (mg $! (tl s x y)) xs' ys
              | kx x == ky y = (mg $! (te s x y)) ((nex $! s) xs) 
                                                  ((ney $! s) ys)
              | kx x >  ky y = (mg $! (tg s x y)) xs ys'
\end{verbatim}

\subsubsection{Hot spot \#5 :Variability of sequence
source/destination}\label{hot-spot-5-variability-of-sequence-sourcedestination}

Hot spot \#5 concerns the ability to take the input sequences from many
possible sources and to direct the output to many possible destinations.

In the Haskell merge functions, these sequences are represented as the
pervasive polymorphic list data type. The redirection is simply a matter
of writing appropriate functions to produce the input lists and to
consume its output list. No changes are needed to the \texttt{merge4b}
function itself.

Of course, for any expressions (e.g., function calls) \texttt{ex} and
\texttt{ey} that generate the input sequence arguments \texttt{xs} and
\texttt{ys} of \texttt{merge4b}, it must be the case that sequences
\texttt{map\ kx\ ex} and \texttt{map\ ky\ ey} are ascending.

\subsubsection{Bag and set operation
implementations}\label{bag-and-set-operation-implementations}

TODO: Possibly reexpress some of the lambdas above with standard
combinators.

Mathematically, a \emph{bag} (also called a \emph{multiset}) is an
unordered collection of elements in which each element may occur one or
more times. We can model a bag as a total function (called the
\emph{multiplicity function}) over the domain of elements to the natural
numbers where the numbers 0 and above denote the number of occurrences
of the element in the bag.

A \emph{set} is thus a bag for which there is no more than one occurence
of any element.

If we restrict the elements to a Haskell data type that is an instance
of class \texttt{Ord}, we can represent a bag by an ascending list of
values and a set by an increasing list of values. With this
representation, we can implement the bag an set operations as special
cases of cosequential processing.

The \emph{intersection} of two bags consists of only the elements that
occur in both bags such that the number of occurrences is the minimum
number for the two input bags. We can express the bag intersection of
two ascending lists in terms of \texttt{merge4b} as follows.

\begin{verbatim}
    bagIntersect xs ys =
        merge4b id id
                (\s x y -> s)
                (\s x y -> x:s)
                (\s x y -> s)
                (\s xs -> tail xs) 
                (\s ys -> tail ys)
                (\s x -> s) 
                (\s y -> s)
                reverse [] xs ys
\end{verbatim}

This function only adds an element to the output when it occurs in both
input lists.

If we require the two input lists to be increasing, the above also
implements set intersection.

The \emph{sum} of two bags consists of the elements that occur in either
bag such that the number of occurrences is the total number for both
bags. We can express the bag sum of two ascending lists in terms of
\texttt{merge4b} as follows.

\begin{verbatim}
    bagSum xs ys =
       merge4b id id
               (\s x y -> x:s)
               (\s x y -> x:y:s)
               (\s x y -> y:s)
               (\s xs -> tail xs) 
               (\s ys -> tail ys)
               (\s x -> x:s) 
               (\s y -> y:s)
               reverse [] xs ys
\end{verbatim}

The \emph{union} of two bags consists of the elements that occur in
either bag such that the number of occurrences is the minimum number in
the two input lists. The prototype function \texttt{merge0} implements
this operation on ascending lists.

The \emph{subtraction} of bag \texttt{B} from bag \texttt{A}, denoted
\texttt{A\ -\ B}, consists of only the elements that occur in both bags
such that the number of occurrences is the number of occurrences in
\texttt{A} minus those in \texttt{B}.

Questions:

\begin{itemize}
\item
  How can we represent set union in terms of \texttt{merge4b}?
\item
  How can we represent a merge function that can be used in the merge
  sort of two lists (whose elements are from an instance of class
  \texttt{Ord})?
\item
  How can we implement a bag union function \texttt{bagUnion} in terms
  of \texttt{merge4b}?
\item
  How can we implement a bag subtraction function
  \texttt{bagSub\ xs\ ys} in terms of \texttt{merge4b}?
\item
  If the elements of the input lists are not instances of class
  \texttt{Ord}, how can we implement bag union? bag intersection?
\end{itemize}

\subsubsection{Sequential file update algorithm
(TODO)}\label{sequential-file-update-algorithm-todo}

\begin{verbatim}
    -- Simple Master-Transaction Update
    -- Master increasing list [(Account,Amount)] 
    --   with Account < maxAccount
    -- Transaction ascending list [(Account,Amount)]
    --   with Account < maxAccount
    -- Result is new Master increasing list [(Account,Amount)] 
    --  with Account < maxAccount

    type Account = Int
    type Amount = Integer

    seqUpdate :: [(Account,Amount)] -> [(Account,Amount)] 
                 -> [(Account,Amount)]
    seqUpdate = merge4c fst        fst
                        masterlt   mastereq  mastergt
                        masternext transnext
                        notrans    nomaster
                        getResult  initState

    initState = ([],[])

    maxAccount = maxBound :: Account

    masterlt (out,[])    m t = (m:out,[])
        -- no transactions for this master
    masterlt (out,[cur]) m t = (cur:out,[])
        -- processed all transactions for this master

    mastereq (out,[])        (ma,mb) (_,tc) 
        = (out, [(ma,mb+tc)])   -- first transaction
    mastereq (out,[(sa,sb)]) (_,_)   (_,tc) 
        = (out, [(sa,sb+tc)])   -- subsequent transaction

    mastergt (_,_) m t
        = error ("Transactions not ascending at " ++ show t)

    masternext (_,_) ms = ms -- do not advance master on eq

    transnext  (_,_) ts = let ys = tail ts
                          in if null ys then [(maxAccount,0)] else ys
                          -- advance transaction on eq
                          -- force master with final (maxAccount,0)

    notrans (out,[])    m = (m:out,[])
    notrans (out,[cur]) m = (m:cur:out,[])

    nomaster ([],[])  t  -- only for empty master list
        = error ("Unmatched transaction " ++ show t)
    nomaster (out,[]) (maxInt,_) -- transaction list ended
        = (out,[]) 
    nomaster _        t
        = error ("Unmatched transaction " ++ show t)

    getResult (nms,[]) = reverse nms
\end{verbatim}

\subsubsection{Recap}\label{recap}

This case study illustrates the function generalization method. It
begins with a simple Haskell program to merge two ascending lists of
integers into third ascending list of integers. This program is
generalized in a step by step fashion to produce a new program that is
capable of carrying out any operation from the family of cosequential
processing programs.

Although some members of the cosequential processing family can be
rather complicated, the family has the characteristic that the primary
driver for the algorithm can be concisely stated as a simple loop (i.e.,
recursive function).

\subsection{Exercises}\label{exercises}

TODO

\subsection{References}\label{references}

\begin{description}
\tightlist
\item[{[}Cunningham-Tadepalli 2006{]}]
H. Conrad Cunningham and Pallavi Tadepalli. ``Using Function
Generalization to Design a Cosequential Processing Framework,'' In
\emph{Proceedings of the 39th Hawaii International Conference on System
Sciences}, January 2006.
\end{description}

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

TODO

\end{document}
