trait Expr[A]We can define an evaluation function with the type

case class I(i: Int) extends Expr[Int]

case class B(b: Boolean) extends Expr[Boolean]

case class Add(a: Expr[Int], b: Expr[Int]) extends Expr[Int]

`Expr[A] => A`

:def eval[A](e: Expr[A]): A = e match {This all compiles and typechecks, and has the expected behavior:

case I(i) => i

case B(b) => b

case Add(a,b) => eval(a) + eval(b)

}

`Add(I(1), B(false))`

is a type error, `eval(I(22))`

results in 22, etc.I haven't played with this much, so I wonder if there's any situations where the Scala GADTs behave differently than Haskell's.

## 5 comments:

Not quite. Scala does not do type refinement. For example, contrast:

trait Eq[A,B]

case class Refl[A]() extends Eq[A,B]

object Main {

def eval[A](a : A, eq : Eq[A,Int]) : A = eq match {

case Refl() => 1 + a

}

}

Versus:

data Equal a b where

Refl :: Equal a a

eval :: a -> Equal a Int -> a

eval x Refl = 1 + x

@Luke - did you mean for Refl[A] to extend Eq[A,A] in your Scala example?

Ah, yes I did, thanks. It still doesn't compile.

@Luke - Hmm... interesting. Thanks for the comment. I'm trying to figure out how limiting this is... can you provide a more illustrative example or maybe just talk about how that facility gets used in Haskell?

There's a nice paper, "Generalized algebraic data types and object-oriented programming," that looks at this kind of encoding in more detail:

http://research.microsoft.com/en-us/um/people/akenn/generics/gadtoop.pdf

Post a Comment