[mrkeen]

HM works great for me. Let's try it elsewhere instead of blaming the algorithm!

  {-# LANGUAGE OverloadedStrings #-}          -- Let strings turn into any type defining IsString
  {-# LANGUAGE GeneralizedNewtypeDeriving #-} -- simplify/automate defining IsString 

  import Data.String (IsString)

  main = do

    -- Each of these expressions might be a String or one of the 30 Foo types below
    let address  = "127.0.0.1"
    let username = "steve"
    let password = "1234"
    let channel  = "11"

    let url = "http://" <> username 
                        <> ":"      <> password 
                        <> "@"      <> address 
                        <> "/api/"  <> channel 
                        <> "/picture" 

    print url

  newtype Foo01 = Foo01 String deriving (IsString, Show, Semigroup)
  newtype Foo02 = Foo02 String deriving (IsString, Show, Semigroup)
  -- ... eliding 27 other type definitions for the comment
  newtype Foo30 = Foo30 String deriving (IsString, Show, Semigroup)

Do we think I've captured the combinatorics well enough?

The url expression is 9 adjoining expressions, where each expression (and pair of expressions, and triplet of expressions ...) could be 1 of at least 31 types.

$ ghc --version

  The Glorious Glasgow Haskell Compilation System, version 9.0.2

$ time ghc -fforce-recomp foo.hs

  [1 of 1] Compiling Main             ( foo.hs, foo.o )
  Linking foo ...

  real    0m0.544s
  user    0m0.418s
  sys     0m0.118s

Feels more sluggish than usual, but bad combinatorics shouldn't just make it slightly slower.

I tried compiling the simplest possible program and that took `real 0m0.332s` so who knows what's going on with my setup...

[ash_gti]

Your example is different than the example in the post.

Specifically, `channel = 11`, an integer.

If it was a string then it parses very quickly.

[mrkeen]

If what your saying is true (the type is fixed as an integer), then it's even easier in tfa's case. No inference necessary.

In my code channel is not a string, it's one type of the 31-set of (String, Foo01, Foo02, .., Foo30). So it needs to be inferred via HM.

> If it was a string then it parses very quickly.

"Parses"? I don't think that's the issue. Did you try it?

----- EDIT ------

I made it an Int

  let channel = 11 :: Int

  instance IsString Int where
    fromString = undefined

  instance Semigroup Int where
    (<>) = undefined


  real    0m0.543s
  user    0m0.396s
  sys     0m0.148s

[ash_gti]

The type is an inferred integer literal in swift (in the swift standard this is the `ExpressibleByIntegerLiteral`, the string literals are `ExpressibleByStringLiteral` types).

The reason this causes issues with the type checker is it has to consider all the possible combinations of the `+` operator against all the possible types that can be represented by an inferred integer literal.

This is whats causing the type checker to try every possible combination of types implementing the `+` operator, types implementing `ExpressibleByIntegerLiteral` and `ExpressibleByStringLiteral` in the standard library. That combination produces 59k+ permutations without even looking at non-standard library types.

If any of the types in the expression had an explicit type then it would be type checked basically instantly. Its the fact that none of the values in the expression have explicit types that is causing the type checker to consider so many different combinations.

[mrkeen]

> The reason this causes issues with the type checker is it has to consider all the possible combinations of the `+` operator against all the possible types that can be represented by an inferred integer literal.

Can you please go back and read what I wrote and come up with any plausible alternative explanation for why I wrote the code that I wrote, if not to overload the HM with too many possible types to infer.

> If any of the types in the expression had an explicit type then it would be type checked basically instantly.

Did you try this?

> Its the fact that none of the values in the expression have explicit types that is causing the type checker to consider so many different combinations.

That's what I wrote in my first version. No explicit types. Then I got some comment about it needing to be an Int.

> That combination produces 59k+ permutations without even looking at non-standard library types.

Mine should reject 26439622160640 invalid typings to land on one of 31 possible well-typed readings of this program. (31 ^ 9) - 31.

[ash_gti]

The haskell source has `let channel = "11"` vs `let channel = 11`. The example from the post is an example that looks like it should be pretty straight forward but the swift compiler falls over when you try it.

Trying it locally for example:

  # Original example
  $ time swiftc -typecheck - <<-HERE
  let address = "127.0.0.1"
  let username = "steve"
  let password = "1234"
  let channel = 11
  
  let url = "http://" + username
              + ":" + password
              + "@" + address
              + "/api/" + channel        
              + "/picture"
  
  print(url)
  
  HERE
  <stdin>:6:5: error: the compiler is unable to type-check this expression in reasonable time; try breaking up the expression into distinct sub-expressions
   4 | let channel = 11
   5 | 
   6 | let url = "http://" + username 
     |     `- error: the compiler is unable to type-check this expression in reasonable time; try breaking up the expression into distinct sub-expressions
   7 |             + ":" + password 
   8 |             + "@" + address 
  swiftc -typecheck - <<<''  36.38s user 1.40s system 96% cpu 39.154 total
  
  # Adding a type to one of the expression values
  $ time swiftc -typecheck - <<-HERE
  let address = "127.0.0.1"
  let username = "steve"
  let password = "1234"
  let channel = 11
  
  let url = "http://" + username
              + ":" + password
              + "@" + address
              + "/api/" + String(channel)
              + "/picture"

  print(url)
  
  HERE
  swiftc -typecheck - <<<''  0.11s user 0.03s system 74% cpu 0.192 total

Which is roughly the in line with the numbers in the original post.

[Olreich]

Type checking is horribly slow in Swift if 59k things to check causes 30 seconds of slowdown. That would mean that on a 4ghz processor it requites more than 2 billion operations per check. That’s insane no matter how you slice it.