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?

I'm trying to finally straighten up my Haskell/Scala knowledge, so the help will be much appreciated. Feel free to correct me if any of the terms I used don't mean what I think they mean. — nietaki

Daniel C. Sobral Daniel C. Sobral · Accepted Answer · 2013-09-09T09:56:03

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.

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

1 Answers