Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456 FLP Pattern Catalog
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.
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.
Variations of this pattern and more application can be
found here.
Incremental Solution
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.
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.
Variations of this pattern and more application can be
found here.
Opaque Type
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.
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.
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.