Rappresentare negativi e complessi numeri utilizzando Lambda Calcolo

Question

La maggior parte dei tutorial su Lambda Calcolo fornire esempio in cui interi positivi e booleane possono essere rappresentati da funzioni. Che dire di -1 e io?

Answer 1

Prima codificare numeri naturali e le coppie, come descritto da jmad.

rappresentano un intero $ k $ come una coppia di numeri naturali $ (a, b) $ tali che $ k = a - b $. Quindi è possibile definire le consuete operazioni su interi come (usando la notazione Haskell a $ \ lambda $ -calcolo):

neg = \k -> (snd k, fst k)
add = \k m -> (fst k + fst m, snd k + snd m)
sub = \k m -> add k (neg m)
mul = \k m -> (fst k * fst m + snd k * snd m, fst k * snd m + snd k * fst m)

Il caso dei numeri complessi è simile, nel senso che un numero complesso è codificato come una coppia di numeri reali. Ma una domanda più complicata è come codificare reali. Qui si ha a che fare più lavoro:

1. codificare un razionale numero $ q $ in coppia $ (k, a) $ dove $ k $ è un numero intero, $ a $ è naturale, e $ q = k / (1 + a) $.
2. Codifica un numero reale $ x $ da una funzione $ f $ tale che per ogni $ naturale k \ in \ mathbb {N} $, $ f k $ codifica una razionale numero di $ q $ tale che $ | x - q | <2 ^ {- k} $. In altre parole, una vera e propria è codificato come una sequenza di numeri razionali che convergono ad esso al tasso di $ k \ mapsto 2 ^ {-} k. $

Codifica reali è un sacco di lavoro e non si vuole fare in realtà nel $ \ lambda $ -calcolo. Ma vedi ad esempio la sottodirectory etc/haskell di Marshall per una semplice implementazione di reali in puro Haskell. Questo potrebbe in linea di principio essere tradotto al $ pura \ lambda $ -calcolo.

Answer 2

Lambda-calcolo possono codificare la maggior parte delle strutture di dati e tipi di base. Ad esempio, è possibile codificare un paio di termini esistenti nel lambda calcolo, utilizzando lo stesso Church codifica che di solito si vede per codificare interi non negativi e booleana:

$$ \ mbox {} = coppia ?xyz.zxy $$ $$ \ mbox {} FST = ?p.p (?xy.x) $$ $$ \ mbox {} = snd ?p.p (?xy.y) $$

Poi la coppia $ (a, b) $ è $ p = (\ mbox {paio} ab) $ e se si vuole tornare $ a $ e $ b $ si può fare $ (\ mbox {FST} p) $ e $ (\ mbox {} p snd) $.

Ciò significa che si può facilmente rappresentare numeri interi positivi e negativi con un paio: il segno sulla sinistra e il valore assoluto sulla destra. Il segno è essere un valore booleano che specifica se il numero è positivo. Il diritto è un numero naturale usando la codifica Chiesa.

$$ (segno, n) $$

E ora che si dispone di numeri interi relativi. La moltiplicazione è facile da definire, è sufficiente applicare la $ \ mbox {xor} $ funzione sul segno e il moltiplicazione numeri naturali sul valore assoluto:

$$ \ mbox {} mult _Z = ?ab. \ Mbox {} coppia ~~ (\ mbox {xor} (\ mbox {} FST a) (\ mbox {} FST b)) ~~ (\ mbox {} mult _N (\ mbox {} snd a) (\ mbox {} snd b)) $$

Per definire l'aggiunta, si deve confrontare due numeri naturali e l'uso di sottrazione quando i segni sono diversi, quindi questo non è un ?-termine, ma è possibile adattare se si vuole veramente:

$$ \ mbox {} add _Z = ?ab. \ Left \ {\ begin {array} {} ll (\ Mbox {true}, \ mbox {} add _N (\ mbox {} snd a) (\ mbox {} snd b)) & \ mbox {if} a=0?b=0 \\ (\ Mbox {false}, \ mbox {} add _N (\ mbox {} snd a) (\ mbox {} snd b)) & \ mbox {} se un <0?b <0 \\ (\ Mbox {true}, \ mbox {} sub _N (\ mbox {} snd a) (\ mbox {} snd b)) & \ mbox {if} a=0?b <0? | un | = | b | \\ (\ Mbox {false}, \ mbox {} sub _N (\ mbox {} snd b) (\ mbox {} snd a)) & \ mbox {if} a=0?b <0? | un | <| b | \\ (\ Mbox {true}, \ mbox {} sub _N (\ mbox {} snd b) (\ mbox {} snd a)) & \ mbox {} se un <0?b=0? | un | <| b | \\ (\ Mbox {false}, \ mbox {} sub _N (\ mbox {} snd a) (\ mbox {} snd b)) & \ mbox {} se un <0?b=0? | un | = | b | \\ \ End {array} \ right. $$

ma poi sottrazione è veramente facile da definire:

$$ \ mbox {} meno _Z = ?a. \ Mbox {} coppia (\ mbox {non} (\ mbox {} FST a)) (\ mbox {} snd a) $$ $$ \ mbox {} sub _Z = ?ab. \ Mbox {} add _Z (a) (\ mbox {} meno _Zb) $$

Una volta che avete i numeri interi positivi e negativi è possibile definire interi complessi molto facilmente: si tratta solo di un paio di due numeri interi $ (a, b) $, che rappresenta $ a + b \ mbox {i} $. Poi aggiunta è puntiforme e moltiplicazione è come al solito , ma non scriverlo, dovrebbe essere facile :

$$ \ mbox {} add _ {Z [\ mbox {i}]} = ?z_1z_2. \ Mbox {} coppia (\ Mbox {} add _Z (\ mbox {} FST z_1) (\ mbox {} FST Z_2)) (\ Mbox {} add _Z (\ mbox {} snd z_1) (\ mbox {} snd Z_2)) $$