Sustracción de la iglesia

El cálculo de Lambda siempre ha sido una fascinación mía y los comportamientos emergentes de pasar funciones entre sí son deliciosamente complejos. Los números de iglesia son representaciones de números naturales construidos a partir de la aplicación repetida de una función (normalmente la suma unaria de una constante). Por ejemplo, el número cero devuelve x e "ignora" la función de entrada, uno es f(x), dos es f(f(x))y así sucesivamente:

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 de esto, podemos ver fácilmente que la suma se logra aplicando la primera función a x y luego aplicando la segunda función a x:

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

La suma es relativamente fácil de entender. Sin embargo, para un recién llegado, podría ser inconcebible pensar en cómo se ve la resta en un sistema numérico codificado de la Iglesia. ¿Qué podría significar desaplicar una función?

Desafío

Implemente la función de resta en un sistema de numeración codificado de Church. Donde la resta realiza la operación monus y no aplica una función nveces si el resultado será mayor que cero o cero de lo contrario. Este es el código de golf, por lo que gana el código más corto.

Entrada

Dos números de la Iglesia que han sido codificados en su idioma de elección. La entrada puede ser posicional o curry. Para probar estos son los verdaderos números de la Iglesia que se tienen que tomar en cualquier función y aplicarlos varias veces ( add1se da en los ejemplos pero podría ser add25, mult7o cualquier otra función unaria.)

Salida

Un número de iglesia. Cabe señalar que si m < na continuación, m - nsiempre es la misma que la función identidad.

Ejemplos:

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

también aceptable:

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

Crédito:

Este github gist por darme una implementación en Python de los números de la iglesia.

Haskell , 35 bytes

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

Pruébalo en línea!

Diga eso ry sson las codificaciones de la iglesia de my n. Queremos r%saplicar f m-ntiempos a algún valor inicial x. Primero generamos la lista infinita

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

luego use s(x:)para anteponer ncopias de x, es decir, desplazar cada níndice de valores a la derecha

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

Luego calculamos mdirectamente como r(+1)0y tomamos el melemento 'th de esa lista como !!r(+1)0. En cambio, una solución libre de indexación podría funcionar head$r tail$..., es decir, soltar el primer elemento mveces y luego tomar el primer elemento, pero la sintaxis de indexación es mucho más corta.

Tenga en cuenta que la solución clásica no funciona en Haskell sin extensiones porque su tipeo fuerte no puede representar la operación predecesora.

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 '))

Pruébalo en línea!

2 bytes gracias a Nick Kennedy señalando un par de padres innecesarios.

Función anónima que implementa menos.

Principalmente, esto solo está comprimiendo la definición que se encuentra en la página de Wikipedia; no como si realmente entendiera el código todavía. Pero interesante!

Python 2 , 77 bytes

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

Pruébalo en línea!

Hacemos decremento de la Iglesia al rastrear el valor anterior para cada iteración y generarlo al final. El 39% de la longitud del código es "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)));

Pruébalo en línea!

Este es, con mucho, el código C ++ más incomprensible que he escrito. Dicho esto, creo que quitar el código a este código solo lo empeorará.

Baja carga , 37 bytes

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

Pruébalo en línea!

El interno (((!())~):*^(~!:(:)~*(*)*)~^^!)es la predfunción, implementada a través de 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)")))

Pruébalo en línea!

Puerto R de la respuesta de Python de @ ChasBrown, así que asegúrese de votar ese también.

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]

Pruébalo en línea! No voy a ganar ningún premio, pero pensé que probaría un enfoque diferente.

a=>[h,a]es una etapa que se aplica h, mientras que a=>[x=>x,a]es una etapa que no se aplica h. Aplicamos los ftiempos de la primera función y los tiempos de la segunda función g. Luego aplicamos los ([f,[g,a]])=>[g(x),a] ftiempos de la función inversa . Esto omite las gsegundas etapas y realiza las f-gprimeras etapas según lo deseado. Luego queda extraer el valor final.

Por supuesto, las tuplas se pueden convertir en funciones lambda, lo que da como resultado la siguiente expresión:

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'

Pruébalo en línea!

Nota: -3 bytes de recuento de TIO param=.

Las funciones de orden superior en J se logran usando adverbios y conjunciones. Aquí, un número de iglesia es la forma gerundia del adverbio formado al combinar la conjunción "poder de" (que aplica repetidamente un verbo) y un entero. El siguiente verbo c(para "crear") usa la representación atómica de J para transformar un número entero en un gerundio:

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

Nuestro operador "menos" (que es una conjunción) resta el número de iglesia gerundio derecho del izquierdo. Sin embargo, no asume ninguna implementación particular de los números de la iglesia, incluido el de nuestro cverbo. En su lugar, se basa en la definición general y se vuelve cada vuelta el numeral iglesia gerundio en un adverbio invirtiendo con 5!:0, y se puede aplicar dicho adverbio al verbo de la subasta >:, y luego aplicar que a 0.

Luego resta y toma el máximo con 0, y aplica cpara obtener el resultado final: un nuevo número de iglesia gerundio.

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

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

Pruébalo en línea!

El símbolo  es 0xF4A1, un punto de código especial de Mathematica que denota una flecha hacia la derecha para \[Function]. Ver aquí para más explicaciones. Así es como se ve el código en el front-end de Mathematica:

Podemos hacerlo en 40 bytes / 32 caracteres , que pueden ser más cortos dependiendo del esquema de medición:#2[n⟼f⟼x⟼n[g⟼#@g@f&][x&][#&]]@#&

La versión sin golf es una traducción literal de la definición clásica 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 ve así en el front-end de Mathematica:

Esta función de resta funciona con los números de la Iglesia definidos con

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

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

para que tengamos

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

y

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