# linrec == unfold fold ;

## Greg Buchholz — 2005-10-03 21:34:23

    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 x

    >                     then []

    >                     else f x : unfold p f g (g x)

         Here's some Joy snippets showing unfold in action.  To produce the

    first 10 natural numbers, an unfold might look like...

     > (* Usage: x  p      f    g    unfold *)

    > nats10 == 1 [10 >] [id] [1 +] unfold ;

     ...and the Fibonacci numbers less than 30...

     > fibs30 == [0 1]       (* initial seed is a pair of numbers           *)

    >           [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;

         For comparison, here's the factorial function defined with an

    unfold-fold combination vs. linrec...

     > fac  == [1 <] [id]       [pred] unfold 1 [*] fold ;

    > fac2 == [1 <] [succ] [dup pred]          [*] linrec ;

     ...or for a slightly wrong definition of factorial (0!=0)...

     > 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

     ;

     >

    > (* ugh, these are some *ugly* stack scramblers *)

    > xpfg->xpfgxp == [] cons cons [[] cons cons dup uncons uncons pop

     rolldown]

     >                 dip swap [uncons uncons pop] dip uncons uncons pop ;

    >

    > xpfg->xpfgxf == [] cons cons cons dupd swap [uncons uncons uncons pop]

     dip

     >                 [] cons cons dupd swap [uncons uncons pop] dip ;

    >

    > 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

     uncons

     >                     [[] cons cons cons] dip swap [uncons uncons pop]

     dip

     >                  uncons uncons uncons pop ;

    >

    > xpfg-> == pop pop pop pop ;

    >

     Thanks,

    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

## phimvt@lurac.latrobe.edu.au — 2005-10-06 06:32:59

    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.

    [..]

    Keep us posted with your findings.

      - Manfred

## Narcoleptic Electron — 2005-10-06 14:59:17

    On 10/6/05, phimvt@... <phimvt@...> wrote:

     >

    > 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.

     That's brilliant.  Thanks for sharing your knowledge, Manfred.  And

    Greg.  And everyone else on this list.  I love this place.

    xoxo,

    N. Electron

## sa@dfa.com — 2005-10-06 15:22:44

    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:

     [:]

     > >

    > > 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.

     >

    > That's brilliant.  Thanks for sharing your knowledge, Manfred.  And

    > Greg.  And everyone else on this list.  I love this place.

     i had the identical reaction.  it reads like a little detective story.

    bravo manfred!

     >

    > xoxo,

    > N. Electron

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

    >