Common practice for higher-order-polymorphism in scala

Question

Hi,

I'm trying to grasp higher-order-polymophism in scala by implementing a very basic interface that describes a monad but I come across a problem that I don't really understand.

I implemented the same with C++ and the code looks like this:

#include <iostream>

template <typename T>
class Value {
private:
  T value;
public:
  Value(const T& t) {
    this->value = t;
  }

  T get() {
    return this->value;
  }
};

template < template <typename> class Container >
class Monad {
public:
  template <typename A> Container<A> pure(const A& a); 
};

template <template <typename> class Container>
  template <typename A>
Container<A> Monad<Container>::pure(const A& a) {
  return Container<A>(a);
}

int main() {
  Monad<Value> m;
  std::cout << m.pure(1).get() << std::endl;
  return 0;
}

When trying to do the same with scala I fail:

class Value[T](val value: T)

class Monad[Container[T]] {
  def pure[A](a: A): Container[A] =
    Container[A](a)
}

object Main {
  def main(args: Array[String]): Unit = { 
    val m = new Monad[Value]
    m.pure(1)
  }
}

The compiler complains about:

[raichoo@lain:Scala]:434> scalac highorder.scala
highorder.scala:5: error: not found: value Container
    Container[A](a)
    ^
one error found

What am I doing wrong here? There seems to be a fundamental concept I don't seem to understand about scala typeconstructors.

Regards, raichoo

Answer 1

Not sure what would be the best solution, but in the definition of pure in your code:

class Monad[Container[T]] {
  def pure[A](a: A): Container[A] = Container[A](a)
}

What Container[A](a) should do? So far, you've defined Container as a generic type XXX and you don't have any information on how to build a new object. You need to pass a "builder" object as implicit parameter. Take a look at how the collection libraries are implemented in Scala 2.8 or the Monad definition in Scalaz

Answer 2

If you change your definition of the Monad class to the following

class Monad[Container[_]] {        
  def pure[A <% Container[A]](a: A): Container[A] = a
}

The syntax Container[_] is how higher kinds are expressed in Scala. The A <% Container[A] is a 'view bound' that expresses that A is implicitly convertible to Container[A]. The body of the method uses this implicit conversion. To use this class, you need to have an implicit conversion in scope for (in your example) Int to Value[Int]

implicit def toValue[T](t:T) = new Value(t)

You can then do the following

scala> val m = new Monad[Value]                     
m: Monad[Value] = Monad@781fb069

scala> m.pure(1).value         
res3: Int = 1

Answer 3

The Monad trait in Scala would be declared as follows:

trait Monad[M[_]] {
  def pure[A](a: => A): M[A]
  def bind[A,B](a: M[A], f: A => M[B]): M[B]
}

Note that it's parameterized with a type constructor M[_]. The bracketed underscore indicates that M is a type constructor of kind (* -> *) (i.e. M takes some type A to construct a type M[A]). Your identity monad instance would then be written like this:

class Value[A](a: => A) { lazy val value = a }

implicit val identityMonad = new Monad[Value] {
  def pure[A](a: => A) = new Value(a)
  def bind[A,B](a: Value[A], f: A => Value[B]) = new Value(f(a.value).value)
}

This definition uses by-name parameters to achieve lazy semantics.

Monad and other useful higher-kinded type classes are provided by the Scalaz library along with a lot of instances for the standard Java/Scala libraries.