Symmetric difference in LC, Pnumerals, and fold
started 8/31/2002; 4:08:31 AM  last post 9/2/2002; 1:56:34 PM


Ehud Lamm  Symmetric difference in LC, Pnumerals, and fold
8/31/2002; 4:08:31 AM (reads: 1341, responses: 1)


Symmetric difference in LC, Pnumerals, and fold 
To compute (diffs ck cl)
we convert cl to a list of length l, and then apply a downorup
operation k times to the list. The downorup operation removes a link
from a list. If, however, it encounters an empty list, it "changes the
direction" and starts adding links. Obviously, the result is the list
whose length is abs(kl). At the last step, we convert the list back
to the corresponding numeral.
If you are familiar with the Peano axioms for natural numbers, you'll feel at home.
Posted to LC by Ehud Lamm on 8/31/02; 4:08:52 AM




Oleg  Re: Symmetric difference in LC, Pnumerals, and fold
9/2/2002; 1:56:34 PM (reads: 542, responses: 0)


I neglected to emphasize the advantage of Pnumerals over Church
numerals: the simplicity of finding a predecessor. Given a lazy order
of evaluation, finding a predecessor of a Pnumeral is a O(1)time and
space operation.
I also wanted to emphasize that the symmetric difference term is
iterative but not recursive. We never needed to resort to a raw
fixpoint combinator. The numerals themselves (as realizations of fold)
can drive iterations.
Thanks, Ehud!



