Reto
Encuentre una expresión, como máximo de 100 bytes de longitud, con la firma de tipo más larga.
Reglas
- Se permite cualquier idioma escrito estáticamente con inferencia de tipos.
- El tipo no debe ser ambiguo, pero de lo contrario puede incluir tipos sin instancias definidas. Por ejemplo
Num [a]
yEq [a]
están permitidos, incluso sin una instancia definida - No hay importaciones aparte del mínimo requerido para compilar un programa con STDIN / STDOUT
- No se permiten tipos infinitos.
- Si una respuesta tiene más de una expresión, solo una puede contribuir a la puntuación. Por ejemplo, aunque la firma tipo de composición es
(.) :: (b -> c) -> (a -> b) -> a -> c
, con una puntuación de 20, la respuesta con 25 copias(.)\n
tendría una puntuación de 20, no 500 - La expresión debe ser, como máximo, 100 bytes.
- La puntuación es el número de caracteres en la firma de tipo, excluyendo el nombre de la función y cualquier espacio en blanco. Por ejemplo,
f :: (a -> b) -> a -> b
tendría una puntuación de 12 - ¡El puntaje más alto gana!
Ejemplos
Aunque se permiten otros idiomas, los siguientes ejemplos están en Haskell:
Score: 112
map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map.map
f :: (a -> b)
-> [[[[[[[[[[[[[[[[[[[[[[[[[a]]]]]]]]]]]]]]]]]]]]]]]]]
-> [[[[[[[[[[[[[[[[[[[[[[[[[b]]]]]]]]]]]]]]]]]]]]]]]]]
Score: 240
(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.).(.)
f :: (b->c)->(a->a1->a2->a3->a4->a5->a6->a7->a8->a9->a10->a11->a12->a13->a14->a15->a16->a17->a18->a19->a20->a21->a22->a23->a24->b)->a1->a2->a3->a4->a5->a6->a7->a8->a9->a10->a11->a12->a13->a14->a15->a16->a17->a18->a19->a20->a21->a22->a23->a24->c
Score: 313
foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl$foldl(.)
f :: (Foldable t, Foldable t1, Foldable t2, Foldable t3, Foldable t4,
Foldable t5, Foldable t6, Foldable t7, Foldable t8, Foldable t9,
Foldable t10, Foldable t11, Foldable t12, Foldable t13,
Foldable t14, Foldable t15) =>
(b -> c)
-> t (t1 (t2 (t3 (t4 (t5 (t6 (t7 (t8 (t9 (t10 (t11 (t12 (t13 (t14 (t15 (b
-> b))))))))))))))))
-> b
-> c
Score: 538
lex.show.foldl1.mapM.traverse.sum.mapM.sum.traverse.(.).mapM.scanl.zipWith3((.traverse).(.traverse))
(Num
(a -> ([[c]] -> t3 [[a1 -> f b]]) -> [[c]] -> t3 [[a1 -> f b]]),
Num
(([[c]] -> t3 [[a1 -> f b]])
-> t1 (t2 ([[c]] -> t3 [[a1 -> f b]]))
-> [[c]]
-> t3 [[a1 -> f b]]),
Show
(t (t1 (t2 ([[c]] -> t3 [[a1 -> f b]])))
-> t1 (t2 ([[c]] -> t3 [[a1 -> f b]]))),
Applicative f, Foldable t,
Foldable ((->) (t1 (t2 ([[c]] -> t3 [[a1 -> f b]])) -> a)),
Foldable
((->) (([[c]] -> t3 [[a1 -> f b]]) -> a -> t3 [a1 -> f b])),
Traversable t1, Traversable t2, Traversable t3, Traversable t4,
Traversable t5,
Traversable ((->) (t1 (t2 ([[c]] -> t3 [[a1 -> f b]])))),
Traversable ((->) ([[c]] -> t3 [[a1 -> f b]]))) =>
[(t5 (t4 a1) -> f (t5 (t4 b))) -> c -> a1 -> f b]
-> [(String, String)]
code-challenge
busy-beaver
functional-programming
Michael Klein
fuente
fuente
Respuestas:
Haskell, ~ 2 ^ (2 ^ 18)
Cada aplicación de
f
aproximadamente el doble de la firma de tipo transformando la firma de tipoT
a(T,T)
. Por ejemplo, la composición cuádruplef.f.f.f$0
tiene tipoCada línea cuadruplica el número de aplicaciones de
f
, dando4^9 = 2^18
al final. Entonces, la firma de tipo tiene un tamaño del orden de2^(2^18)
.fuente
f x=(x,x,x)
al costo de unon.
en la última línea da el puntaje óptimo para esta estructura general.n.
va a ser más grande.2^18
vs a3 * (2^16)
menos que haya cometido un error al calcular la exponenciación original:2^(4^9)
vs.3^((4^8)*3)
(,)
(o(,,)
) se puede usar para guardar algunos bytes y mejorar la puntuación usando másn
s.Java, puntaje 17301488
Requiere el método
<T>java.util.Map<T,T>f(T t){return null;}
, que se ha contado para el límite de 100 bytes.f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(1)))))))))))))))))))
La firma de tipo de tiempo de compilación de esto debería coincidir con esto.
fuente
Haskell con extensiones,⋙A(A(A(A(220,0),0),0),0)
Pruébalo en línea!
Requiere
-XDataKinds
,-XPolyKinds
,-XTypeOperators
,-XUndecidableInstances
, y-XTypeFamilies
.Muchas gracias a Ørjan Johansen, quien se dio cuenta de que hacer que el constructor de números naturales se infija y construir los argumentos de manera un poco diferente ahorró dos bytes, dejando suficiente espacio para otra iteración de
#
.Obviamente, el verificador de tipos dejará de intentar verificar este programa. Para tener una idea general de cómo se vería la firma (si fuera lo suficientemente pequeña como para caber en el universo observable), pruebe el más pequeño
Explicación
LaUNA , pero
#
familia tipográfica está estrechamente relacionada con la función Ackermann – Péter , comúnmente escrita como#
crece considerablemente más rápido. Se define la función Ackermann – Péter.#
, por otro lado, podemos llamar aSolo el segundo caso es diferente. La prueba de terminación es idéntica a la estándar paraA , y debe quedar claro que B(m,n)≥A(m,n) para todo m y n .
Aquí calculamos una representación unaria de
Por cálculo directo,B(B(B(B(0,0),0),0),0)=220 , entonces
Tenga en cuenta queA ( A ( A ( A ( 0 , 0 ) , 0 ) , 0 ) , 0 ) es solo 5 5 , por lo que hemos mejorado un poco para comenzar. No tengo una idea muy clara de cuánto más rápido crece si que UNA , pero teniendo en cuenta cómo procede el cálculo, es probable que crezca mucho más rápido.
El número de dígitos incluso enA ( 6 , 0 ) es demasiado grande para expresarse prácticamente en decimal, así que esto es ... bastante ridículamente grande.
La definición de los números naturales
(?)
, es un poco no estándar. Para ahorrar espacio, utilizamos(?)
tanto un tipo de número natural (en el nivel de tipo) como un tipo de proxy (en el nivel de término).Creo que uno
TypeFamilies
o (de manera más vergonzosa y ofuscada)FunctionalDependencies
son necesarios para obtener el cálculo de nivel de tipo requerido para alcanzar tipos realmente grandes.UndecidableInstances
es necesario para evitar la comprobación de terminación muy primitiva de Haskell. Las otras extensiones solo son necesarias para comprimir el código en el pequeño espacio disponible.fuente
#Z
Z
s en la parte delantera mejor que comenzarS(S Z)#S Z
, o lo mismo?#Z
al final es bienvenido.?
otro, deja espacio para el extra#Z
.A(m,1)
nunca era más grandeA(A(m,0),0)
y estaba a punto de comentarlo, pero luego se optimizó hasta el punto en que las opciones eran iguales. (Tambiénm+1
nunca es más grande queA(m,0)
.)Haskell, 9 · 2 663552 - 3 (≈ 1.02 · 10 199750 )
Una mejora pequeña ("pequeña") sobre los 5⋅2 262144 + 5 de xnor . Esto es 99 bytes.
Cómo funciona
Tenemos
y así sucesivamente, con una longitud que se duplica aproximadamente para cada uno
(:)
. La expresión dadao.o.o
funciona(:).(:).(:).….(:)
con 2 · 4 6 · 3 4 = 663552 copias de(:)
.Haskell con
FlexibleContexts
yNoMonomorphismRestriction
, (200 · 4 331776 + 75 · 331776 + 16) / 9 ≈ 2.53 · 10 199750Una pequeña mejora con respecto a Bubbler's 12 · 2 663552 + 9 · 663552 - 4 ≈ 1.36 · 10 199750 , que también se basa en estas extensiones. La redacción del desafío sugiere que podría estar bien confiar en ellos ("Por ejemplo,
Num [a]
yEq [a]
están permitidos, incluso sin una instancia definida"); No estoy seguro. Esto es 100 bytes.Cómo funciona
Tenemos
y así sucesivamente, con la longitud aproximadamente cuadruplicando para cada uno
(/).(:)
. La expresión dada-o.o.o
funciona-(/).(:).(/).(:).….(/).(:)
con 4 6 · 3 4 = 331776 copias de(/).(:)
.fuente
Haskell, 12 · 2 663552 + 9 · 663552 - 4
Otra pequeña mejora sobre la respuesta de Anders Kaseorg .
Cómo funciona
Acaba de cambiar la composición de la función
(.)
a la división fraccional(/)
. LaFractional x
parte en la firma de la función explota junto con la parte principal, dando un multiplicador constante ligeramente más alto.fuente
C, 979
f
tiene la firma:fuente
C ++ 11, no competitivo
Yo apenas no puedo conseguir esto bajo 100 bytes, pero está tan cerca que pensé que podría publicar de todos modos, con la esperanza de que alguien ve a una optimización.
Este es el prólogo, que cuesta 93 bytes:
Y la expresión, 9 bytes:
Para ilustrar:
Aproximadamente doblando cada vez que aumenta el número.
fuente
class
lugar detypename
. Me pregunto si hay un compilador en algún lugar que aún sea compatible con esa redacción para la compatibilidad con versiones anteriores.C #, 363
Expresión:
Firma de tipo:
Pruébalo en línea!
fuente
Ir 1.0 sin
reflect
, 98Los tipos Go 1.x están definidos estáticamente. Aquí está mi primer intento:
En el patio de juegos Go :
Ir 1.9 usando alias de tipo, 2389
En el patio de juegos Go :
Resultado:
Ir 1 usando
reflect
, 65532Hay un límite en el paquete
reflect
sobre la longitud de los nombres de tipo:len(name) <= 1<<16-1
Hasta ahora he podido alcanzar un nombre de tipo de 65532 bytes con este bloque:
Código completo en el patio de juegos Go :
Notas:
x:=
nunca se cuenta.fuente
reflect
importación debería contarseIdris,> hyper (hyper (hyper (hyper (999999999, 99, 99), 99,99), 99,99), 99,99)
Explicación:
Estamos definiendo una función f, calcular un tipo f (0) es solo el tipo de unidad, mientras que f (S (n)) calcula el tipo de igualdad aplicado al argumento de la función "hipered" por sí mismo y a f aplicado a n . La última línea es básicamente una función que espera un valor de un tipo como (27 = (4 = (2 = (1 = ()))))) (para n = 4).
Ejemplo simple
fuente
:Type
?hyper
; ¿Podrías explicar?hyper
se amplifica enormemente más que el resto, creo que quiere que todos / la mayoría de esos99
s sean9
s. (3) Asumiendo que Idris$
funciona como Haskell, el conjunto externo de paréntesis despuésf$
es redundante. (4) ¿Podría abreviarhyper
o requeriría una firma de tipo en sí misma?Haskell, 782
Expresión:
Firma de tipo:
fuente
sum
entonces es(Num a, Foldable t) => t a -> a
Ceilán, 38843546786070481 (~ 4 · 10 16 )
Son 49 tuplas anidadas, con una tupla vacía en el interior. El nombre corto de este tipo es en realidad el mismo que el valor en este caso, pero el nombre completamente expandido es mucho más largo.
El compilador de Ceilán funciona para siempre al intentar compilar esto (el compilador seguía ejecutándose después de 180 minutos). Tendré que intentar calcular la longitud de tipo teórica.
El problema aquí es que un tipo de tupla de un elemento
[X]
está realmente representado en el sistema de tipos de Ceylon comoTuple<X, X, []>
(el primer parámetro es un supertipo para todos los tipos de elementos, el segundo es el tipo del primer elemento y el tercero el tipo de todos excepto los primeros elementos) , que aquí es una tupla vacía (elempty
objeto, la instancia única que satisface la interfazEmpty
)).Entonces
[]
esempty
,[[]]
esTuple<[], [], []>
=Tuple<empty, empty, empty>
,[[[]]]
esTuple<[[]], [[]], []>
=Tuple<Tuple<[], [], []>, Tuple<[], [], []>, []>
. Y el nombre completo incluye los nombres de los paquetes, por lo que en realidadceylon.language::Tuple<ceylon.language::Tuple<ceylon.language::empty, ceylon.language::empty, ceylon.language::empty>, ceylon.language::Tuple<ceylon.language::empty, ceylon.language::empty, ceylon.language::empty>, ceylon.language::empty>
solo tenemos tres niveles. Y queremos ir a los 50.Como
ceylon.language::empty
tiene 22 caracteres de largo, y cada unoceylon.language::Tuple<?,?,ceylon.language::empty>
agrega 47 al doble del resultado del paso anterior, obtenemosf(1) = 22
, yf(n) = 2 · f(n-1) + 47
. Esto se simplificaf(n) = 69 · 2^(n - 1) - 47
, y al ingresar 50 nos da 38843546786070481. Por supuesto, esto es mucho más grande de lo que cabría en la memoria de mi computadora (8 · 10 9 bytes).Por supuesto, el compilador podría ser inteligente y no tratar de tener el nombre completo del tipo en la memoria hasta que se solicite su nombre.
Aquí está el programa completo tratando de imprimir el tipo:
fuente
C # (compilador interactivo de Visual C #) , 99 bytes, puntaje 841
Pruébalo en línea!
Salidas
fuente