Scala type bounds not inferred correctly in match statement

Question

I have a case-class that takes arguments with a bounded type, however when using the case-class extractor the type system appears to be losing the bounds and inferring 'Any' instead.

For example:

trait Expr[T]

case class IntLit(value:Int) extends Expr[Int]
case class GreaterThan[T <% Ordered[T]]( a:Expr[T], b:Expr[T] ) extends Expr[Boolean]

object TestRuntime {
    def execute[T]( expr:Expr[T] ):T = expr match {
        case IntLit(value)    => value

        // ---> This line fails because the compiler thinks a and b are Expr[Any]
        //      Instead of Expr[_ <% Ordered[_]]
        //      error: value > is not a member of Any
        case GreaterThan(a,b) => execute(a) > execute(b) 

        // ---> Whereas this line works correctly.
        /// EDIT: Actually, no it doesn't, it throws a ClassCastException!
        ///       T is Boolean,
        ///       Whereas we're expecting a new type U <: Ordered[U]
        case gt:GreaterThan[T] => execute(gt.a) > execute(gt.b)
    }
}

Is this simply a limitation of Scalas type inference, or am I missing something?

I've also attempted to achieve the same result using the Ordering[T] typeclass using a context bounds (This would be preferable)

case class GreaterThan[T : Ordering]( a:Expr[T], b:Expr[T] )

However I can't figure out how to access the typeclass instance inside the match{} block without adding a method to GreaterThan itself (Which somewhat defeats the point of using a typeclass for this purpose.)

Effectively, what I'm trying to do is port this Haskell to Scala

{-# LANGUAGE GADTs #-} 
data Expr a where
    StringLit   :: String  -> Expr String
    IntLit      :: Int     -> Expr Int
    Equals      :: (Eq a)  => (Expr a) -> (Expr a) -> Expr Bool
    GreaterThan :: (Ord a) => (Expr a) -> (Expr a) -> Expr Bool

runExpr :: Expr a -> a
runExpr (IntLit i)        = i
runExpr (StringLit s)     = s
runExpr (Equals a b)      = (runExpr a) == (runExpr b)
runExpr (GreaterThan a b) = (runExpr a) >  (runExpr b)

Answer 1

There are two issues getting in the way, one with the scoping of view and context bounds, the other with type erasure.

1. Scoping

These:

case class GreaterThan[T <% Ordered[T]]( a:Expr[T], b:Expr[T]) extends Expr[Boolean]
case class GreaterThan[T : Ordering]( a:Expr[T], b:Expr[T]) extends Expr[Boolean]

Are syntactic sugar for:

case class GreaterThan[T]( a:Expr[T], b:Expr[T])(implicit evidence: T => Ordered[T]) extends Expr[Boolean]
case class GreaterThan[T]( a:Expr[T], b:Expr[T])(implicit ordering: Ordering[T]) extends Expr[Boolean]

The implicit parameters are scoped inside of the case class and aren't accessible outside, as you discovered when you tried a solution with Ordering. Inside of your match statement, it can't get at the > from Ordered[T].

2. Type Erasure

With this statement:

case GreaterThan(a,b) => execute(a) > execute(b)

At run-time the code can discover that the Expr being matched on is a GreaterThan, however because of type erasure there is no way for it to know what the type parameter for this particular GreaterThan is. Even if it could, this wouldn't take it very far, because views and context bounds are resolved statically - all the work is done at compile-time. With the solution with Ordered, the compiler has to find an appropriate T => Ordered[T] to pass to the constructor of GreaterThan at compile-time. None of that resolution can happen at run-time inside of execute however, and the same T => Ordered[T] might not even be in scope.

3. Solution

There isn't any way to fix this without exposing the implicit outside of GreaterThan. You could do:

case class GreaterThan[T]( a:Expr[T], b:Expr[T])(implicit val ordering: Ordering[T]) extends Expr[Boolean]

The val in front of ordering will make it accessible outside.

Then in the match:

case gt: GreaterThan[_] => gt.ordering.gt(execute(gt.a), execute(gt.b))

We don't know what the type parameter for the GreaterThan is at this point, but we do know that both subexpressions and the Ordering are parameterized with the same type, and so we can safely do the comparison.

My knowledge of Haskell's internals aren't as deep, but I believe generic types actually carry a reference to a table holding the methods for their typeclasses. We are doing the same thing here with Scala, but we have to explicitly pass around the type class object.

Another solution would be to use the Visitor pattern, but that would take you even farther from the original Haskell.