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