Вычитание церкви

13

Вычитание церкви

Лямбда-исчисление всегда было моим увлечением, и возникающее поведение передачи функций друг другу восхитительно сложно. Церковные цифры - это представления натуральных чисел, полученные из многократного применения функции (обычно это одинарное сложение константы). Например, нулевое число возвращает x и «игнорирует» входную функцию, one is f(x), two is f(f(x))и так далее:

ident = lambda x: x
zero = lambda f: ident
succ = lambda n: lambda f: lambda x: f(n(f)(x))
one = succ(zero)
add1 = lambda x: x + 1
to_int = lambda f: f(add1)(0)
print(to_int(one))
>>> 1

Из этого легко увидеть, что добавление выполняется путем применения первой функции к x, а затем применения второй функции к x:

add = lambda m: lambda n: lambda f: lambda x: n(f)(m(f)(x))
print(to_int(add(one)(two)))
>>> 3

Дополнение относительно легко понять. Однако для новичка было бы немыслимо подумать о том, как выглядит вычитание в зашифрованной церковной системе счисления. Что это может означать, чтобы не применять функцию?

Вызов

Реализуйте функцию вычитания в системе счисления, закодированной Церковью. Где вычитание выполняет операцию monus и отменяет функцию nраз, если результат будет больше нуля или ноль в противном случае. Это код-гольф, поэтому выигрывает самый короткий код.

вход

Две церковные цифры, которые были закодированы на выбранном вами языке. Ввод может быть позиционным или карри. Для того, чтобы доказать этот являются истинным Чёрчем они должны будут принимать в любой функции и применять их повторно ( add1дано в примерах , но это может быть add25, mult7или любой другая одноместный функция) .

Выход

Церковная цифра. Следует отметить, что если m < nтогда m - nвсегда то же самое, что и функция тождества.

Примеры:

minus(two)(one) = one
minus(one)(two) = zero
...

также приемлемо:

minus(two, one) = one
minus(one, two) = zero

Кредит:

Это GitHub суть для того, чтобы дать мне реализацию Python церковных цифр.

Райан Шефер
источник
1
(Комментарий в сущности неверен; exp(m, n)подсчитывает, m^nконечно.)
Нейл
1
Я не уверен, что вы имеете в виду, что «ввод может быть позиционным или карри». Можно ли определять основную функцию как lambda m,n,f:apply f m-n times(или даже lambda m,n,f,x:apply f m-n times to x) вместо lambda m,n:lambda f:...? Или это относится только к двум входам mи n?
xnor
Кроме того, мы можем принять аргументы mи nв другом порядке? Это поможет с карри.
xnor
@xnor, пока вы можете доказать, что это вычитает две церковные цифры, вы можете принимать входные данные в любое время.
Райан Шефер

Ответы:

9

Haskell , 35 байт

(r%s)f x=s(x:)(iterate f x)!!r(+1)0

Попробуйте онлайн!

Скажи это rи sесть церковные кодировки mи n. Мы хотим r%sприменить f m-nвремена к некоторому начальному значению x. Сначала мы генерируем бесконечный список

iterate f x = [x, f x, f (f x), f (f (f x)), ...]

затем используйте s(x:)для добавления nкопий x, то есть сдвиг каждого nиндекса значения вправо:

s(x:)(iterate f x) = [x, x, x, ...,  x, f x, f (f x), f (f (f x)), ...]

Затем мы вычисляем mнепосредственно как r(+1)0и принимаем mый элемент этого списка как !!r(+1)0. Вместо этого можно было бы использовать решение без индексации head$r tail$..., то есть отбрасывать первый элемент mраз, а затем брать первый элемент, но синтаксис индексации намного короче.

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

XNOR
источник
3

Python 2 , 82 80 байт

eval('!u:!v:v(!n:!f:!x:n(!g:!h:h(g(f)))(!u:x)(!u:u))(u)'.replace('!','lambda '))

Попробуйте онлайн!

2 байта спасибо Нику Кеннеди, отмечая ненужную пару паренов.

Анонимная функция, которая реализует минус.

В основном это просто сжатие определения, найденного на странице Википедии; не так, как я действительно понимаю код еще. Но интересно!

Час Браун
источник
Судя по сути, упомянутый OP, !u:!v:v(!n:!f:!x:n(!g:!h:h(g(f)))(!y:x)(!x:x))(u)похоже, экономит 2 байта, но я не совсем понимаю код!
Ник Кеннеди
@NickKennedy gettingsharper.de/2012/08/30/… если вы заинтересованы
Райан Шефер,
@ Райан Шефер: Хороший "трюк"!
Час Браун
3

Python 2 , 77 байт

lambda r,s:s(lambda r:lambda f:lambda x:r(lambda(_,x):(x,f(x)))((x,x))[0])(r)

Попробуйте онлайн!

Мы делаем церковный декремент, отслеживая предыдущее значение для каждой итерации и выводя его в конце. 39% длины кода это "lambda"...

XNOR
источник
красивый! Я ждал ответа от python в гольфе, который не просто смотрел на суть реализации. Думал ли ты об использовании eval, как о другом ответе, для дальнейшей игры в гольф?
Райан Шефер
@RyanSchaefer Я проверил eval / replace, когда увидел другой ответ, но на самом деле он на 2 байта длиннее с 5 лямбдами для замены. К сожалению, Python действительно многословен как в определении функций, так и в манипулировании строками. И в нем отсутствует встроенная функция «compose», которая бы сохраняла слой лямбд.
xnor
2

C ++ (лязг) , 112 байт

#define L(x,y)[&](auto x){return y;}
auto m=L(u,L(v,v(L(n,L(f,L(x,n(L(g,L(h,h(g(f)))))(L(u,x))(L(u,u))))))(u)));

Попробуйте онлайн!

Это, безусловно, самый непостижимый код C ++, который я когда-либо писал. Тем не менее, я думаю, что разглашение этого кода только ухудшит его.

Г. Слипен
источник
2

Недогрузка , 37 байт

(~(((!())~):*^(~!:(:)~*(*)*)~^^!)~^^)

Попробуйте онлайн!

Внутренняя (((!())~):*^(~!:(:)~*(*)*)~^^!)является predфункция, осуществляемая с помощью пар:

(               ( start pred function )!
  (
    (!())~      ( push zero below argument )!
  ):*^          ( do that twice )!

  (             ( start pair-increasing function )!
    ~!          ( remove second argument)!
    :           ( duplicate first argument )!
    (:)~*(*)*   ( increment first return value )!
  )
  ~^^           ( run pair-increasing function n times )
  !             ( remove first in returned pair )!
)
Nitrodon
источник
1

JavaScript (Node.js) , 87 85 81 76 74 байта

f=>g=>h=>x=>f(([x,[g,a]])=>[g(x),a])([x,g(a=>[x=>x,a])(f(a=>[h,a])())])[0]

Попробуйте онлайн! Не собираюсь выигрывать никаких наград, но я решил попробовать другой подход.

a=>[h,a]это этап, который применяется h, в то время a=>[x=>x,a]как это этап, который не применяется h. Мы применяем первый fраз функции и второй gраз функции . Затем мы применяем обратную функцию ([f,[g,a]])=>[g(x),a] fвремени. Это пропускает gвторые этапы и выполняет f-gпервые этапы по желанию. Затем остается извлечь окончательное значение.

Конечно, кортежи могут быть преобразованы в лямбда-функции, что приводит к следующему выражению:

f=>g=>h=>x=>f(e=>e(x=>d=>d(g=>a=>e=>e(g(x))(a))))(e=>e(x)(g(a=>e=>e(x=>x)(a))(f(a=>e=>e(h)(a))())))(x=>a=>x)
Нил
источник
1

J , 56 байт

c=:3 :0
t=.^:y
5!:1<'t'
)
m=.2 :'c 0>.(>:u 5!:0->:v 5!:0)0'

Попробуйте онлайн!

Примечание: -3 байта от счета TIO дляm=.

Функции высшего порядка в J достигаются с помощью наречий и союзов. Здесь церковное число - это герундовая форма наречий, образованного сочетанием «силы» соединения (которое многократно применяет глагол) и целого числа. Следующий глагол c(для «создания») использует атомарное представление J, чтобы преобразовать целое число в такой герундий:

c=:3 :0
t=.^:y
5!:1<'t'
)

Наш оператор «минус» (который является конъюнкцией) вычитает правую цифру церковного герунда слева. Однако он не предполагает какой-либо конкретной реализации церковных цифр, в том числе из нашего cглагола. Вместо этого он полагается на общем определении и превращает каждую герундий Чёрч обратно в наречие, переворачивая его 5!:0, а затем применять эти наречия с глаголом приращения >:, а затем применяя , что 0.

Затем он вычитает и принимает максимум с 0 и применяется cдля получения окончательного результата: новой церковной цифры герунды.

Ион
источник
1

Wolfram Language (Mathematica) , 55 48 47 39 байт (33 символа)

#2[(fx#[g#@g@f&][x&][#&])&]@#&

Попробуйте онлайн!

Символ is - это 0xF4A1, специальная кодовая точка Mathematica, обозначающая стрелку вправо \[Function]. Смотрите здесь для большего количества объяснений. Вот как выглядит код в интерфейсе Mathematica:

введите описание изображения здесь

Мы можем сделать это в 40 байтах / 32 символа , которые могут быть короче в зависимости от схемы измерения:#2[n⟼f⟼x⟼n[g⟼#@g@f&][x&][#&]]@#&

Версия без гольфа - буквальный перевод классического определения pred :

pred = n \[Function] f \[Function] x \[Function] n[g \[Function] h \[Function] h[g[f]]][u \[Function] x][u \[Function] u];
subtract[m_, n_] := n[pred][m]

который выглядит так в интерфейсе Mathematica:

введите описание изображения здесь

Эта функция вычитания работает с церковными цифрами, определенными с

c@0=#& &;c@n_=#@*c[n-1][#]&

(ип-golfed: c[0] = Identity &; c[n_] = Function[a, a@*c[n-1][a]])

так что у нас есть

Table[c[n][f][x], {n, 0, 6}]
(*    {x, f[x], f[f[x]], f[f[f[x]]], f[f[f[f[x]]]], f[f[f[f[f[x]]]]], f[f[f[f[f[f[x]]]]]]}    *)

и

subtract[c[7],c[5]][f][x]
(*    f[f[x]]    *)
Роман
источник