Wyzwanie

Znajdź wyrażenie o maksymalnej długości 100 bajtów z najdłuższym podpisem.

Zasady

• Dowolny język o typie statycznym z wnioskowaniem typu jest dozwolony
• Typ musi być niejednoznaczny, ale w przeciwnym razie może zawierać typy bez zdefiniowanych instancji. Na przykład Num [a]i Eq [a]mogą nawet bez określonej instancji
• Brak importu innego niż minimum wymagane do skompilowania programu z STDIN / STDOUT
• Nieskończone typy są niedozwolone
• Jeśli odpowiedź ma więcej niż jedno wyrażenie, tylko jeden może przyczynić się do wyniku. Na przykład, chociaż sygnatura typu kompozycji ma (.) :: (b -> c) -> (a -> b) -> a -> cwynik 20, odpowiedź z 25 kopiami (.)\nmiałaby wynik 20, a nie 500
• Wyrażenie musi mieć maksymalnie 100 bajtów
• Wynik to liczba znaków w podpisie typu, z wyłączeniem nazwy funkcji i wszelkich białych znaków. Na przykład f :: (a -> b) -> a -> bmiałby wynik 12
• Najwyższy wynik wygrywa!

Przykłady

Chociaż dozwolone są inne języki, następujące przykłady są w języku 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)]

Haskell, ~ 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

Każde zastosowanie z fgrubsza podwaja podpis typu, przekształcając podpis typu Tna (T,T). Na przykład czterokrotna kompozycja f.f.f.f$0ma typ

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

Każda linia czterokrotnie zwiększa liczbę aplikacji f, podając 4^9 = 2^18na końcu. Tak więc podpis typu ma rozmiar rzędu 2^(2^18).

Java, wynik 17301488

Wymaga metody <T>java.util.Map<T,T>f(T t){return null;}, która została zaliczona do limitu 100 bajtów.

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

Podpis tego typu kompilacji powinien być zgodny z tym.

Haskell z rozszerzeniami,$\ggg 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)

Wypróbuj online!

Wymaga -XDataKinds, -XPolyKinds, -XTypeOperators, -XUndecidableInstances, i -XTypeFamilies.

Ogromne podziękowania dla Ørjana Johansena, który zdał sobie sprawę, że poprawienie konstruktora liczb naturalnych i zbudowanie argumentów nieco inaczej pozwoliło zaoszczędzić dwa bajty, pozostawiając wystarczająco dużo miejsca na kolejną iterację #.

Oczywiście sprawdzanie typu zrezygnuje z próby sprawdzenia tego programu. Aby uzyskać ogólne wyobrażenie o tym, jak wyglądałby podpis (gdyby był wystarczająco mały, aby zmieścił się w obserwowalnym wszechświecie), wypróbuj znacznie mniejszy

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

Wyjaśnienie

Rodzina #typów jest ściśle powiązana z funkcją Ackermann – Péter , powszechnie zapisywaną literą , ale rośnie znacznie szybciej. Funkcja Ackermanna – Pétera jest zdefiniowana$A$#

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

$A(m,0)=A(m-1,1)$ gdy$m > 0$

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

#z drugiej strony możemy zadzwonić do i napisać$B$

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

$B(m,0)=B(m-1,m)$ gdy$m > 0$

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

Tylko drugi przypadek jest inny. Dowód zakończenia jest identyczny ze standardowym dla i powinno być jasne, że dla wszystkich i .$A$$B(m,n) \ge A(m,n)$$m$$n$

Tutaj obliczamy jednoargumentową reprezentację

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

Według bezpośredniego obliczenia , a więc$B(B(B(B(0,0),0),0),0)=220$

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

Zauważ, że to tylko , więc na początek trochę podnieśliśmy. Nie mam jasnego pojęcia, o ile szybciej rośnie niż , ale biorąc pod uwagę przebieg obliczeń, wydaje się prawdopodobne, że będzie rosło znacznie szybciej.$A(A(A(A(0,0),0),0),0)$$5$$B$$A$

Liczba cyfr w parzystym jest zbyt duża, aby wyrazić praktycznie w systemie dziesiętnym, więc jest ... dość śmiesznie duża.$A(6,0)$

Definicja liczb naturalnych (?)jest nieco niestandardowa. Aby zaoszczędzić miejsce, używamy (?)zarówno typu liczb naturalnych (na poziomie typu), jak i typu proxy (na poziomie terminu).

Uważam, że albo, TypeFamiliesalbo (bardziej dosłownie i zaciemniając) FunctionalDependenciessą konieczne, aby uzyskać obliczenia na poziomie typu wymagane do osiągnięcia naprawdę dużych typów. UndecidableInstancesjest potrzebny do obejścia bardzo prymitywnego sprawdzania terminacji w Haskell. Inne rozszerzenia są potrzebne tylko do skompresowania kodu do małej dostępnej przestrzeni.

Haskell, 9 · 2 ⁶⁶³⁵⁵² - 3 (≈ 1,02 · 10 ¹⁹⁹⁷⁵⁰ )

Mała („mała”) poprawa w stosunku do xnor 522 ²⁶²¹⁴⁴ + 5 . To jest 99 bajtów.

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

Jak to działa

Mamy

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

i tak dalej, przy długości mniej więcej dwukrotnie większej dla każdego (:). Podane wyrażenie o.o.odziała (:).(:).(:).….(:)z 2 · 4 ⁶ · 3 ⁴ = 663552 kopii (:).

Haskell ^ziFlexibleContexts oraz NoMonomorphismRestriction(200 · 4 ³³¹⁷⁷⁶ + 75 · 331776 + 16) / 9 ≈ 2,53 · 10 ¹⁹⁹⁷⁵⁰

Niewielka poprawa w porównaniu z 12 · 2 ⁶⁶³⁵⁵² + 9 · 663552 - 4 × 1,36 · 10 ^{199750 Bubblera} , która również opiera się na tych rozszerzeniach. Sformułowanie rodzaju wyzwania sugeruje, że można na nich polegać („Na przykład Num [a]i Eq [a]są dozwolone, nawet bez określonej instancji”); Nie jestem pewny. To jest 100 bajtów.

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

Jak to działa

Mamy

-(/).(:) :: (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]]]

i tak dalej, z grubością czterokrotnie dla każdego (/).(:). Podane wyrażenie -o.o.odziała -(/).(:).(/).(:).….(/).(:)z 4 ⁶ · 3 ⁴ = 331776 kopii (/).(:).

Haskell, ^{12,2 663552} + 9,663552 - 4

Kolejna drobna poprawa w stosunku do odpowiedzi Andersa Kaseorga .

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

Jak to działa

(/) -- 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

Właśnie zmieniłem skład funkcji (.)na podział ułamkowy (/). Fractional xUdział w wybucha podpisu funkcji wraz z głównej części, dając nieco wyższą stałą mnożnika.

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 ma podpis:

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, niekonkurencyjny

I ledwo nie może uzyskać to pod 100 bajtów, ale to jest tak blisko Pomyślałem, że mogę pisać to w każdym razie, w nadziei, że ktoś zauważy optymalizację.

To jest prolog, który kosztuje 93 bajty:

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

I wyrażenie, 9 bajtów:

A<9>::T()

Ilustrować:

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

Z grubsza podwaja się za każdym razem, gdy liczba rośnie.

C # 363

Wyrażenie:

new{a=new{a=new{a=new{a=new{a=new{a=new{a=new{a=new{a=new{a=new{a=new{a=new{a=new{a=""}}}}}}}}}}}}}}

Podpis typu:

<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[<>f__AnonymousType0#1`1[System.String]]]]]]]]]]]]]]

Wypróbuj online!

Idź 1.0 bez reflect, 98

Typy Go 1.x są zdefiniowane statycznie. Oto moja pierwsza próba:

[][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][]string{}

Plac zabaw On the Go :

package main;import "fmt"
func main() {

    x := [][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][][]string{}

    fmt.Printf("%d %T\n", len(fmt.Sprintf("%T", x)), x)
}

Idź 1.9 używając aliasów typów, 2389

type(I=interface{f();g()};S=struct{p,q,r,s,t,u,v,w,x,y,z I});map[S]map[S]map[S]map[S]map[S]map[S]S{}

Plac zabaw On the Go :

package main;import("fmt";"strings")
func main() {

    type(I=interface{f();g()};S=struct{p,q,r,s,t,u,v,w,x,y,z I});x:=map[S]map[S]map[S]map[S]map[S]map[S]S{}

    fmt.Printf("%d %T\n", len(strings.Replace(fmt.Sprintf("%T", x), " ", "", -1)), x)
}

Wynik:

2389 map[struct { p interface { main.f(); main.g() }; q interface { main.f(); main.g() }; r interface { main.f(); main.g() }; s interface { main.f(); main.g() }; t interface { main.f(); main.g() }; u interface { main.f(); main.g() }; v interface { main.f(); main.g() }; w interface { main.f(); main.g() }; x interface { main.f(); main.g() }; y interface { main.f(); main.g() }; z interface { main.f(); main.g() } }]map[struct { p interface { main.f(); main.g() }; q interface { main.f(); main.g() }; r interface { main.f(); main.g() }; s interface { main.f(); main.g() }; t interface { main.f(); main.g() }; u interface { main.f(); main.g() }; v interface { main.f(); main.g() }; w interface { main.f(); main.g() }; x interface { main.f(); main.g() }; y interface { main.f(); main.g() }; z interface { main.f(); main.g() } }]map[struct { p interface { main.f(); main.g() }; q interface { main.f(); main.g() }; r interface { main.f(); main.g() }; s interface { main.f(); main.g() }; t interface { main.f(); main.g() }; u interface { main.f(); main.g() }; v interface { main.f(); main.g() }; w interface { main.f(); main.g() }; x interface { main.f(); main.g() }; y interface { main.f(); main.g() }; z interface { main.f(); main.g() } }]map[struct { p interface { main.f(); main.g() }; q interface { main.f(); main.g() }; r interface { main.f(); main.g() }; s interface { main.f(); main.g() }; t interface { main.f(); main.g() }; u interface { main.f(); main.g() }; v interface { main.f(); main.g() }; w interface { main.f(); main.g() }; x interface { main.f(); main.g() }; y interface { main.f(); main.g() }; z interface { main.f(); main.g() } }]map[struct { p interface { main.f(); main.g() }; q interface { main.f(); main.g() }; r interface { main.f(); main.g() }; s interface { main.f(); main.g() }; t interface { main.f(); main.g() }; u interface { main.f(); main.g() }; v interface { main.f(); main.g() }; w interface { main.f(); main.g() }; x interface { main.f(); main.g() }; y interface { main.f(); main.g() }; z interface { main.f(); main.g() } }]map[struct { p interface { main.f(); main.g() }; q interface { main.f(); main.g() }; r interface { main.f(); main.g() }; s interface { main.f(); main.g() }; t interface { main.f(); main.g() }; u interface { main.f(); main.g() }; v interface { main.f(); main.g() }; w interface { main.f(); main.g() }; x interface { main.f(); main.g() }; y interface { main.f(); main.g() }; z interface { main.f(); main.g() } }]struct { p interface { main.f(); main.g() }; q interface { main.f(); main.g() }; r interface { main.f(); main.g() }; s interface { main.f(); main.g() }; t interface { main.f(); main.g() }; u interface { main.f(); main.g() }; v interface { main.f(); main.g() }; w interface { main.f(); main.g() }; x interface { main.f(); main.g() }; y interface { main.f(); main.g() }; z interface { main.f(); main.g() } }

Idź 1 za pomocą reflect, 65532

W pakiecie istnieje ograniczeniereflect długości nazw typów:len(name) <= 1<<16-1

Do tej pory udało mi się uzyskać nazwę typu 65532 bajtów za pomocą tego bloku:

t:=reflect.TypeOf(0);u:=t;for i:=0;i<8191;i++{t=reflect.MapOf(u,t)};reflect.New(t).Interface()

Pełny kod na placu zabaw Go :

package main;import("fmt";"reflect")
func main() {

    t:=reflect.TypeOf(0);u:=t;for i:=0;i<8191;i++{t=reflect.MapOf(u,t)};x:=reflect.New(t).Interface()

    fmt.Printf("%d %T\n", len(fmt.Sprintf("%T", x)), x)
}

Idris,> hyper (hyper (hyper (hyper (999999999, 99, 99), 99,99), 99,99), 99,99)

f:Nat->Type
f Z=()
f(S n)=hyper n n n~=~f n
the$f$hyper(hyper(hyper(hyper 999999999 9 9) 9 9)9 9)9 9

Wyjaśnienie:

Definiujemy funkcję f, obliczenie typu f (0) jest tylko typem jednostki, podczas gdy f (S (n)) oblicza się do typu równości zastosowanego do argumentu funkcji „przeforsowanego” przez siebie i do f zastosowanego do n . Ostatni wiersz jest w zasadzie funkcją oczekującą wartości typu typu (27 = (4 = (2 = (1 = ()))))) (dla n = 4).

Prosty przykład

f 3 = (27 = (4 = (2 = (1 = ()))))

Haskell, 782

Wyrażenie:

sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum.sum

Podpis typu:

:: (Num [[[[[[[[[[[[[[[[[[[[[[[[c]]]]]]]]]]]]]]]]]]]]]]]], Num [[[[[[[[[[[[[[[[[[[[[[[c]]]]]]]]]]]]]]]]]]]]]]], Num [[[[[[[[[[[[[[[[[[[[[[c]]]]]]]]]]]]]]]]]]]]]], Num [[[[[[[[[[[[[[[[[[[[[c]]]]]]]]]]]]]]]]]]]]], Num [[[[[[[[[[[[[[[[[[[[c]]]]]]]]]]]]]]]]]]]], Num [[[[[[[[[[[[[[[[[[[c]]]]]]]]]]]]]]]]]]], Num [[[[[[[[[[[[[[[[[[c]]]]]]]]]]]]]]]]]], Num [[[[[[[[[[[[[[[[[c]]]]]]]]]]]]]]]]], Num [[[[[[[[[[[[[[[[c]]]]]]]]]]]]]]]], Num [[[[[[[[[[[[[[[c]]]]]]]]]]]]]]], Num [[[[[[[[[[[[[[c]]]]]]]]]]]]]], Num [[[[[[[[[[[[[c]]]]]]]]]]]]], Num [[[[[[[[[[[[c]]]]]]]]]]]], Num [[[[[[[[[[[c]]]]]]]]]]], Num [[[[[[[[[[c]]]]]]]]]], Num [[[[[[[[[c]]]]]]]]], Num [[[[[[[[c]]]]]]]], Num [[[[[[[c]]]]]]], Num [[[[[[c]]]]]], Num [[[[[c]]]]], Num [[[[c]]]], Num [[[c]]], Num [[c]], Num [c], Num c) => [[[[[[[[[[[[[[[[[[[[[[[[[c]]]]]]]]]]]]]]]]]]]]]]]]] -> c

Ceylon, 38843546786070481 (~ 4 · 10 ¹⁶ )

[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]

To 49 zagnieżdżonych pojedynczych krotek, z pustą krotką najbardziej od środka. Krótka nazwa tego typu jest w rzeczywistości taka sama jak wartość w tym przypadku, ale w pełni rozwinięta nazwa jest znacznie dłuższa.

Kompilator Ceylon działa wiecznie, próbując to skompilować (kompilator nadal działał po 180 minutach) - będę musiał spróbować obliczyć teoretyczną długość typu.

Problem polega na tym, że w [X]systemie typów Cejlona typ krotki z jednym elementem jest w rzeczywistości reprezentowany jako Tuple<X, X, []>(pierwszy parametr jest nadtypem dla wszystkich typów elementów, drugi to typ pierwszego elementu, a trzeci typ wszystkich oprócz pierwszych elementów , który jest tutaj pustą krotką ( emptyobiekt, pojedyncza instancja spełniająca interfejs Empty)).

Więc []jest empty, [[]]jest Tuple<[], [], []>= Tuple<empty, empty, empty>, [[[]]]jest Tuple<[[]], [[]], []>= Tuple<Tuple<[], [], []>, Tuple<[], [], []>, []>. A pełna nazwa zawiera nazwy pakietów, więc właściwie mamy ceylon.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>tylko trzy poziomy. I chcemy przejść do 50.

Ponieważ ceylon.language::emptyma 22 znaki i każdy ceylon.language::Tuple<?,?,ceylon.language::empty>dodaje 47 do dwukrotności wyniku z poprzedniego kroku, otrzymujemy f(1) = 22i f(n) = 2 · f(n-1) + 47. Upraszcza to f(n) = 69 · 2^(n - 1) - 47, a wpisanie 50 daje nam 38843546786070481. Oczywiście jest to znacznie więcej niż mieściłoby się w pamięci mojego komputera (8 · 10 ⁹ bajtów).

Oczywiście kompilator może być inteligentny i nie próbować przechowywać w pamięci całej nazwy typu, dopóki nie zostanie zażądana jego nazwa.

Oto pełny program próbujący wydrukować typ:

import ceylon.language.meta {
    type
}
"Run the module `codegolf.signature71797`."
shared void run() {
    value x = [[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]];
    print(type(x));
}

C # (interaktywny kompilator Visual C #) , 99 bajtów, wynik 841

(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,(1,1,1))))))))))))))))))))))))

Wypróbuj online!

Wyjścia

System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`2[System.Int32,System.ValueTuple`3[System.Int32,System.Int32,System.Int32]]]]]]]]]]]]]]]]]]]]]]]]