도전

가장 긴 형식 서명으로 최대 100 바이트 길이의 표현식을 찾으십시오.

규칙

형식 유추가있는 정적으로 유형이 지정된 언어가 허용됩니다.
유형은 모호하지 않아야하지만 정의 된 인스턴스가없는 유형을 포함 할 수 있습니다. 예를 들어 Num [a]및Eq [a] 심지어 정의 예를하지 않고, 사용할 수 있습니다
STDIN / STDOUT으로 프로그램을 컴파일하는 데 필요한 최소값 이외의 가져 오기는 없습니다.
무한 타입은 허용되지 않습니다
답변에 둘 이상의 표현이있는 경우 하나만 점수에 기여할 수 있습니다. 예를 들어, 컴포지션의 형식 서명이 (.) :: (b -> c) -> (a -> b) -> a -> c점수가 20이지만, 사본이 25 개인 답변 (.)\n의 점수는 500이 아닌 20입니다.
표현식은 최대 100 바이트 여야합니다.
점수는 함수의 이름과 공백을 제외한 유형 서명의 문자 수입니다. 예를 들어 f :: (a -> b) -> a -> b점수는 12입니다.
가장 높은 점수가 이깁니다!

예

다른 언어도 허용되지만 다음 예제는 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)]

답변

하스켈, ~ 2 ^ (2 ^ 18)

f x=(x,x)
g=f.f.f.f
h=g.g.g.g
i=h.h.h.h
j=i.i.i.i
k=j.j.j.j
l=k.k.k.k
m=l.l.l.l
n=m.m.m.m
n.n.n.n$0

각 응용 프로그램은 f대략 유형 서명으로 변환하여 유형 서명을 두배 T로를 (T,T). 예를 들어, 네 가지 구성 f.f.f.f$0은 유형이

Num a => ((((a, a), (a, a)), ((a, a), (a, a))), (((a, a), (a, a)), ((a, a), (a, a))))

각 줄의 응용 프로그램의 수를 quadraples f주는 4^9 = 2^18말. 따라서 형식 서명의 크기는의 순서입니다 2^(2^18).

답변

자바, 17301488 점

<T>java.util.Map<T,T>f(T t){return null;}100 바이트 제한으로 계산 된 방법이 필요합니다 .

f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(1)))))))))))))))))))

이것의 컴파일 타임 타입 서명은 이것과 일치해야 합니다.

답변

확장 기능이있는 Haskell , $⋙ A (A (A (A (220, 0), 0), 0), 0)$

Z::Z#Z#Z#Z#Z#Z#Z#Z#Z?Z
data a?b=Z|S(a?b)
type family m#n where Z#n=S n;S m#Z=m#S m;S m#S n=m#(S m#n)

온라인으로 사용해보십시오!

필요 -XDataKinds, -XPolyKinds, -XTypeOperators, -XUndecidableInstances,와 -XTypeFamilies.

Ørjan Johansen은 자연수 생성자를 삽입하고 인수를 조금 다르게 저장하여 2 바이트를 절약하여 다른 반복을위한 충분한 공간을 제공한다는 사실을 깨달은 Ørjan Johansen에게 많은 감사를드립니다 #.

분명히 타입 체커는이 프로그램을 검사하려고 포기할 것입니다. 서명이 어떻게 보이는지에 대한 일반적인 의미를 얻으려면 (관찰 가능한 우주에 적합 할 정도로 작은 경우) 훨씬 더 작은 것을 시도하십시오

Z::S(S Z)#Z?Z

설명

#유형 제품군은 밀접하게 관련되어 ACKERMANN – 피터 기능 , 일반적으로 작성 $A$

A

$A$ 하지만, #상당히 빠르게 성장한다. Ackermann–Péter 기능이 정의되었습니다

$A (0, n) = n + 1$
$A (0, n) = n + 1$
$A(0,n)=n+1$

$A (m, 0) = A (m - 1, 1)$
$A (m, 0) = A (m - 1, 1)$
$A(m,0)=A(m-1,1)$ 경우 $m > 0$
$m > 0$
$m > 0$

$A (m, n) = A (m - 1, A (m, n - 1))$
$A (m, n) = A (m - 1, A (m, n - 1))$
$A(m,n)=A(m-1, A(m, n-1))$ 때 $m, n > 0$
$m, n > 0$
$m, n > 0$

#반면에, 우리는 $B$

B

$B$ 를 호출 하고

$B (0, n) = n + 1$
$B (0, n) = n + 1$
$B(0,n)=n+1$

$B (m, 0) = B (m - 1, m)$
$B (m, 0) = B (m - 1, m)$
$B(m,0)=B(m-1,m)$ 경우 $m > 0$
$m > 0$
$m > 0$

$B (m, n) = B (m - 1, B (m, n - 1))$
$B (m, n) = B (m - 1, B (m, n - 1))$
$B(m,n)=B(m-1, B(m, n-1))$ 때 $m, n > 0$
$m, n > 0$
$m,n > 0$

두 번째 경우 만 다릅니다. 종료 증명은 $A$

A

$A$ 의 표준과 동일 하며 모든 과 대해 $B (m, n) \geq A (m, n)$

B (m, n) \geq A (m, n)

$B(m,n) \ge A(m,n)$ 임을 분명히해야합니다 . $m$

m

$m$ $n$

n

$n$

여기서 우리는 단항 표현을 계산합니다.

$r = B (B (B (B (B (B (B (B (0, 0), 0), 0), 0), 0), 0), 0), 0)$
$r = B (B (B (B (B (B (B (B (0, 0), 0), 0), 0), 0), 0), 0), 0)$
$r = B(B(B(B(B(B(B(B(0,0),0),0),0),0),0),0),0)$

직접 계산을 통해 $B (B (B (B (0, 0), 0), 0), 0) = 220$

B (B (B (B (0, 0), 0), 0), 0) = 220

$B(B(B(B(0,0),0),0),0)=220$ 이므로

$r = B (B (B (B (220, 0), 0), 0), 0)$
$r = B (B (B (B (220, 0), 0), 0), 0)$
$r = B(B(B(B(220,0),0),0),0)$ .

참고 아니라 우리가 시작하기 좋은 비트까지 일을 충돌했습니다, 그래서. 나는 가 보다 얼마나 빨리 자라는 지에 대한 명확한 의미가 없습니다 $A (A (A (A (0, 0), 0), 0), 0)$

A (A (A (A (0, 0), 0), 0), 0)

$A(A(A(A(0,0),0),0),0)$ $5$

5

$5$ $B$

B

$B$ $A$

A

$A$ 계산이 진행되는 방식을 고려할 때 상당히 빠르게 성장할 것으로 보입니다.

짝수 의 자릿수 $A (6, 0)$

A (6, 0)

$A(6,0)$ 실제로 십진수로 표현하기에는 너무 크므로 이것은 엄청나게 큽니다.

자연수의 정의는 (?)약간 비표준입니다. 공간을 절약하기 위해 (?)자연수 유형 (유형 레벨)과 프록시 유형 (용어 레벨)으로 사용합니다.

나는 정말로 큰 유형에 도달하는 데 필요한 유형 수준 계산을 얻으려면 하나 TypeFamilies이상 (더 자세하고 난독하게) FunctionalDependencies이 필요 하다고 생각합니다 . UndecidableInstancesHaskell의 매우 기본적인 종료 검사 문제를 해결하는 데 필요합니다. 다른 확장은 코드를 사용 가능한 작은 공간으로 압축하는 데만 필요합니다.

답변

하스켈, 9 · 2 ^663552-3 (≈ 1.02 · 10 ¹⁹⁹⁷⁵⁰ )

xnor의 5⋅2 ²⁶²¹⁴⁴ + 5 보다 작은 ( “작은”) 개선 . 99 바이트입니다.

f=(:).(:)
g=f.f.f.f
h=g.g.g.g
i=h.h.h.h
j=i.i.i.i
k=j.j.j.j
l=k.k.k.k
m=l.l.l
n=m.m.m
o=n.n.n
o.o.o

작동 원리

우리는

(:)         :: a -> [a] -> [a]
(:).(:)     :: a -> [[a] -> [a]] -> [[a] -> [a]]
(:).(:).(:) :: a -> [[[a] -> [a]] -> [[a] -> [a]]] -> [[[a] -> [a]] -> [[a] -> [a]]]

등등, 길이는 각각에 대해 대략 배가됩니다 (:). 주어진 표현 o.o.o은 (:).(:).(:).….(:)2 · 4 ⁶ · 3 ⁴ = 663552의(:) .

Haskell with `FlexibleContexts`and `NoMonomorphismRestriction`, (200 · 4 ³³¹⁷⁷⁶ + 75 · 331776 + 16) / 9 ≈ 2.53 · 10 ¹⁹⁹⁷⁵⁰

Bubbler의 12 · 2 ⁶⁶³⁵⁵² + 9 · 663552 − 4 ≈ 1.36 · 10 ^199750에 비해 약간의 개선이 이루어 ^졌으며 , 이러한 확장에도 의존합니다. 의 도전 종류의 문구가 그들에 의존 괜찮을 수도 있습니다 제안 ( “예를 들어 Num [a]그리고 Eq [a]심지어 정의 예를하지 않고, 사용할 수 있습니다”); 잘 모르겠습니다. 100 바이트입니다.

f=(/).(:)
g=f.f.f.f
h=g.g.g.g
i=h.h.h.h
j=i.i.i.i
k=j.j.j.j
l=k.k.k.k
m=l.l.l
n=m.m.m
o=n.n.n
-o.o.o

작동 원리

우리는

-(/).(:) :: (Fractional ([a] -> [a]), Num (a -> ([a] -> [a]) -> [a] -> [a])) => a -> ([a] -> [a]) -> [a] -> [a]
-(/).(:).(/).(:) :: (Fractional ([a] -> [a]), Fractional ([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]), Num (a -> ([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]) -> [([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]])) => a -> ([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]) -> [([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]
-(/).(:).(/).(:).(/).(:) :: (Fractional ([a] -> [a]), Fractional ([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]), Fractional ([([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]) -> [([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]] -> [([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]) -> [([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]]), Num (a -> ([([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]) -> [([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]] -> [([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]) -> [([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]]) -> [([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]) -> [([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]] -> [([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]) -> [([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]])) => a -> ([([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]) -> [([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]] -> [([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]) -> [([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]]) -> [([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]) -> [([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]] -> [([([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]) -> [([a] -> [a]) -> [a] -> [a]] -> [([a] -> [a]) -> [a] -> [a]]]

길이는 각각 대략 4 배가됩니다 (/).(:). 주어진 표현 -o.o.o은의 -(/).(:).(/).(:).….(/).(:)4 ⁶ · 3 ⁴ = 331776 사본으로 해결 (/).(:)됩니다.

답변

하스켈, 12 · 2 ⁶⁶³⁵⁵² + 9 · 663552-4

Anders Kaseorg의 답변에 대한 또 다른 작은 개선점 .

f=(/).(/)
g=f.f.f.f
h=g.g.g.g
i=h.h.h.h
j=i.i.i.i
k=j.j.j.j
l=k.k.k.k
m=l.l.l
n=m.m.m
o=n.n.n
o.o.o

작동 원리

(/) -- score 27
   :: Fractional a => a -> a -> a
(/).(/) -- score 62
   :: (Fractional a, Fractional (a -> a)) => a -> (a -> a) -> a -> a
(/).(/).(/) -- score 119
   :: (Fractional a, Fractional (a -> a), Fractional ((a -> a) -> a -> a)) =>
      a -> ((a -> a) -> a -> a) -> (a -> a) -> a -> a
(/).(/).(/).(/) -- score 224
   :: (Fractional a, Fractional (a -> a),
       Fractional ((a -> a) -> a -> a),
       Fractional (((a -> a) -> a -> a) -> (a -> a) -> a -> a)) =>
      a
      -> (((a -> a) -> a -> a) -> (a -> a) -> a -> a)
      -> ((a -> a) -> a -> a)
      -> (a -> a)
      -> a
      -> a

함수 구성 (.)을 분수 나누기로 변경했습니다 (/). Fractional x함수 시그니처 의 부분은 메인 부분과 함께 폭발하여 약간 더 높은 상수 승수를 제공합니다.

답변

C, 979

#define a int,int,int
#define b a,a,a,a
#define c b,b,b
#define d c,c,c
#define e d,d,d
int(*f)(e);

f 서명이 있습니다 :

int(*)(int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int)

답변

비경쟁 C ++ 11

나는 이것을 100 바이트 이하로 간신히 얻을 수는 없지만, 너무 가까워서 누군가가 최적화를 발견하기를 바랍니다.

이것은 프롤로그이며 93 바이트입니다.

#define t(a,b,c)template<a>union A b{using T=c(*)(c);};
t(int N,,typename A<N-1>::T)t(,<0>,A)

그리고 표현은 9 바이트입니다.

A<9>::T()

설명하기 위해 :

Expr       Type
A<0>::T()  A<0> (*)(A<0>)
A<1>::T()  A<0> (*(*)(A<0> (*)(A<0>)))(A<0>)
A<2>::T()  A<0> (*(*(*)(A<0> (*(*)(A<0> (*)(A<0>)))(A<0>)))(A<0> (*)(A<0>)))(A<0>)

숫자가 증가 할 때마다 거의 두 배가됩니다.

How IT

언제든지 물어보세요.

태그 보관물: busy-beaver

긴 타입의 서명을 만드십시오 b) -> a -> c점수가

도전

규칙

예

답변

하스켈, ~ 2 ^ (2 ^ 18)

답변

자바, 17301488 점

답변

확장 기능이있는 Haskell , $⋙ A (A (A (A (220, 0), 0), 0), 0)$

설명

답변

하스켈, 9 · 2 ^663552-3 (≈ 1.02 · 10 ¹⁹⁹⁷⁵⁰ )

작동 원리

Haskell with `FlexibleContexts`and `NoMonomorphismRestriction`, (200 · 4 ³³¹⁷⁷⁶ + 75 · 331776 + 16) / 9 ≈ 2.53 · 10 ¹⁹⁹⁷⁵⁰

작동 원리

답변

하스켈, 12 · 2 ⁶⁶³⁵⁵² + 9 · 663552-4

작동 원리

답변

C, 979

답변

비경쟁 C ++ 11

도전

규칙

예

답변

하스켈, ~ 2 ^ (2 ^ 18)

답변

자바, 17301488 점

답변

확장 기능이있는 Haskell , ⋙A(A(A(A(220,0),0),0),0) ⋙A(A(A(A(220,0),0),0),0) \ggg A(A(A(A(220,0),0),0),0)

설명

답변

하스켈, 9 · 2 663552-3 (≈ 1.02 · 10 199750 )

작동 원리

Haskell with FlexibleContextsand NoMonomorphismRestriction, (200 · 4 331776 + 75 · 331776 + 16) / 9 ≈ 2.53 · 10 199750

작동 원리

답변

하스켈, 12 · 2 663552 + 9 · 663552-4

작동 원리

답변

C, 979

답변

비경쟁 C ++ 11

확장 기능이있는 Haskell , $⋙ A (A (A (A (220, 0), 0), 0), 0)$

하스켈, 9 · 2 ^663552-3 (≈ 1.02 · 10 ¹⁹⁹⁷⁵⁰ )

Haskell with `FlexibleContexts`and `NoMonomorphismRestriction`, (200 · 4 ³³¹⁷⁷⁶ + 75 · 331776 + 16) / 9 ≈ 2.53 · 10 ¹⁹⁹⁷⁵⁰

하스켈, 12 · 2 ⁶⁶³⁵⁵² + 9 · 663552-4