Subtração da Igreja

O cálculo lambda sempre foi um fascínio meu e os comportamentos emergentes de passar funções entre si são deliciosamente complexos. Os numerais da igreja são representações de números naturais calculados a partir da aplicação repetida de uma função (normalmente a adição unária de uma constante). Por exemplo, o número zero retorna x e "ignora" a função de entrada, um é f(x), dois é f(f(x))e assim por diante:

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

A partir disso, podemos ver facilmente que a adição é realizada aplicando a primeira função em x e aplicando a segunda função em x:

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

A adição é relativamente fácil de entender. No entanto, para um recém-chegado, pode ser inconcebível pensar em como é a subtração em um sistema numérico codificado pela Igreja. O que poderia significar não aplicar uma função?

Desafio

Implemente a função de subtração em um sistema numérico codificado pela Igreja. Onde a subtração executa a operação monus e aplica uma função nvezes se o resultado for maior que zero ou zero, caso contrário. Este é o código-golfe, pelo que o código mais curto vence.

Entrada

Dois números da igreja que foram codificados na sua escolha de idioma. A entrada pode ser posicional ou com curry. Para provar estes são verdadeiros números da Igreja que terá que tomar em qualquer função e aplicá-los repetidamente ( add1é dado nos exemplos, mas poderia ser add25, mult7ou qualquer outra função unário.)

Resultado

Um numeral da igreja. Deve-se notar que se m < nentão m - né sempre o mesmo que a função de identidade.

Exemplos:

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

também aceitável:

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

Crédito:

Esta essência do github por me dar uma implementação em python dos numerais da igreja.

Haskell , 35 bytes

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

Experimente online!

Diga isso re ssão as codificações da igreja de me n. Queremos r%saplicar f m-ntempos a algum valor inicial x. Primeiro, geramos a lista infinita

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

use s(x:)para anexar ncópias de x, ou seja, desloque cada níndice de valor para a direita:

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

Em seguida, calculamos mdiretamente como r(+1)0e tomamos o m'th elemento dessa lista como !!r(+1)0. Uma solução livre de indexação poderia fazer head$r tail$...isso, ou seja, eliminar o primeiro elemento mvezes e pegar o primeiro elemento, mas a sintaxe da indexação é muito mais curta.

Observe que a solução clássica não funciona no Haskell sem extensões, porque sua digitação forte não pode representar a operação predecessora.

Python 2 , 82 80 bytes

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

Experimente online!

2 bytes thx para Nick Kennedy, observando um par de pares desnecessário.

Função anônima que implementa menos.

Principalmente isso está apenas comprimindo a definição encontrada na página da Wikipedia; não é como se eu realmente entendesse o código ainda. Mas interessante!

Python 2 , 77 bytes

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

Experimente online!

Fazemos decremento da Igreja rastreando o valor anterior para cada iteração e exibindo esse valor no final. 39% do comprimento do código é "lambda"...

C ++ (clang) , 112 bytes

#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)));

Experimente online!

Este é de longe o código C ++ mais incompreensível que já escrevi. Dito isto, acho que desmascarar esse código só o tornará pior.

Subcarga , 37 bytes

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

Experimente online!

O interno (((!())~):*^(~!:(:)~*(*)*)~^^!)é a predfunção, implementada via pares:

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

R , 86 bytes

eval(parse(t=gsub("!(.)","function(\\1)","!u!vv(!n!f!xn(!g!hh(g(f)))(!ux)(!uu))(u)")))

Experimente online!

A porta R da resposta Python do @ ChasBrown, portanto, certifique-se de votar também.

JavaScript (Node.js) , 87 85 81 76 74 bytes

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

Experimente online! Não vou ganhar nenhum prêmio, mas pensei em tentar uma abordagem diferente.

a=>[h,a]é um estágio que se aplica h, enquanto a=>[x=>x,a]é um estágio que não se aplica h. Aplicamos os primeiros ftempos de função e os segundos de função g. Em seguida, aplicamos os ([f,[g,a]])=>[g(x),a] ftempos de função inversa . Isso pula os gsegundos estágios e executa os f-gprimeiros, conforme desejado. Resta então extrair o valor final.

Obviamente, as tuplas podem ser convertidas em funções lambda, o que resulta na seguinte expressão:

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)

J , 56 bytes

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

Experimente online!

Nota: -3 bytes fora da contagem TIO param=.

Funções de ordem superior em J são alcançadas usando advérbios e conjunções. Aqui, o numeral da igreja é a forma gerúndio do advérbio formada pela combinação do "poder da" conjunção (que aplica repetidamente um verbo) e um número inteiro. O verbo a seguir c(para "create") usa a representação atômica de J para transformar um número inteiro em um gerúndio:

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

Nosso operador "menos" (que é uma conjunção) subtrai o número da igreja do gerúndio direito da esquerda. Entretanto, ele não assume nenhuma implementação específica de numerais da igreja, incluindo a do nosso cverbo. Em vez disso, ele se baseia na definição geral e transforma cada numeral de igreja gerúndio novamente em um advérbio, invertendo-o com 5!:0e, em seguida, aplicando esse advérbio ao verbo de incremento >:e, em seguida, aplicando- o a 0.

Em seguida, subtrai e obtém o máximo com 0 e aplica c- se para obter o resultado final: um novo numeral de igreja gerúndio.

Wolfram Language (Mathematica) , 55 48 47 39 bytes (33 caracteres)

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

Experimente online!

O símbolo is é 0xF4A1, um ponto de código especial do Mathematica que indica uma seta para a direita \[Function]. Veja aqui para mais explicações. É assim que o código se parece no front end do Mathematica:

Podemos fazê-lo em 40 bytes / 32 caracteres , que podem ser mais curtos dependendo do esquema de medição:#2[n⟼f⟼x⟼n[g⟼#@g@f&][x&][#&]]@#&

A versão sem golfe é uma tradução literal da definição clássica de 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]

que se parece com isso no front end do Mathematica:

Esta função de subtração trabalha com os números da Igreja definidos com

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

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

para que tenhamos

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]]]]]]}    *)

e

subtract[c[7],c[5]][f][x]
(*    f[f[x]]    *)