A Catalog of Design Patterns in FLP
February 2001
extension April 2011
revision July 2017
Index
Links
| Intent |
Prevent invoking a constructor that might create invalid data |
| Applicability |
A type is too general for a problem |
| Structure |
Replace a call to a constructor with a call
to a function with the same signature.
The function checks the validity of the arguments and
either invokes the constructor or fails |
| Consequences |
Invalid instances of a type are not created |
Motivation
The Missionaries and Cannibals puzzle deals with
3 missionaries and 3 cannibals that cross forth and back
a river on a boat. A state of the puzzle is likely defined by
the following type:
| data State = State Int Int Bool |
where the two integers define the number of missionaries and
cannibals, respectively, on the initial bank of the river and
the boolean tells whether the boat is on the initial bank.
Unfortunately, this representation allows the construction of
states, e.g., State 5 -2 True, that are inconsistent
with the logic of the problem.
Applications
mission.curry
queens.curry
waterjug.curry
knight.curry
| Concurrent Distinct Choices |
| Intent |
Ensure that a mapping from indices to values is injective |
| Applicability |
Index-value pairs are computed concurrently |
| Structure |
A value of the problem is used as an index
in the representation of the mapping (the roles are reversed).
Initially, the values in the representation of the mapping are
free variables. During the computation, the variable at a given
index of the representation is bound to a token which is unique
for that index
|
| Consequences |
The index-value relation is an injective mapping |
Motivation
A cryptarithmetic puzzle presents an arithmetic computation
in which the digits are replaced by letters.
The problem is to find a correspondence from letters to digits
that satisfies the computation. For example:
SEND + MORE = MONEY
9567 + 1085 = 10652 |
A solution is
an injective mapping representing the correspondence from letters to
digits. In an efficient implementation,
the equations for the units, tens, hundreds, etc.,
residuate in no predefined order and are computed concurrently.
Applications
send_more.curry
queens.curry
Further information
Variations of this pattern and more application can be
found here.
| Intent |
Compute the solutions of a problem incrementally |
| Applicability |
A solution consists of a sequence of steps |
| Structure |
Compute a solution of a problem from an
initial partial solution that contains no steps.
Non-deterministically extend the partial solution
step by step until the solution is complete |
| Consequences |
Avoid the explicit representation of the search space |
Motivation
The solutions of many popular puzzles and common problems can be
modeled as sequences of steps. For example, the solution of the
stagecoach problem, which consists in finding a route between
two cities in a network of connections, is a sequence of legs;
the solution of the N-queens puzzle is a sequence of queen placements
on the board;
the solution of the missionaries and cannibals puzzles is a sequence
of river crossing, etc.
Applications
inc_search.curry
mission.curry
queens.curry
stagecoach.curry
waterjug.curry
knight.curry
| Locally Defined Global Identifier |
| Intent |
Ensure that a locally defined identifier is globally distinct |
| Applicability |
A global identifier is declared in a local scope |
| Structure |
Globally distinct identifiers are declared
as local unbound variables possibly to be bound later |
| Consequences |
Local identifiers are globally distinct |
Motivation
A graphical user interface is assembled from components.
Some component, e.g., a slidebar, must refer to some other
component, e.g., a textfield, which is not defined in the same scope.
This and other similar problems, e.g., dynamically generated
HTML pages, are abstracted by the composition
of graphs independently defined. A graph may need to refer to a
node of another graph which is defined by a local identifier, but
must be unique among all the graphs of a composition.
Applications
Graph.curry (library)
examples.curry
(examples of use of the library)
thompson.curry
(NFA construction for accepting regular expressions)
Further information
Variations of this pattern and more application can be
found here.
| Intent |
Ensure that the values of a public type are private |
| Applicability |
The values of a type must be internally/automatically
computed by an application |
| Structure |
Use only unbound variables to define instances of a type.
Enforce this policy by wrapping the values with a private constructor |
| Consequences |
Literal values of a type are not accessible to the programmer |
Motivation
Some data structures express the relations between elements that
are not expressive or interesting by themselves.
For example, in a graphical user interface the name of a textfield
is interesting only because a slidebar must refer to it.
A similar situation occurs in HTML documents.
A generalization of this situation is a graph where the nodes
must be defined only to define the edges.
In these situations it is more general and flexible to avoid
a specific representation of nodes as, e.g., integers or
strings.
Applications
Graph.curry (library)
examples.curry
(examples of use of the library)
thompson.curry
(NFA construction for accepting regular expressions)
| Composite-Visitor-Interpreter |
These patterns are popular and important in Object Oriented programming
languages. Declarative languages trivialize these patterns.
For example, a hierarchy of classes in
an OO language is replaced by a single type declaration in a
functional language, and a visitor is replaced by a single function
that uses pattern matching.
Below are the links to some simple programs that show how the features
of a declarative language simplify the use of these patterns.
Applications
Expr.curry
Statement.curry
Store.curry
Tests.curry
| Intent |
Merge together the generator and tester of a search problem |
| Applicability |
Search problems implemented with a generate-and-test architecture |
| Structure |
Generate the elements of a search space
with a function that simultaneously tests, as much as possible
for the problem at hand, the generated elements. |
| Consequences |
Elements of the search space are not passed from
generator to tester. Sometimes, the code is simpler,
clearer and more efficient. Partially constructed elements
can be eliminated before completion. |
Motivation
Many search problems are solved by generating each element
of a search space an testing whether the element is a goal.
Lazy evaluation is a useful or essential for the efficiency
of execution. However, using strict equality may decrease the
effectiveness of lazy evaluation. Merging together generator
and tester may improve the efficiency. In particular it
reduces the control needed to pass elements from the generator
to the tester and it may allow earlier testing and consequently
pruning of the search space.
Applications
g24.curry
queens.curry
| Intent |
Return multiple values from a function
without defining a containing structure |
| Applicability |
A function must return more than one value |
| Structure |
An argument passed to a function is an unbound variable.
The function binds a value to this variable before returning. |
| Consequences |
Avoid constructing a structure to hold multiple values |
Motivation
When a function must returns multiple values, a standard technique
is to return a structure that holds all the values to be returned.
For example, if function f must return both a value of type A and
a value of type B, the return type could be (A,B), a pair
with components of type A and B, respectively.
The client of f extracts the components of the returned structure
and uses them as appropriate.
Although straightforward, this approach quickly becomes tedious
and produces longer and less readable code.
This pattern, instead, suggests to pass unbound variables to the function
which both returns a value and binds other values to the unbound variables.
Applications
state.curry
maybe.curry
bitexpr.curry
| Intent |
Encode a many-to-many relation with a single simple function |
| Applicability |
A relation is computed in both directions |
| Structure |
A non-deterministic function defines
a one-to-many relation; a functional pattern
defines the inverse relation. |
| Consequences |
Avoid structures to define a relation |
Motivation
We consider a many-to-many relation R between
two sets A and B.
Some element of A is related to distinct elements of
B and, vice versa, distinct elements of A are
related to some element of B.
In a declarative program, such a relation is typically abstracted
by a function f from A to subsets of B, such that
b ∈ f(a) iff a R b.
We will call this function the core function of the relation.
Relations are dual to graphs and, accordingly,
the core function can be defined, e.g., by an adjacency list.
The relation R implicitly defines an inverse relation
which, when appropriate, is encoded in the program
by a function from B to subsets of A,
the core function of the inverse relation.
In this pattern, the core function is encoded as a non-deterministic function
that maps every a ∈ A to every b ∈ B
such that a R b.
The rest of the abstraction is obtained nearly automatically
using standard functional logic features and libraries.
In particular, the core function of the inverse relation, when needed,
is automatically obtained through a functional pattern.
The sets of elements related to a given element are automatically
obtained using the set functions of the core function.
Applications
blood.curry
call_funct.curry
| Intent |
Encode first-order logic formula in programs |
| Applicability |
Problems specified in a first-order logic language |
| Structure |
Apply "there exists"
and "for all" library functions. |
| Consequences |
Programs are encoded specifications |
Motivation
First-order logic is a common and powerful language for the specification of
problems. The ability to execute even some approximation
of this language enables us to directly translate
many specifications into programs.
A consequence of this approach is that the logic of the resulting program
is correct by definition and the code is obtained with very little effort.
The main hurdle is existential quantification, since
specifications of this kind are often not constructive.
However, narrowing, which is the most characterizing feature
of functional logic languages, supports this approach.
Narrowing evaluates expressions, such as a constrains, containing
free variables. The evaluation computes some instantiations of the
variables that lead to the value of the expression, e.g., the
satisfaction of the constrain. Hence, it solves the problem of
existential quantification.
Universal quantification is more straightforward.
Mapping and/or folding operations on sets are sufficient
to verify whether all the elements of the set satisfy some condition.
In particular, set functions can be a convenient mean
to compute the sets required by an abstraction.
Applications
mapcolor.curry
min.curry
queens.curry
itinerary.curry
| Intent |
Pattern matching at arbitrary depth in recursive types |
| Applicability |
Select an element with given properties in a structure |
| Structure |
Combine a type generator with a functional pattern. |
| Consequences |
Separate structure traversal from pattern matching |
Motivation
Pattern matching allows us to easily retrieve the
components of a data structure such as a tuple. Recursively defined
types, such as lists and trees, have components at arbitrary
depths that cannot be selected by pattern matching because pattern
matching selects components only at predetermined positions.
For recursively defined types, the
selection of some element with a given property in a
data structure typically requires code for the traversal of the
structure which is intertwined with the code for using the element. The
combination of functional patterns with type generators
allows us to select elements arbitrarily nested in a
structure in a pattern matching-like fashion without
explicit traversal of the structure and mingling of
different functionalities of a problem.
Applications
addresses.curry
exp.curry
exp_withposition.curry
| Non-determinism introduction and elimination |
| Intent |
Use different algorithms for the same problem |
| Applicability |
Some algorithm is either too slow or it may be incorrect |
| Structure |
Either replace non-deterministic code with deterministic one or vice versa. |
| Consequences |
Improve speed or verify correctness of algorithms |
Motivation
Specifications of problems are often non-deterministic because
in many cases non-determinism defines the desired results of
a computation more easily than by other means.
Thus, it is not unusual for programmers to
initially code non-deterministic programs
even for deterministic problems because this approach
produces correct programs quickly.
We call a prototypical implementation
this direct encoding of a specification.
For some problems, prototypical implementations are not as
efficient as an application requires. In these cases, the
prototypical implementation, often non-deterministic,
should be replaced by a more efficient implementation,
often deterministic, that produces the same result.
We call the latter production implementation.
The investment that went into the prototypical implementation
is not wasted because the specification of the problem is better understood
and it has been tested through the input/output behavior of the
prototypical implementation and possibly debugged and corrected.
Furthermore, the prototypical implementation can be used as a
testing oracle of the production implementation.
Testing can be largely automated, which both reduces
effort and improves reliability.
Applications
min.curry
test.curry
uniq.curry