Hacker News Reader

Comment by emptysea | Hacker News Reader

Helpful explanation. I think a lot of the trouble for me in understanding GADTs is the Haskell syntax used in a lot of examples.

My static typing experience is limited to TypeScript and Rust, so I'm curious what a GADT would look like if they were added to those languages.

View on HN

Here's all the code from the parent in Rusty pseudosyntax:

    enum MyRecord {
      ConstructorName(Int, String, Bool)
    }

    enum TrafficLight {
      Red,
      Yellow,
      Green
    }

    enum AST {
      Integer(Int),
      Boolean(Bool),
      Addition(Ast, Ast),
      Multiplication(Ast, Ast),
      Equals(Ast, Ast),
      Not(Ast)
    }

`Not(Equals(Integer(1), Integer(2))) : AST`

    enum IntErr {
      Error(String),
      IntResult(Int)
    }

    enum StringErr {
      Error(String),
      StringResult(String)
    }

    enum WithError<A> {
      Error(String),
      Result(A)
    }

`Result(3) : WithError<Int>` `Result(True) : WithError<Bool>`

    enum Weird<A, B> {
      IgnoreTheType(Int),
    }

`Weird<String, Bool>` `IgnoreTheType(1) : Weird<String, Bool>` `IgnoreTheType(2) : Weird<Char, Float>` `IgnoreTheType(3) : Weird<Bool, Double>`

`Addition(Boolean(True), Not(Integer(3)))`

    enum AST<R> {
      Integer(Int),
      Boolean(Bool),
      Addition(Ast<Int>, Ast<Int>),
      Multiplication(Ast<Int>, Ast<Int>),
      Equals(Ast<R>, Ast<R>),
      Not(Ast<Bool>)
    }

Finally, we get our GADT:

    enum AST<R> {
      Integer(Int) : Ast<Int>,
      Boolean(Bool) : Ast<Bool>,
      Addition(Ast<Int>, Ast<Int>) : Ast<Int>,
      Multiplication(Ast<Int>, Ast<Int>) : Ast<Int>,
      Equals(Ast<R>, Ast<R>) : Ast<Bool>,
      Not(Ast<Bool>) : Ast<Bool>
    }

Thanks lalaithion! I don’t know Rust, so it’s interesting to see how different it is compared to Haskell.

A question: how much of this would actually compile in Rust?

- Assuming `Int` and `Bool` are user-defined types (Rust has `bool` and many types of ints like `usize`, `i64`, etc. instead). If you want to work over ANY primitive integer you can use the `num_traits` crate and make your type generic over `num_traits::PrimInt`, or even `num_integer::Integer` to include support for crates such as `num_bigint`.

- Rust needs indirection for recursive data types (like the AST) using `Box`, references, or another kind of indirection. Otherwise, the size isn't known at compile time (since it's potentially infinite).

- Rust doesn't have GADTs (yet?) so the last AST is purely theoretical.

- `IgnoreTheType` (and `AST<R>`) would require explicit use of `PhantomData` for variants without `R` https://doc.rust-lang.org/std/marker/struct.PhantomData.html

On Rust's playground: https://play.rust-lang.org/?version=stable&mode=debug&editio...

Thank you! So it looks like most of my post does indeed work, except for the GADT itself.

(Also, I had not known about Rust Playground, so thanks for introducing me to that too.)

Reply on news.ycombinator.com