Desafio
Encontre uma expressão, no máximo 100 bytes, com a assinatura de tipo mais longa.
Regras
- Qualquer idioma digitado estaticamente com inferência de tipo é permitido
- O tipo deve ser não ambíguo, mas pode incluir tipos sem instâncias definidas. Por exemplo
Num [a]
eEq [a]
são permitidos, mesmo sem uma instância definida - Nenhuma importação além do mínimo necessário para compilar um programa com STDIN / STDOUT
- Tipos infinitos não são permitidos
- Se uma resposta tiver mais de uma expressão, apenas uma poderá contribuir para a pontuação. Por exemplo, embora a assinatura do tipo de composição seja
(.) :: (b -> c) -> (a -> b) -> a -> c
, com uma pontuação de 20, a resposta com 25 cópias de(.)\n
teria uma pontuação de 20, e não 500 - A expressão deve ter no máximo 100 bytes
- A pontuação é o número de caracteres na assinatura do tipo, excluindo o nome da função e qualquer espaço em branco. Por exemplo,
f :: (a -> b) -> a -> b
teria uma pontuação de 12 - A pontuação mais alta vence!
Exemplos
Embora outros idiomas sejam permitidos, os seguintes exemplos estão em 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
fonte
fonte
Respostas:
Haskell, ~ 2 ^ (2 ^ 18)
Cada aplicativo
f
dobra aproximadamente a assinatura de tipo, transformando a assinatura de tipoT
em(T,T)
. Por exemplo, a composição quádruplaf.f.f.f$0
tem o tipoCada linha quadruplica o número de aplicações de
f
, dando4^9 = 2^18
no final. Portanto, a assinatura do tipo tem tamanho da ordem de2^(2^18)
.fonte
f x=(x,x,x)
, ao custo de umn.
na última linha, obtemos a pontuação ideal para essa estrutura geral.n.
será maior.2^18
vs, a3 * (2^16)
menos que eu tenha cometido um erro ao calcular a exponenciação original:2^(4^9)
vs3^((4^8)*3)
(,)
(ou(,,)
) pode ser usado para salvar alguns bytes e melhorar a pontuação usando maisn
s.Java, pontuação 17301488
Requer o método
<T>java.util.Map<T,T>f(T t){return null;}
, que foi contado no limite de 100 bytes.f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(1)))))))))))))))))))
A assinatura do tipo em tempo de compilação disso deve corresponder a isso.
fonte
Haskell com extensões,⋙A(A(A(A(220,0),0),0),0)
Experimente online!
Requer
-XDataKinds
,-XPolyKinds
,-XTypeOperators
,-XUndecidableInstances
, e-XTypeFamilies
.Muito obrigado a Ørjan Johansen, que percebeu que fazer o construtor de números naturais infixar e construir os argumentos um pouco diferentemente salvou dois bytes, abrindo espaço suficiente para outra iteração de
#
.Obviamente, o verificador de tipos desistirá de tentar verificar este programa. Para ter uma idéia geral de como seria a assinatura (se ela fosse pequena o suficiente para caber no universo observável), tente o tamanho bem menor.
Explicação
AA , mas
#
família de tipos está intimamente relacionada à função Ackermann – Péter , comumente escrita#
cresce consideravelmente mais rápido. A função Ackermann – Péter é definida#
Aqui calculamos uma representação unária de
A definição dos números naturais,,
(?)
é um pouco fora do padrão. Para economizar espaço, usamos(?)
como um tipo de número natural (no nível do tipo) e um tipo de proxy (no nível do termo).Acredito que
TypeFamilies
ou (de maneira mais detalhada e ofuscada)FunctionalDependencies
são necessários para obter a computação em nível de tipo necessária para alcançar tipos verdadeiramente grandes.UndecidableInstances
é necessário para solucionar a verificação de terminação muito primitiva de Haskell. As outras extensões são necessárias apenas para compactar o código no pequeno espaço disponível.fonte
#Z
Z
s na frente é melhor do que começar comS(S Z)#S Z
o mesmo?#Z
no final é bem-vindo.?
salvar o outro, deixando espaço para o extra#Z
.A(m,1)
nunca era maior queA(A(m,0),0)
e estava prestes a comentar sobre isso, mas então você acabou de otimizar até o ponto em que as opções eram iguais. (Tambémm+1
nunca é maior queA(m,0)
.)Haskell, 9 · 2 663552 - 3 ( ± 1,02 · 10 199750 )
Uma pequena ("pequena") melhoria em relação a 5n2 262144 + 5 do xnor . Isso é 99 bytes.
Como funciona
Nós temos
e assim por diante, com o comprimento aproximadamente dobrando para cada um
(:)
. A expressão fornecidao.o.o
funciona(:).(:).(:).….(:)
com 2 · 4 6 · 3 4 = 663552 cópias de(:)
.Haskell com
FlexibleContexts
eNoMonomorphismRestriction
, (200 · 4 331776 + 75 · 331776 + 16) / 9 ± 2,53 · 10 199750Uma pequena melhoria em relação ao 12 · 2 663552 + 9 · 663552 - 4 × 1,36 · 10 199750 do Bubbler , que também se baseia nessas extensões. A redação do desafio sugere que pode ser bom confiar neles ("Por exemplo,
Num [a]
eEq [a]
são permitidos, mesmo sem uma instância definida"); Não tenho certeza. Isso é 100 bytes.Como funciona
Nós temos
e assim por diante, com o comprimento quadruplicando para cada um
(/).(:)
. A expressão dada-o.o.o
funciona-(/).(:).(/).(:).….(/).(:)
com 4 6 · 3 4 = 331776 cópias de(/).(:)
.fonte
Haskell, 12 · 2 663552 + 9 · 663552 - 4
Mais uma pequena melhoria em relação à resposta de Anders Kaseorg .
Como funciona
Apenas alterei a composição da função
(.)
para divisão fracionária(/)
. AFractional x
parte na assinatura da função explode junto com a parte principal, resultando em um multiplicador constante um pouco maior.fonte
C, 979
f
tem a assinatura:fonte
C ++ 11, não-concorrente
Eu mal consigo obter isso abaixo de 100 bytes, mas é tão próximo que achei que poderia postá-lo de qualquer maneira, na esperança de que alguém visse uma otimização.
Este é o prólogo, custando 93 bytes:
E a expressão, 9 bytes:
Ilustrar:
Dobrar praticamente toda vez que o número aumenta.
fonte
class
vez detypename
. Gostaria de saber se existe um compilador por aí em algum lugar que ainda suporta esse fraseado para compatibilidade com versões anteriores?C #, 363
Expressão:
Assinatura de tipo:
Experimente online!
fonte
Go 1.0 sem
reflect
, 98Os tipos Go 1.x são definidos estaticamente. Aqui está minha primeira tentativa:
Parque infantil On the Go :
Vá 1.9 usando aliases de tipo, 2389
Parque infantil On the Go :
Resultado:
Vá 1 usando
reflect
, 65532Há um limite no pacote
reflect
para o tamanho dos nomes dos tipos:len(name) <= 1<<16-1
Consegui alcançar um nome de tipo de 65532 bytes até agora com este bloco:
Código completo no playground Go :
Notas:
x:=
nunca é contado.fonte
reflect
importação precisaria ser contadaIdris,> hyper (hyper (hyper (hyper (999999999, 99, 99), 99,99), 99,99), 99,99)
Explicação:
Estamos definindo uma função f, computando um tipo f (0) é apenas o tipo de unidade, enquanto f (S (n)) calcula o tipo de igualdade aplicado ao argumento da função "hypered" por si só e f aplicado a n . A última linha basicamente é uma função que espera um valor de um tipo como (27 = (4 = (2 = (1 = ())))))) (para n = 4).
Exemplo Simples
fonte
:Type
?hyper
; você poderia explicar?hyper
é amplificado enormemente mais do que o resto, acho que você deseja que todos / a maioria desses99
s sejam9
s. (3) Assumindo os$
trabalhos de Idris como os de Haskell, o conjunto externo de parênteses depoisf$
é redundante. (4) Você poderia abreviarhyper
ou isso exigiria uma assinatura de tipo?Haskell, 782
Expressão:
Assinatura de tipo:
fonte
sum
então é(Num a, Foldable t) => t a -> a
Ceilão, 38843546786070481 (~ 4 · 10 16 )
São 49 tuplas aninhadas, com uma tupla vazia mais interna. O nome abreviado desse tipo é realmente o mesmo que o valor nesse caso, mas o nome totalmente expandido é muito mais longo.
O compilador Ceylon está funcionando para sempre ao tentar compilar isso (o compilador ainda estava em execução após 180 minutos) - vou ter que tentar calcular o tamanho do tipo teórico.
O problema aqui é que um tipo de tupla de um elemento
[X]
é realmente representado no sistema de tipos do Ceilão comoTuple<X, X, []>
(o primeiro parâmetro é um supertipo para todos os tipos de elementos, o segundo é o tipo do primeiro elemento e o terceiro o tipo de todos, exceto os primeiros elementos , que aqui é uma tupla vazia (oempty
objeto, a instância única que satisfaz a interfaceEmpty
)).Então
[]
éempty
,[[]]
éTuple<[], [], []>
=Tuple<empty, empty, empty>
,[[[]]]
éTuple<[[]], [[]], []>
=Tuple<Tuple<[], [], []>, Tuple<[], [], []>, []>
. E o nome completo inclui os nomes dos pacotes, portanto, temosceylon.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>
apenas três níveis. E nós queremos ir para 50.Com
ceylon.language::empty
22 caracteres e cada umceylon.language::Tuple<?,?,ceylon.language::empty>
adiciona 47 a duas vezes o resultado da etapa anterior, obtemosf(1) = 22
, ef(n) = 2 · f(n-1) + 47
. Isso simplificaf(n) = 69 · 2^(n - 1) - 47
e a inserção de 50 fornece 38843546786070481. É claro que isso é muito maior do que o que caberia na memória do meu computador (8,10 9 bytes).Obviamente, o compilador pode ser inteligente e não tentar ter o nome do tipo inteiro na memória até que seu nome seja solicitado.
Aqui está o programa completo tentando imprimir o tipo:
fonte
C # (compilador interativo do Visual C #) , 99 bytes, pontuação 841
Experimente online!
Saídas
fonte