Flow sensitive type inference

[MainShayne233]

:wave: Hey! Me again.

I ran into an issue where the compiler doesn't seem to be able to resolve a value's type when it's generally matched, but can when it's explicitly matched.

Relevant code:

pub type ParseResult(t) =
  Result(tuple(Parsable, t), Parsable)

pub type Parser(t) =
  fn(Parsable) -> ParseResult(t)

pub fn pair(lhs: Parser(a), rhs: Parser(b)) -> Parser(tuple(a, b)) {
  fn(input: Parsable) {
    case lhs(input) {
      Ok(tuple(lhs_rest, lhs_match)) -> case rhs(lhs_rest) {
        Ok(
          tuple(rhs_rest, rhs_match),
        ) -> Ok(tuple(rhs_rest, tuple(lhs_match, rhs_match)))
        error -> error
      }
      error -> error
    }
  }
}

This code results in the following compiler error:

error: Type mismatch
   ┌─ /home/shayne/gleam/parcomb/src/parcomb.gleam:54:18
   │
54 │         error -> error
   │                  ^^^^^

Expected type:

    Result(tuple(Parsable, tuple(a, b)), c)

Found type:

    Result(tuple(Parsable, b), Parsable)

===> Unable to compile Gleam project

If I change the lines with error -> error to Error(err) -> Error(err), it compiles and works as expected :heart:

Commit with broken code: https://github.com/MainShayne233/parcomb/commit/0be0c4e52a135eb4dfe789e0c8e19afa33d73c34

Commit with working code: https://github.com/MainShayne233/parcomb/commit/bc30f5f3127557f871fb329c8c1f5b8d878be0a9

I'd expect the generic matching (i.e. error -> ...) to work, but maybe this due to a bit of naivety I have about type checking.

P.s. Lemme know if you'd like issues like this to be reported some other way. I don't wanna be an unwanted spammer. :stuck_out_tongue:

[MainShayne233]

Also, just wanted to shout out how fun it's been to write Gleam! Other than some of the sharp edges, I get the same level of satisfaction when writing in other statically typed languages like Elm and Rust. Typically, once the compiler is happy, my tests pass on the first run :heart: :heart: :heart:

[lpil]

A smaller reproduction:

fn run(x: Result(Int, Nil)) -> Result(Float, Nil) {
  case x {
    Ok(_) -> Ok(1.0)
    Error(_) -> x
  }
}

Here Gleam knows that x is a Result(Int, Nil), so it doesn't allow it to be used as a Result(Float, Nil), even if it is in the error case. A smarter compiler would understand that in the error case the type in that branch is Result(anything, Nil), but we can't do that yet.

This might be called Flow-Sensitive Type-Inference? I'm not sure.

This would be a nice little improvement, but it is low priority.

[MainShayne233]

Cool! Thanks for the context. The low priority makes sense given that the workaround isn’t too expensive 🙂