22
\$\begingroup\$

Challenge

Find an expression, at most 100 bytes long, with the longest type signature.

Rules

  • Any statically typed language with type inference is allowed
  • The type must be non-ambiguous, but otherwise may include types without defined instances. For example Num [a] and Eq [a] are allowed, even without a defined instance
  • No imports other than the minimum required to compile a program with STDIN/STDOUT
  • Infinite types are not allowed
  • If an answer has more than one expression, only one may contribute to the score. For example, although the type signature of composition is (.) :: (b -> c) -> (a -> b) -> a -> c, having a score of 20, the answer with 25 copies of (.)\n would have a score of 20, not 500
  • The expression must be, at most, 100 bytes
  • The score is the number of characters in the type signature, excluding the name of the function and any whitespace. For example, f :: (a -> b) -> a -> b would have a score of 12
  • The highest score wins!

Examples

Although other languages are allowed, the following examples are in 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)]
\$\endgroup\$
  • \$\begingroup\$ Related. I did think there was an almost exact dupe, but I haven't found it. \$\endgroup\$ – Peter Taylor Feb 12 '16 at 8:12
  • 2
    \$\begingroup\$ I suspect that a language with dependent typing can make a type signature of the length of any number of can compute. \$\endgroup\$ – xnor Feb 12 '16 at 8:12
  • \$\begingroup\$ @xnor As type systems themselves may be turing complete (stackoverflow.com/a/4047732/5154287), I guess it becomes more of a busy beaver problem then. Should I edit the tags? \$\endgroup\$ – Michael Klein Feb 12 '16 at 8:17

13 Answers 13

19
\$\begingroup\$

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

Each application of f roughly double the type signature by transforming the type signature T to (T,T). For example, the fourfold composition f.f.f.f$0 has type

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

Each line quadraples the number of applications of f, giving 4^9 = 2^18 at the end. So, the type signature has size of the order of 2^(2^18).

\$\endgroup\$
  • 2
    \$\begingroup\$ The classic approach, but I think the parameters can be better tuned. Specifically, I think that f x=(x,x,x) at the cost of one n. in the last line gives the optimal score for this overall structure. \$\endgroup\$ – Peter Taylor Feb 12 '16 at 9:11
  • \$\begingroup\$ I don't know Haskell, so I could be off base here, but I'll point out that 4^(4^4) is less than 3^(4^5) \$\endgroup\$ – Sparr Feb 12 '16 at 18:01
  • \$\begingroup\$ Pretty sure the 4th n. is going to be larger. 2^18 vs 3 * (2^16) unless I made a mistake calculating the original exponentiation: 2^(4^9) vs. 3^((4^8)*3) \$\endgroup\$ – Draco18s Feb 12 '16 at 18:20
  • \$\begingroup\$ No, @PeterTaylor is correct: 2^(4^9) = 16^(4^8) < 27^(4^8) = 3^(4^8 ⋅ 3). \$\endgroup\$ – Anders Kaseorg Jun 22 '17 at 23:53
  • \$\begingroup\$ (,) (or (,,)) can be used to save some bytes and improve the score by using more ns. \$\endgroup\$ – ბიმო Aug 8 '18 at 12:29
11
\$\begingroup\$

Java, score 17301488

Requires the method <T>java.util.Map<T,T>f(T t){return null;}, which has been counted towards the 100-byte limit.

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

The compile-time type signature of this should match this.

\$\endgroup\$
  • \$\begingroup\$ hmm. since lambdas are allowed this would probably get a higher score \$\endgroup\$ – ASCII-only Mar 14 at 5:26
10
\$\begingroup\$

Haskell with extensions, \$\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)

Try it online!

Requires -XDataKinds, -XPolyKinds, -XTypeOperators, -XUndecidableInstances, and -XTypeFamilies.

Many thanks to Ørjan Johansen, who realized that making the natural number constructor infix and building the arguments a bit differently saved two bytes, making just enough room for another iteration of #.

Obviously, the type checker will give up trying to check this program. To get a general sense of what the signature would look like (if it were small enough to fit in the observable universe), try the much smaller

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

Explanation

The # type family is closely related the Ackermann–Péter function, commonly written \$A\$, but # grows considerably faster. The Ackermann–Péter function is defined

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

\$A(m,0)=A(m-1,1)\$ when \$m > 0\$

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

#, on the other hand, we can call \$B\$, and write

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

\$B(m,0)=B(m-1,m)\$ when \$m > 0\$

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

Only the second case is different. The termination proof is identical to the standard one for \$A\$, and it should be clear that \$B(m,n) \ge A(m,n)\$ for all \$m\$ and \$n\$.

Here we calculate a unary representation of

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

By direct calculation, \$B(B(B(B(0,0),0),0),0)=220\$, so

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

Note that \$A(A(A(A(0,0),0),0),0)\$ is only \$5\$, so we've bumped things up a good bit to start out. I don't have a very clear sense of just how much faster \$B\$ grows than \$A\$, but considering how the calculation proceeds, it seems likely to grow quite a lot faster.

The number of digits in even \$A(6,0)\$ is too large to express practically in decimal, so this is ... rather ridiculously large.

The definition of the natural numbers, (?), is a bit non-standard. To save space, we use (?) as both a natural number type (at the type level) and a proxy type (at the term level).

I believe that either TypeFamilies or (more verbosely and obfuscatedly) FunctionalDependencies are necessary to get the type-level computation required to reach truly large types. UndecidableInstances is needed to work around Haskell's very primitive termination checking. The other extensions are only needed to compress the code into the small available space.

\$\endgroup\$
  • \$\begingroup\$ One more #Z \$\endgroup\$ – Ørjan Johansen Mar 14 at 23:33
  • \$\begingroup\$ @ØrjanJohansen, is stacking up Zs at the front better than starting with S(S Z)#S Z, or the same? \$\endgroup\$ – dfeuer Mar 15 at 2:20
  • \$\begingroup\$ Either way, the extra #Z at the end is most welcome. \$\endgroup\$ – dfeuer Mar 15 at 2:21
  • 1
    \$\begingroup\$ It's the exact same value but saves one byte, and changing the datatype to ? saves the other, leaving room for the extra #Z. \$\endgroup\$ – Ørjan Johansen Mar 15 at 3:30
  • 1
    \$\begingroup\$ While you were first editing, I discovered A(m,1) was never bigger than A(A(m,0),0), and was about to remark on it, but then you'd just optimized to the point where the options were equal. (Also m+1 is never bigger than A(m,0).) \$\endgroup\$ – Ørjan Johansen Mar 15 at 3:34
9
\$\begingroup\$

Haskell, 9·2663552 − 3 (≈ 1.02·10199750)

A small (“small”) improvement over xnor’s 5⋅2262144 + 5. This is 99 bytes.

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

How it works

We have

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

and so on, with the length roughly doubling for each (:). The given expression o.o.o works out to (:).(:).(:).….(:) with 2·46·34 = 663552 copies of (:).

Haskell with FlexibleContexts and NoMonomorphismRestriction, (200·4331776 + 75·331776 + 16)/9 ≈ 2.53·10199750

A small improvement over Bubbler’s 12·2663552 + 9·663552 − 4 ≈ 1.36·10199750, which also relies on these extensions. The wording of the challenge sort of suggests it might be okay to rely on them (“For example Num [a] and Eq [a] are allowed, even without a defined instance”); I’m not sure. This is 100 bytes.

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

How it works

We have

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

and so on, with the length roughly quadrupling for each (/).(:). The given expression -o.o.o works out to -(/).(:).(/).(:).….(/).(:) with 46·34 = 331776 copies of (/).(:).

\$\endgroup\$
7
\$\begingroup\$

Haskell, 12·2663552 + 9·663552 - 4

Yet another small improvement over Anders Kaseorg's answer.

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

How it works

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

Just changed function composition (.) to fractional division (/). The Fractional x part in the function signature explodes along with the main part, giving slightly higher constant multiplier.

\$\endgroup\$
6
\$\begingroup\$

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 has the signature:

int(*)(int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int,int)
\$\endgroup\$
  • 1
    \$\begingroup\$ 979 33554438 58640620148060 this looks like some ridiculous OEIS entry. possibly the largest changes in magnitude I've ever seen in a PPCG entry being refined. \$\endgroup\$ – Sparr Feb 12 '16 at 17:56
  • \$\begingroup\$ @Sparr you ain't seen nuthin' yet \$\endgroup\$ – cat Mar 15 '16 at 3:45
5
\$\begingroup\$

C++11, noncompeting

I barely can't get this under 100 bytes, but it's so close I figured I might post it anyway, in the hopes that someone spots an optimization.

This is the prologue, costing 93 bytes:

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

And the expression, 9 bytes:

A<9>::T()

To illustrate:

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

Roughly doubling every time the number increases.

\$\endgroup\$
  • \$\begingroup\$ I seem to remember there were some very old (pre-standard?) versions of C++ that used the keyword class rather than typename. I wonder if there's a compiler out there somewhere which still supports that phrasing for backwards compatibility? \$\endgroup\$ – user62131 Feb 4 '17 at 15:06
4
\$\begingroup\$

C#, 363

Expression:

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=""}}}}}}}}}}}}}}

Type signature:

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Go 1.0 without reflect, 98

Go 1.x types are statically defined. Here is my first try:

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

On the Go playground:

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

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

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

Go 1.9 using type aliases, 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{}

On the Go playground:

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

Result:

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

Go 1 using reflect, 65532

There is a limit in package reflect on the length of type names: len(name) <= 1<<16-1

I've been able to reach a type name of 65532 bytes so far with this block:

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

Full code on the Go playground:

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


Notes: x:= is never counted.

\$\endgroup\$
  • \$\begingroup\$ invalid, reflect import would need to be counted \$\endgroup\$ – ASCII-only Mar 14 at 4:27
  • \$\begingroup\$ 3403? \$\endgroup\$ – ASCII-only Mar 14 at 4:33
  • \$\begingroup\$ 3685 \$\endgroup\$ – ASCII-only Mar 14 at 4:51
  • \$\begingroup\$ 65535 \$\endgroup\$ – ASCII-only Mar 14 at 5:14
1
\$\begingroup\$

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

Explanation:

We're defining a function f, computing a type f(0) is just the unit type, while f(S(n)) computes to the equality type applied to the function argument "hypered" by itself and to f applied to n. The last line basically is a function expecting a value of a type like (27 = (4 = (2 = (1 = ()))))) (for n=4).

Simple Example

f 3 = (27 = (4 = (2 = (1 = ()))))
\$\endgroup\$
  • 1
    \$\begingroup\$ I don't really know Idris, but I think this may fail on a technicality: You're supposed to maximize the length of the type signature of an expression, not the length of its value. Isn't the type signature of your final expression just :Type? \$\endgroup\$ – Ørjan Johansen Mar 24 at 23:48
  • \$\begingroup\$ What do you mean by an uncomputable number? I'm not familiar with hyper; could you explain? \$\endgroup\$ – dfeuer Mar 25 at 8:27
  • \$\begingroup\$ @ØrjanJohansen Oh yes, just fixed that and applied a few more changes \$\endgroup\$ – Mega Man Mar 25 at 14:32
  • 1
    \$\begingroup\$ (0) Explanation seems lagging a bit. (1) This is just 98 bytes now. (2) Since the first argument of hyper gets amplified enormously more than the rest, I think you want all/most of those 99s to be 9s. (3) Assuming Idris's $ works like Haskell's, the outer set of parentheses after f$ is redundant. (4) Could you abbreviate hyper or would that require a type signature itself? \$\endgroup\$ – Ørjan Johansen Mar 25 at 15:51
  • 1
    \$\begingroup\$ @dfeuer en.wikipedia.org/wiki/Hyperoperation (The Idris definition is a direct translation.) \$\endgroup\$ – Ørjan Johansen Mar 25 at 15:58
0
\$\begingroup\$

Haskell, 782

Expression:

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

Type signature:

:: (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
\$\endgroup\$
  • \$\begingroup\$ Becomes 1814 characters with ghc 8.0.2, as the type of sum then is (Num a, Foldable t) => t a -> a \$\endgroup\$ – Mathieu CAROFF Jan 3 at 21:39
0
\$\begingroup\$

Ceylon, 38843546786070481 (~ 4·1016)

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

This are 49 nested one-tuples, with an empty tuple innermost. The short name of this type is actually the same as the value in this case, but the fully expanded name is much longer.

The Ceylon compiler is working forever when trying to compile this (The compiler was still running after 180 minutes) – I'll have to try calculating the theoretical type length.

The problem here is that a one-element-tuple type [X] is actually represented in Ceylon's type system as Tuple<X, X, []> (first parameter is a supertype for all element types, second is the type of the first element, and third the type of all except the first elements, which is here an empty tuple (the empty object, the single instance satisfying the interface Empty)).

So [] is empty, [[]] is Tuple<[], [], []> = Tuple<empty, empty, empty>, [[[]]] is Tuple<[[]], [[]], []> = Tuple<Tuple<[], [], []>, Tuple<[], [], []>, []>. And the full name includes the package names, so we have actually 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> just for three levels. And we want to go to 50.

As ceylon.language::empty is 22 characters long, and each ceylon.language::Tuple<?,?,ceylon.language::empty> adds 47 to twice the result from the previous step, we get f(1) = 22, and f(n) = 2 · f(n-1) + 47. This simplifies to f(n) = 69 · 2^(n - 1) - 47, and entering 50 gives us 38843546786070481. Of course, this is much larger than what would fit in the memory of my computer (8·109 bytes).

Of course, the compiler could be smart and not try to have the whole type name in memory until its name is requested.

Here is the full program trying to print the type:

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

C# (Visual C# Interactive Compiler), 99 bytes, Score 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))))))))))))))))))))))))

Try it online!

Outputs

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]]]]]]]]]]]]]]]]]]]]]]]]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.