Over the weekend I managed to read Takano and Meijer's paper on shortcut
deforestation in calculational form [1].
Here they propose to split functions in three parts:
<c, N, a>
where c is a catamorphism, N a natural transformation an a an anamorphism.
They propose that when composing functions
<c2, N2, a2> . <c1, N1, a1>
this can be simplified to something like
<c2, N(N2, N1), a1>
where N(N2, N1) is a new natural transformation, dependent on former N2,
N1.
This arises as a generalisation of the <cN, a> notation (foldr/build)
observing that
<cN, a> == <c, Na>, so that the natural transformation can be factored out
in the middle.
This strikingly reminded me to the Dirac formalism of bra-ket notation. (It
is some years ago when I took my QM courses at university, so please do not
flame me with an ion-blaster because of errors.)
Essentially there was a space-vector |q> (ket) and an impulse-vector <p|
(bra) that were connected by an unitary operator (transformation) U:
<p|U|q>
Since U is self-adjoint
<pU|q> == <p|Uq> holds.
There were some nice tricks that could be used simplifying the above
expression, the most popular being the "insertion of a One":
The identity operator 1 was represented as the sum of the orthogonal
projections:
1 == SUM |ei> <ei|
here <ei|q> is the scalar product of the i-th (unit) base vector with a
ket, <ei| the i-th bra (unit) base vector corresponding to <ei| and SUM
becomes an integral in the presence of infinite-dimensional Hilbert space.
Clever insertion of the One ( like <p|U|1|q> == SUM <p|U|ei> <ei|q>) could
cancel out some subterms and leave back expressions that were easily
solvable.
This trick seems to be at the heart of Launchbury and Sheard's "Warm
Fusion" paper (Did they know that this was more than just a play on words?)
The analogy seems to be more than a similarity of notation, since the
multiplications of unitary operators in QM is nothing else than composition
of linear functions, and the 1 operator has the copy function [3] of
algebraic datatypes as corresponding notion in FP.
If in fact there is a deeper connection between FP and QM, I wonder if
other notions of QM such as commutators and Lie-algebras can be exploited
in FP too (along with their reasoning rules)?
Maybe some people more savvy then me in both areas (Jerzy?) can comment on
these thoughts...
Gabor
[1] http://www.cs.uu.nl/~erik/Publications/acid.ps
[2] http://www.cse.ogi.edu/~jl/Papers/warmFusion.ps
[3] http://www.cs.nott.ac.uk/Department/Staff/gmh/bib.html#bananas
