Best way to use type classes with list parametrized with some base class, abstract class or trait

Question

I think it would be easier to describe a problem with concrete example. Suppose I have have Fruit class hierarchy and Show type class:

trait Fruit
case class Apple extends Fruit
case class Orange extends Fruit

trait Show[T] {
    def show(target: T): String
}

object Show { 
    implicit object AppleShow extends Show[Apple] {
        def show(apple: Apple) = "Standard apple"
    }

    implicit object OrangeShow extends Show[Orange] {
        def show(orange: Orange) = "Standard orange"
    }
}

def getAsString[T](target: T)(implicit s: Show[T]) = s show target

I also have list of fruits that I would like to show to the user using Show (this is my main goal in this question):

val basket = List[Fruit](Apple(), Orange())

def printList[T](list: List[T])(implicit s: Show[T]) = 
    list foreach (f => println(s show f))

printList(basket)

This will not compile because List is parametrized with Fruit and I have not defined any Show[Fruit]. What is the best way to achieve my goal using type classes?

I tried to find solution for this problem, but unfortunately have not found any nice one yet. It's not enough to know s in printList function - somehow it needs to know Show[T] for each element of the list. This means, that in order to be able to make this, we need some run-time mechanism in addition to the compile-time one. This gave me an idea of some kind of run-time dictionary, that knows, how to find correspondent Show[T] at run-time.

Implementation of implicit Show[Fruit]can serve as such dictionary:

implicit object FruitShow extends Show[Fruit] {
    def show(f: Fruit) = f match {
        case a: Apple => getAsString(a)
        case o: Orange => getAsString(o)
    }
}

And actually very similar approach can be found in haskell. As an example, we can look at Eq implementation for Maybe:

instance (Eq m) => Eq (Maybe m) where  
    Just x == Just y = x == y  
    Nothing == Nothing = True  
    _ == _ = False  

The big problem with this solution, is that if I will add new subclass of Fruit like this:

case class Banana extends Fruit

object Banana {
    implicit object BananaShow extends Show[Banana] {
        def show(banana: Banana) = "New banana"
    }
}

and will try to print my basket:

val basket = List[Fruit](Apple(), Orange(), Banana())

printList(basket)

then scala.MatchError would be thrown because my dictionary does not know anything about bananas yet. Of course, I can provide updated dictionary in some context that knows about bananas:

implicit object NewFruitShow extends Show[Fruit] {
    def show(f: Fruit) = f match {
        case b: Banana => getAsString(b)
        case otherFruit => Show.FruitShow.show(otherFruit)
    }
}

But this solution is far from perfect. Just imagine that some other library provides another fruit with it's own version of dictionary. It will just conflict with NewFruitShow if I try to use them together.

Maybe I'm missing something obvious?

---

Update

As @Eric noticed, there is one more solution described here: forall in Scala . It's really looks very interesting. But I see one problem with this solution.

If I use ShowBox, then it will remember concrete type class during it's creation time. So I generally building list with objects and correspondent type classes (so dictionary in present in the list). From the other hand, scala has very nice feature: I can drop new implicits in the current scope and they will override defaults. So I can define alternative string representation for the classes like:

object CompactShow { 
    implicit object AppleCompactShow extends Show[Apple] {
        def show(apple: Apple) = "SA"
    }

    implicit object OrangeCompactShow extends Show[Orange] {
        def show(orange: Orange) = "SO"
    }
}

and then just import it in current scope with import CompactShow._. In this case AppleCompactShow and OrangeCompactShow object would be implicitly used instead of defaults defined in the companion object of Show. And as you can guess, list creation and printing happens in different places. If I will use ShowBox, than most probably I will capture default instances of type class. I would like to capture them at the last possible moment - the moment when I call printList, because I even don't know, whether my List[Fruit] will ever be shown or how it would be shown, in the code that creates it.

Answer 1

The most obvious answer is to use a sealed trait Fruit and a Show[Fruit]. That way your pattern matches will complain at compile time when the match is not exhaustive. Of course, adding a new kind of Fruit in an external library will not be possible, but this is inherent in the nature of things. This is the "expression problem".

You could also stick the Show instance on the Fruit trait:

trait Fruit { self =>
  def show: Show[self.type]
}

case class Apple() extends Fruit { self =>
  def show: Show[self.type] = showA
}

Or, you know, stop subtyping and use type classes instead.