Functional programming texts often start
with the naive definition of reverse:
rev [] = []
rev x:xs = app (rev xs) [x]
which, unfortunately, due to the usual
definition of append:
app [] ys = ys
app x:xs ys = x : (app xs ys)
leads to O(N^2) execution, so the standard
trick involves adding an accumulator:
rev x = rev' x [], where
rev' [] ys = ys
rev' x:xs ys = x : (rev' xs ys)
Is there a way to make "adding an accumulator"
work in theory as well as it does in practice,
so it's not just a rabbit pulled from a hat?
Yes, according to [Hughes], who seems to be
echoing [Filinski] in noting when composing
expressions that functions, from one side,
can be seen as value-transformers:
x : 1->A
foo : A->B
----------------------
foo(x) : 1->B
but from the other side, can also be seen as
continuation-transformers:
exit : B->0
foo : A->B
----------------------
exit(foo(*)) : A->0
so what if functions could be defined with
pattern matching (and substitution) on the
continuations, as well the arguments?
Writing argument / continuation, we wind up
with an O(N) definition for reverse:
rev [] / pre (*) cs = cs
rev x:xs / pre (*) cs = pre (rev xs) (x:cs)
rev xs = pre (rev xs) []
which shows that the extra argument (and even
the extra function) in the accumulator-style
definition is simply an abstract continuation,
reflected to stay on the value-transformation
side of the duality.
-Dave
:: :: ::
| John Hughes, "The Design of a Pretty-printing Library", 1995
| <http://www.cs.chalmers.se/~rjmh/Papers/pretty.ps>
Discusses (en passant) representing values
in two forms:
- term representation, and
- context-passing representation
which are categorical duals, according to:
| Andrzej Filinski, Declarative Continuations and Categorical Duality, 1989
| <http://citeseer.nj.nec.com/filinski89declarative.html>
one usually thinks of expressions being
evaluated to produce Values, but if one
takes Continuations as dual to Values,
then:
Values (1->A) are what they are, and can
be passed to a Function (A->B) to yield
a new Value (1->B), or handed off to a
Continuation (A->0) of the right shape.
Functions can act on Values, as above,
and on Continuations, as below, and can
also be composed directly, from (Z->A)
and (A->B) to (Z->B).
Continuations (A->0) are what they are,
and can be composed with a Function (Z->A)
to yield a new Continuation (Z->0), or
passed a Value (1->A) of the right shape.
think of a spreadsheet: one enters data
into the cells (values), selects output
formats for the cells (continuations),
and puts formulae in between (functions).
For each intermediate cell, cells which
refer to it look like continuations, and
cells to which it refers, like values.
