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

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

data-structures lambda-calculus integers real-numbers zcaudate
источник

Ответы:

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

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

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)

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

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

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

Андрей Бауэр
источник

Вау =) Мне интуитивно интересно, что это значит ... например, используя кодировку церковных чисел ... т.е. Церковное число целого числа n представлено функцией, которая применяет функцию к значению n раз. Имеют ли пары и отрицательные значения лямбда такое же интуитивное чувство к ним?

zcaudate

Кодировка Черча кодирует натуральные числа

, ... Не кодирует отрицательные числа. В ответе выше я предположил, что вы уже знаете о кодировании натуральных чисел, поэтому я объяснил, как получить целые числа. Целые числа, как я их кодировал, представляют собой более формальную конструкцию, в отличие от церковных цифр, которые более сложно связаны с

калькуляцией. Я не думаю, что «отрицательные значения лямбда» - это осмысленная фраза.

0

$0$

1

$1$

2

$2$

λ

$\lambda$

Андрей Бауэр

@zcaudate [Тип аннотация: i:ℤ, x:a, f,u,s:a→a, p:(a→a,a→a)] Если вы закодировать ℤ , как (Sign,ℕ)то, учитывая пар функций , (s,f)как pэтот термин λi.λp.λx.(fst i) (fst p) id ((snd i) (snd p) x)будет производить либо f(…f(x)…)или s(f(…f(x)…))(если результат отрицательный). Если вы закодируете ℤ как (ℕ,ℕ), вам нужна функция, которая имеет обратное значение - заданная пара (f,u)и x, функция λi.λp.λx.(snd i)(snd p)((fst i)(fst p) x)выдаст, u(…u(f(…f(x)…))…)что оставит fприложенное iвремя до x. Оба работают в разных контекстах (результат может быть «перевернут» || fявляется обратимым).

никто не

@zcaudate Дополнительные функции необходимы, так как числа, закодированные Церковью, "рекурсивно", но пары передадут вам только свои компоненты. Вспомогательные функции просто склеивают компоненты в «правильном» порядке (что происходит автоматически для nats). См. Также: en.wikipedia.org/wiki/… - Кодировка Church в основном fold . ctorдля любого конструктора и этого типа fold( r). (Именно поэтому, для рекурсивных типов, данные будут «рекурсия на своем» Для не рекурсивных типов это больше похожи. case/ Матч шаблона.)

никто не

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

пара знак равно λ Икс Y Z, Z Икс Y

$\mbox{pair}= λxyz.zxy$

FST знак равно λ п, п (λ Икс Y, Икс)

$\mbox{fst} = λp.p(λxy.x)$

SND знак равно λ п, п (λ Икс Y, Y)

$\mbox{snd} = λp.p(λxy.y)$

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

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

(s i g n, N)

$(sign,n)$

$\mbox{xor}$

{мульт}_{ℤ} знак равно λ a б, пара (исключающее (FST a) (FST б)) ({мульт}_{ℕ} (snd a) (snd b))

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

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

{add}_{ℤ} = λ a b . {\begin{cases} (true, {add}_{ℕ} (snd a) (snd b)) & if a \geq 0 \land b \geq 0 \\ (false, {add}_{ℕ} (snd a) (snd b)) & if a < 0 \land b < 0 \\ (true, {sub}_{ℕ} (snd a) (snd b)) & if a \geq 0 \land b < 0 \land | a | \geq | b | \\ (false, {sub}_{ℕ} (snd b) (snd a)) & if a \geq 0 \land b < 0 \land | a | < | b | \\ (true, {sub}_{ℕ} (snd b) (snd a)) & if a < 0 \land b \geq 0 \land | a | < | b | \\ (false, {sub}_{ℕ} (snd a) (snd b)) & if a < 0 \land b \geq 0 \land | a | \geq | b | \end{cases}

$\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|<|b| \\ (\mbox{true},\mbox{sub}_ℕ(\mbox{snd }b)(\mbox{snd }a)) & \mbox{if } a<0∧b≥0∧|a|<|b| \\ (\mbox{false},\mbox{sub}_ℕ(\mbox{snd }a)(\mbox{snd }b)) & \mbox{if } a<0∧b≥0∧|a|≥|b| \\ \end{array}\right.$

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

{minus}_{ℤ} = λ a . pair (not (fst a)) (snd a)

$\mbox{minus}_ℤ=λa.\mbox{pair}(\mbox{not}(\mbox{fst } a))(\mbox{snd } a)$

{sub}_{ℤ} = λ a b . {add}_{ℤ} (a) ({minus}_{ℤ} b)

$\mbox{sub}_ℤ=λab.\mbox{add}_ℤ(a)(\mbox{minus}_ℤb)$

$(a,b)$ $a+b\mbox{i}$

{add}_{ℤ [i]} = λ z_{1} z_{2} . pair ({add}_{ℤ} (fst z_{1}) (fst z_{2})) ({add}_{ℤ} (snd z_{1}) (snd z_{2}))

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

jmad
источник

k

$k$

(a, b)

$(a,b)$

k = a - b

$k = a - b$

Сложные целые числа хорошо, но он просил комплексные числа. Опять же, они, конечно, никогда не могут быть представлены, так как существуют бесчисленные.

HDM

@AndrejBauer: очень хороший трюк (возможно, не такой простой) HdM: конечно, могут, даже не во всех. Но я подумал, что метод построения материала в λ-исчислении с церковным кодированием был более важным / уместным здесь.

Джмад

Хотел бы я дать два правильных ответа =) Я даже не думал, что можно представить реалы, когда я спрашиваю о комплексных числах, но вот, пожалуйста!

zcaudate