Recently while reading up on the Squiggol [1,2] school of program
algebra [3], I had a "Eureka" moment when I realized that the Joy
combinator linrec was a hylomorphism, that is an unfold [4] followed by a
fold [5]. Unfold is the list generator, while fold is its dual, the
list consumer. Unfold takes an initial seed (x), a stopping predicate
(p), a function (f) for producing the list elements from the seed, and
another function (g) for modifying the seed between recursions. In
Haskell, the definition of unfold looks like...
> unfold p f g x = if p xHere's some Joy snippets showing unfold in action. To produce the
> then []
> else f x : unfold p f g (g x)
first 10 natural numbers, an unfold might look like...
> (* Usage: x p f g unfold *)...and the Fibonacci numbers less than 30...
> nats10 == 1 [10 >] [id] [1 +] unfold ;
> fibs30 == [0 1] (* initial seed is a pair of numbers *)For comparison, here's the factorial function defined with an
> [fst 30 >] (* stop when the first member of pair is > 30 *)
> [fst] (* the final list is made up of just the first *)
> (* members of the pairs *)
> [dup snd swap (* create a new pair from the second *)
> uncons uncons pop + (* number and the sum of the first *)
> [] cons cons ] (* and seconds numbers *)
> unfold ;
>
> fst == uncons pop;
> snd == uncons swap pop uncons pop;
unfold-fold combination vs. linrec...
> fac == [1 <] [id] [pred] unfold 1 [*] fold ;...or for a slightly wrong definition of factorial (0!=0)...
> fac2 == [1 <] [succ] [dup pred] [*] linrec ;
> fac3 == [2 <] [id] [dup pred] [*] linrec ;Is there any advantage of one approach over the other? I can see at
least two reasons to prefer the unfold-fold approach.
1.) The call stack is made more explicit. We're dealing with a
intermediate list which could be easily inspected for debugging
purposes, etc.
2.) Decomposing into an unfold-fold might make other program
transformations like fusion or deforestation possible
(or more obvious).
Anyone have other thoughts? Here's my first attempt at writing a
recursive unfold in Joy. I'd be interested to see what better examples
of unfold an experienced concatenator could come up with.
> (* stack required for unfold *);
> (* x -- the initial seed *)
> (* p -- the stopping predicate *)
> (* f -- seed beautifier *)
> (* g -- seed munging predicate *)
>
> unfold == xpfg->xpfgxp i [xpfg-> []] [xpfg->xpfgxf i
> xpfga->xpfgaxg i
> xpfgab->abpfg unfold cons] branch
>rolldown]
> (* ugh, these are some *ugly* stack scramblers *)
> xpfg->xpfgxp == [] cons cons [[] cons cons dup uncons uncons pop
> dip swap [uncons uncons pop] dip uncons uncons pop ;dip
>
> xpfg->xpfgxf == [] cons cons cons dupd swap [uncons uncons uncons pop]
> [] cons cons dupd swap [uncons uncons pop] dip ;uncons
>
> xpfga->xpfgaxg == [] cons cons cons cons dupd swap
> [uncons uncons uncons uncons pop] dip
> [] cons cons dupd swap [uncons uncons pop] dip ;
>
> xpfgab->abpfg == [] cons cons cons cons cons swap pop uncons uncons
> [[] cons cons cons] dip swap [uncons uncons pop]dip
> uncons uncons uncons pop ;Thanks,
>
> xpfg-> == pop pop pop pop ;
>
Greg Buchholz
Notes:
1. Jeremy Gibbons. An Introduction to the Bird-Meertens Formalism.
http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#squiggolintro
2. Erik Meijer, Maarten Fokkinga, Ross Paterson. Functional Programming
with Bananas, Lenses, Envelopes and Barbed Wire.
http://citeseer.ist.psu.edu/meijer91functional.html
3. Manfred von Thun. The Algebra of Joy.
http://www.latrobe.edu.au/philosophy/phimvt/joy/j04alg.html
4. Jeremy Gibbons and Geraint Jones. The Under-Appreciated Unfold.
http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#unfold
5. Graham Hutton. A Tutorial on the Universality and Expressiveness of
Fold
http://citeseer.ist.psu.edu/hutton93tutorial.html
__________________________________
Yahoo! Mail - PC Magazine Editors' Choice 2005
http://mail.yahoo.com
On Mon, 3 Oct 2005, Greg Buchholz wrote:
> Recently while reading up on the Squiggol [1,2] school of program^^^^^^ Yes, I know the feeling
> algebra [3], I had a "Eureka" moment when I realized that the Joy
> combinator linrec was a hylomorphism, that is an unfold [4] followed by aSomething very similar occurred to me quite some time ago. The idea
> fold [5]. Unfold is the list generator, while fold is its dual, the
> list consumer. Unfold takes an initial seed (x), a stopping predicate
> (p), a function (f) for producing the list elements from the seed, and
> another function (g) for modifying the seed between recursions.
was to start with intrinsically useless copy algorithms for the various
data types DT (lists, trees, various number types, even numbers..), such
that
DT DTcopy == DT
For example, for lists:
DEFINE LISTcopy == [null] [pop []] [uncons] [cons] linrec
Not a useful thing, because all it does is to dismantle and then
re-assemble the given list. But let me write it over three lines,
still to be read in a single pass from left to right:
[null] [uncons]
DEFINE LISTcopy == linrec
[pop []] [cons]
Now the two things on the first line define a catamorphism, or
they constitute the essentials of what a list is: A list is
either null, or it can be unconsed into two parts.
The two things in on the third line define an anamorphism, or
they constitute the essential way of building a list: either
by a unary function which ignores its argument (pop) and returns
the empty list, or by consing a new element into an existing list.
Still not very useful, but be patient.
Suppose one does not like this style of writing over three lines.
Define a modified version of linrec:
DEFINE reclin == [swap] dip linrec
(which swaps the second and third element - could also write swapd)
Now define
DEFINE LISTcopy == [null] [uncons] [pop []] [cons] reclin;
Or even
DEFINE LISTana == [null] [uncons];
LISTcata == [pop []] [cons];
LISTcopy == LISTana LISTcata reclin.
Now do the same sort of thing for all sorts of other (linear) data types.
This still gives you useless copy operators. But now mix and match:
DEFINE FOO2BAR == FOOana BARcata reclin
for all the various combinations of FOO and BAR.
For N FOOs and BARs this will give N*N interesting operators, except
for the case where FOO = BAR, which just gives the copy operator.
The number of possibly interesting operators increases with the
square of the number of FOOs and BARs.
Exercise: write some familiar operators in this style. Start with
a definition of size (or length) of lists. That's easy. But then
do the same for more interesting functions.
I did not pursue this line of thought because it did not really increase
the power of the language. But it sure widens one's perspective on things.
[..]
Keep us posted with your findings.
- Manfred
On 10/6/05, phimvt@... <phimvt@...> wrote:
>That's brilliant. Thanks for sharing your knowledge, Manfred. And
> On Mon, 3 Oct 2005, Greg Buchholz wrote:
>
> > Recently while reading up on the Squiggol [1,2] school of program
> > algebra [3], I had a "Eureka" moment when I realized that the Joy
> ^^^^^^ Yes, I know the feeling
> > combinator linrec was a hylomorphism, that is an unfold [4] followed by a
> > fold [5]. Unfold is the list generator, while fold is its dual, the
> > list consumer. Unfold takes an initial seed (x), a stopping predicate
> > (p), a function (f) for producing the list elements from the seed, and
> > another function (g) for modifying the seed between recursions.
>
> Something very similar occurred to me quite some time ago. The idea
> was to start with intrinsically useless copy algorithms for the various
> data types DT (lists, trees, various number types, even numbers..), such
> that
> DT DTcopy == DT
> For example, for lists:
> DEFINE LISTcopy == [null] [pop []] [uncons] [cons] linrec
> Not a useful thing, because all it does is to dismantle and then
> re-assemble the given list. But let me write it over three lines,
> still to be read in a single pass from left to right:
>
> [null] [uncons]
> DEFINE LISTcopy == linrec
> [pop []] [cons]
>
>
> Now the two things on the first line define a catamorphism, or
> they constitute the essentials of what a list is: A list is
> either null, or it can be unconsed into two parts.
> The two things in on the third line define an anamorphism, or
> they constitute the essential way of building a list: either
> by a unary function which ignores its argument (pop) and returns
> the empty list, or by consing a new element into an existing list.
> Still not very useful, but be patient.
>
> Suppose one does not like this style of writing over three lines.
> Define a modified version of linrec:
> DEFINE reclin == [swap] dip linrec
> (which swaps the second and third element - could also write swapd)
> Now define
> DEFINE LISTcopy == [null] [uncons] [pop []] [cons] reclin;
> Or even
> DEFINE LISTana == [null] [uncons];
> LISTcata == [pop []] [cons];
> LISTcopy == LISTana LISTcata reclin.
>
> Now do the same sort of thing for all sorts of other (linear) data types.
> This still gives you useless copy operators. But now mix and match:
> DEFINE FOO2BAR == FOOana BARcata reclin
> for all the various combinations of FOO and BAR.
> For N FOOs and BARs this will give N*N interesting operators, except
> for the case where FOO = BAR, which just gives the copy operator.
> The number of possibly interesting operators increases with the
> square of the number of FOOs and BARs.
>
> Exercise: write some familiar operators in this style. Start with
> a definition of size (or length) of lists. That's easy. But then
> do the same for more interesting functions.
>
> I did not pursue this line of thought because it did not really increase
> the power of the language. But it sure widens one's perspective on things.
Greg. And everyone else on this list. I love this place.
xoxo,
N. Electron
concatenative@yahoogroups.com wrote on 10/06/2005 10:59:17 AM:
> On 10/6/05, phimvt@... <phimvt@...>wrote:
> >[:]
> > On Mon, 3 Oct 2005, Greg Buchholz wrote:
> >increase
> > I did not pursue this line of thought because it did not really
> > the power of the language. But it sure widens one's perspective onthings.
>i had the identical reaction. it reads like a little detective story.
> That's brilliant. Thanks for sharing your knowledge, Manfred. And
> Greg. And everyone else on this list. I love this place.
bravo manfred!
>
> xoxo,
> N. Electron
>
>
>
>
> Yahoo! Groups Links
>
>
>
>
>
>
>