Lambda the Ultimate

inactiveTopic Symmetric difference in LC, P-numerals, 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, P-numerals, and fold blueArrow
8/31/2002; 4:08:31 AM (reads: 1341, responses: 1)

Symmetric difference in LC, P-numerals, and fold

To compute (diffs ck cl) we convert cl to a list of length l, and then apply a down-or-up operation k times to the list. The down-or-up 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(k-l). 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, P-numerals, and fold blueArrow
9/2/2002; 1:56:34 PM (reads: 542, responses: 0)

I neglected to emphasize the advantage of P-numerals over Church numerals: the simplicity of finding a predecessor. Given a lazy order of evaluation, finding a predecessor of a P-numeral 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!