Haskell-like type-constrained trait implementation in Scala (?)

Question

In Haskell you can construct parametrized types as in the following example:

data Tree a = Leaf | Node a (Tree a) (Tree a)

..and afterwards make them an instance of a typeclass if the type parameter is also an instance of the very same typeclass (Eq is used as an example here, it could be anything):

instance (Eq m) => Eq (Tree m) where
  Leaf == Leaf = True
  Node a b c == Node x y z = (a == x) && (b == y) && (c == z)
  _ == _ = False

I am wondering how a similar thing would be possible in Scala. To start let's create the parametrized type:

abstract class Tree[T]
case class Leaf[T]() extends Tree [T]
case class Node[T](value: T, left: Tree[T], right: Tree[T]) extends Tree [T]

..and pick an even simpler trait as the typeclass being implemented:

trait Serializable {
  def toDifferentString(): String
}

Now what I'd like be able to do is provide an implementation of the Serializable trait for Tree, if The T type is Serializable.

I can see a couple of ways of how to do it partially, but none that would get me the Haskell-like result:

• add a type constraint :< in the Tree abstract class, but then it's getting less generic and I'm assuming I can modify the Tree class
• create an implicit conversion from Tree[Serializable] to Serializable, but I'm not even sure it would work and how robust it would be.

What is a good way of approaching the issue?

Answer 1

The type class pattern in Scala works like this:

trait Serializable[-T] {
  def toDifferentString(v: T): String
}

class SerializableTree[T : Serializable] extends Serializable[Tree[T]] {
  def toDifferentString(t: Tree[T]) = t match {
    case Leaf() => ""
    case Node(v, left, right) => 
      val vStr = implicitly[Serializable[T]].toDifferentString(v)
      val lStr = toDifferentString(left)
      val rStr = toDifferentString(right)
      s"Node($vStr, $lStr, $rStr)"
  }
}

object SerializableTree {
  implicit def st[T : Serializable]: Serializable[Tree[T]] = new SerializableTree[T]
}

Type classes in Scala are implemented as a pattern, where the type class provides one or more methods that take as one of their parameters the class for which they are providing these methods.

The notation T : Serializable is a context bound, and is equivalent to an implicit parameter of type Serializable[T]. This implicit parameter is being retrieved by implicitly[Serializable[T]] (the method implicitly[A] return the implicit parameter of type A).

The object SerializableTree contains the necessary definition to produce the serializers for trees, so it has to be imported to be used. Often, common definitions for type classes are put on the object companion of the type class itself, which makes it available without an import.

Because I made Serializable contravariant, a Serializable[Tree[T]] can be used where a Serializable[Node[T]] or Serializable[Leaf[T]] is required.