Sustracción de la iglesia

13

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.

Ryan Schaefer
fuente
1
(El comentario en la esencia es incorrecto; exp(m, n)calcula, m^npor supuesto.)
Neil
1
No estoy seguro de lo que quiere decir que "la entrada puede ser posicional o curry". ¿Está bien definir la función principal como lambda m,n,f:apply f m-n times(o incluso lambda m,n,f,x:apply f m-n times to x) en lugar de lambda m,n:lambda f:...? ¿O esto solo se aplica a las dos entradas my n?
xnor
Además, ¿podemos tomar los argumentos my nen el otro orden? Esto ayudaría con el curry.
xnor
@xnor siempre que pueda probar que resta dos números de iglesia y luego puede tomar las entradas de la forma que desee.
Ryan Schaefer

Respuestas:

9

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.

xnor
fuente
3

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!

Chas Brown
fuente
Según la esencia del OP mencionado, !u:!v:v(!n:!f:!x:n(!g:!h:h(g(f)))(!y:x)(!x:x))(u)parece ahorrar 2 bytes, ¡pero realmente no entiendo el código!
Nick Kennedy el
@NickKennedy gettingsharper.de/2012/08/30/… si está interesado
Ryan Schaefer el
@ Ryan Schaefer: ¡Buen "truco"!
Chas Brown el
3

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"...

xnor
fuente
¡bonito! Estaba esperando una respuesta de Python golfizada que no solo mirara la implementación de lo esencial. ¿Has pensado en usar eval como la otra respuesta para seguir jugando golf?
Ryan Schaefer
@RyanSchaefer Verifiqué evaluar / reemplazar cuando vi la otra respuesta, pero en realidad son 2 bytes más aquí con 5 lambdas para reemplazar. Desafortunadamente, Python es muy prolífico tanto en la definición de funciones como en la manipulación de cadenas. Y carece de una "composición" incorporada, lo que ahorraría una capa de lambdas.
xnor
2

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á.

G. Sliepen
fuente
2

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 )!
)
Nitrodon
fuente
1

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)
Neil
fuente
1

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.

Jonás
fuente
1

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:

ingrese la descripción de la imagen aquí

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:

ingrese la descripción de la imagen aquí

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]]    *)
romano
fuente