# Lambda the Ultimate

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