Представление отрицательных и сложных чисел с использованием исчисления лямбды

Question

Большинство учебных пособий по исчислению Lambda приведены пример, где положительные целые числа и логические данные могут быть представлены функциями. А как насчет -1 и я?

Answer 1

Сначала кодируйте натуральные числа и пары, как описано JMAD.

Представляйте целое число $ k $ в качестве пары натуральных чисел $ (a, b) $ так, что $ k = a - b $. Затем вы можете определить обычные операции на целых числах как (используя нотацию Haskell для $ lambda $ -calculus):

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)

Случай сложных чисел похож в том смысле, что сложное число кодируется как пара реальных. Но более сложный вопрос - как кодировать реальные. Здесь вы должны сделать больше работы:

1. Кодируйте рациональный номер $ Q $ в качестве пары $ (k, a) $, где $ k $ - целое число, $ a $ естественно и $ q = k / (1 + a) $.
2. Кодировать реальное число $ x $ функцией $ f $ такой, что для каждого натурального $ k in mathbb {n} $, $ fk $ кодирует рациональное число $ q $ такова, что $ | x - q | <2^{-k} $. Другими словами, реальное кодируется как последовательность рациональных, сходящихся к нему по скорости $ k mapsto 2^{-k} $.

Кодирование реальных-это большая работа, и вы не хотите делать это в $ lambda $ -calculus. Но см., Например, etc/haskell подкаталог Маршалл Для простой реализации реальных в Pure Haskell. Это в принципе может быть переведено на чистый $ lambda $ -calculus.

Answer 2

Lambda-Calculus может кодировать большинство структур данных и основных типов. Например, вы можете кодировать пару существующих терминов в исчислении лямбда, используя то же самое Церковное кодирование что вы обычно видите, чтобы кодировать неотрицательные целые числа и логические:

$$ mbox {pair} = λxyz.zxy $$ $$ mbox {fst} = λp.p (λxy.x) $$ $$ mbox {snd} = λp.p (λxy.y) $$$

Тогда пара $ (a, b) $ is $ p = ( mbox {pair} ab) $, и если вы хотите вернуть $ a $ и $ b $, вы можете сделать $ ( mbox {fst} p) $ и $ ( mbox {snd} p) $.

Это означает, что вы можете легко представлять положительные и отрицательные целые числа с парой: знак слева и абсолютное значение справа. Знаком является логическим, который указал, является ли число положительным. Право - это естественное число, используя кодирование церкви.

$$ (sign, n) $$

И теперь, когда у вас есть относительные целые числа. Умножение легко определить, вам просто нужно применить $ mbox {xor} $ function на знаке и умножение на естественных числах по абсолютному значению:

$$ mbox {mult} _ℤ = λab. mbox {pair} ~~ ( mbox {xor} ( mbox {fst} a) ( mbox {fst} b)) ~~ ( mbox {mult} _ℕ ( mbox {snd} a) ( mbox {snd} b)) $$

Чтобы определить дополнение, вы должны сравнить два естественных числа и использовать вычитание, когда знаки отличаются, так что это не λ-термин, но вы можете адаптировать его, если действительно хотите:

$$ mbox {add} _ℤ = λab. Left { begin {array} {ll} ( mbox {true}, mbox {add} _ℕ ( mbox {snd} a) ( mbox {snd} b)) & mbox {if} a≥0∧b≥0 ( mbox {false}, mbox {add} _ℕ ( mbox {snd} a) ( mbox {snd} b)) & mbox {if} a <0∧b <0 ( mbox {true}, mbox {sub} _ℕ ( mbox {snd} a) ( mbox {snd} b)) и mbox {if} a ≥0∧b <0∧ | a | ≥ | b | ( mbox {false}, mbox {sub} _ℕ ( mbox {snd} b) ( mbox {snd} a)) и mbox {if} a≥0∧b <0∧ | a | < | б | ( mbox {true}, mbox {sub} _ℕ ( mbox {snd} b) ( mbox {snd} a)) и mbox {if} a <0∧b≥0∧ | a | < | б | ( mbox {false}, mbox {sub} _ℕ ( mbox {snd} a) ( mbox {sn} b)) & mbox {if} a <0∧b≥0∧ | a | ≥ | б | end {array} right. $$

Но тогда вычитание действительно легко определить:

$$ mbox {minus} _ℤ = λa. mbox {pair} ( mbox {not} ( mbox {fst} a)) ( mbox {snd} a) $$ $$ mbox {sub} _ℤ = λab. mbox {add} _ℤ (a) ( mbox {minus} _ℤb) $$

Как только у вас есть положительные и отрицательные целые числа, вы можете определить Сложные целые числа Очень легко: это всего лишь пара из двух целых чисел $ (a, b) $, которая представляет $ a+b mbox {i} $. Тогда добавление в точках, а умножение по-прежнему, но я не буду написать это, это должно быть легко:

$$ mbox {add} _ {ℤ [ mbox {i}]} = λz_1z_2. mbox {pare} ( mbox {add} _ℤ ( mbox {fst} z_1) ( mbox {fst} z_2)))) ( mbox {add} _ℤ ( mbox {snd} z_1) ( mbox {snd} z_2)) $$