[temp123789246]

Does anyone know why, anecdotally, it seems like the slowness of type inference is more of a pain point in Swift than in Ocaml, Rescript, Purescript, Haskell, etc?

[tines]

Is it that Haskell, at least, doesn't support overloading in the same way as Swift? I don't know either of them well enough to be sure.

It seems like there's a combinatorial explosion of possible overloads in Swift, whereas if you implement a function with the same ergonomics in Haskell (e.g. a printf-like function), the only thing the compiler has to do is ask "Does type X have an implementation for typeclass Show? Yes? Done."

Essentially Haskell solved this overload inference problem in the same way that iterators solve the M*N problem for basic algorithms: convert all these disparate types to a single type, and run your algorithm on that.

[ackfoobar]

"Does type X have an implementation for typeclass Y" isn't always easy to answer.

https://aphyr.com/posts/342-typing-the-technical-interview

[tines]

That post, while awesome (as is the rest of aphyr's stuff), is a lot to wade through to get to the point you're trying to convey. Can you spell it out for me?

[ackfoobar]

That typeclass resolution can encode some heavy computation, the example being n-queens in the article.

[tines]

That's only the case when you turn on the "enable arbitrary computation in typeclasses" flag, so I'd say it's not much of a worry.

[steinuil]

I'm not an expert on the theory, but OCaml has a very fast compiler and while it is (almost) capable of fully reconstructing the types from a program with no annotations, it doesn't have to deal with ad-hoc polymorphism and takes some shortcuts like weak polymorphism when it gets too hard: https://www.ocaml.org/manual/5.2/polymorphism.html

[fweimer]

Try this:

    let f0  = fun x -> (x, x) in
        let f1  = fun y -> f0(f0 y) in
        let f2  = fun y -> f1(f1 y) in
        let f3  = fun y -> f2(f2 y) in
        let f4  = fun y -> f3(f3 y) in
        let f5  = fun y -> f4(f4 y) in
        f5 (fun z -> z)

Lifted from https://dl.acm.org/doi/pdf/10.1145/96709.96748 via Pierce, Types And Programming Languages.

[_flux]

But that's just a type that is huge. I didn't want to wait for the evaluation, but if I drop the f5 out, I got a type that is 1.6 megabytes long when printed without spaces.

It's still very fast for "normal size" types. That reduced version compiles in 151 milliseconds.

[tombert]

Wait what? In Haskell the types are usually directly inferrable from the arguments they're being used as, and when you put a type annotation it's usually not explicit types (Num a => a -> b -> c).

I almost never bother putting types in Haskell, unless I want to guarantee some constraint, in which case I typically use typeclasses. Maybe I'm just weird but I don't think so. One of the very few things I actually like about Haskell is how good the type inference is.

[nyrikki]

My guess is different extensions to Hindley–Milner type system, which is EXPTIME-complete in the worst case.

HM isn't bidirectional in the special case, so probably the features they added vs the top level universal quantifier type that has pathological low time complexity.