Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Defining implicit view-bounds on Scala traits

I'm doing an exercise to implement a functional binary-search-tree in Scala, following a similar pattern that I've seen used in Haskell. I have a structure that looks something like this:

trait TreeNode[A] {
    def isLeaf: Boolean
    def traverse: Seq[A]
    ...
}

case class Branch[A](value: A, left: TreeNode[A], right: TreeNode[A]) extends TreeNode[A] { 
   def isLeaf: Boolean = false
   def traverse: Seq[A] = ...
   ... 
}

case class Leaf[A]() extends TreeNode[A] { 
    def isLeaf: Boolean = true
    def traverse: Seq[A] = Seq[A]()
    ... 
}

I'd like to put a type constraint on A so that it will only accept objects that extend Ordered. It looks like I need to define a view bound on A ([A <% Ordered[A]]) on Branch and Leaf, as well as the TreeNode trait.. I can't do this on the TreeNode trait, however, because view bounds aren't accepted.

As I understand, <%-style view-bounds are syntactic sugar for an implicit definition, so there should be a way to write to define the bound manually within the TreeNode trait. I'm not sure how I'm supposed to do this, though. I've looked around a bit, but haven't gotten much further than that some sort of implicit needs to be defined.

Can anybody point me in the right direction? Am I approaching this from the wrong angle entirely?

like image 285
KChaloux Avatar asked Jan 23 '13 15:01

KChaloux


People also ask

Can a trait take parameters Scala?

Unlike a class, Scala traits cannot be instantiated and have no arguments or parameters. However, you can inherit (extend) them using classes and objects.

How do you define a trait in Scala?

In scala, trait is a collection of abstract and non-abstract methods. You can create trait that can have all abstract methods or some abstract and some non-abstract methods. A variable that is declared either by using val or var keyword in a trait get internally implemented in the class that implements the trait.

What is context bound in Scala?

Given that background, a context bound is a shorthand syntax for expressing the pattern of, “a context parameter that depends on a type parameter.” Using a context bound, the maximum method can be written like this: def maximum[A: Ord](xs: List[A]): A = xs.reduceLeft(max)

What is a Scala trait when do you use Scala traits?

Traits are used to define object types by specifying the signature of the supported methods. Scala also allows traits to be partially implemented but traits may not have constructor parameters. A trait definition looks just like a class definition except that it uses the keyword trait.


3 Answers

The problem is that view bounds as well as context bounds are just syntactic sugar for specific types of implicit parameters. When applied to a type parameter of a generic class (as opposed to when applied to a generic method), these implicits are added to the constructor of the class. Because traits have no constructor (or rather, only have a single parameterless constructor), there is nowhere to pass these implicit parameters and thus context bounds and view bounds are illegal on generic traits. The simplest solution would be to turn TreeNode into an abstract class.:

abstract class TreeNode[A <% Ordered[A]]

Note that as advised by Ben James, using a context bound with an Ordering is usually better than a view bound with an Ordered (it is more general). However the problem is still the same: won't work on a trait.

If turning TreeNode into a class is not practical (say you need to mix it at various places in the type hierarchy), you can define an abstract method in TreeNode that will provide the implicit value (of type Ordered[A]) and have all the classes that extend it define it. This unfortunately more verbose and explicit, but you can't do much better in this case:

trait TreeNode[A] {
  implicit protected def toOrdered: A => Ordered[A]
}

case class Branch[A<%Ordered[A]](value: A, left: TreeNode[A], right: TreeNode[A]) extends TreeNode[A] { 
   protected def toOrdered = implicitly[A => Ordered[A]]
}

case class Leaf[A<%Ordered[A]]() extends TreeNode[A] { 
    protected def toOrdered = implicitly[A => Ordered[A]]
}

Note that for a more concise definition, you could equivalently define Leaf like this:

case class Leaf[A](implicit protected val toOrdered: A => Ordered[A]) extends TreeNode[A]
like image 134
Régis Jean-Gilles Avatar answered Oct 08 '22 10:10

Régis Jean-Gilles


You could provide the "evidence" that A is Ordered by requiring an abstract member of type Ordered[A] on the trait:

trait TreeNode[A] {
  implicit val evidence: Ordered[A]
}

You would then be forced to provide this in any concrete subtypes, this proving that A is Ordered:

case class Leaf[A](value: A)(implicit ev: Ordered[A]) extends TreeNode[A] {
  val evidence = ev
}

You might instead want to constrain A to a type which has an implicit Ordering[A] - this is not an inheritance relationship; it is more like a haskell typeclass. But the implementation in terms of the above technique would be the same.

like image 22
Ben James Avatar answered Oct 08 '22 11:10

Ben James


@ben-james's answer is great, I would like improve it a bit to avoid redundant vals in classes.

The idea is to define implicit constructor parameter name the same as it is defined in trait that holds implicit value.

The idea is to avoid this line:

val evidence = ev

Here is a complete example (gist)

trait PrettyPrinted[A] extends (A => String)

object PrettyPrinted {
  def apply[A](f: A => String): PrettyPrinted[A] = f(_)
}

trait Printable[A] {
  implicit def printer: PrettyPrinted[A]
}

// implicit parameter name is important
case class Person(name: String, age: Int)
                 (implicit val printer: PrettyPrinted[Person])
  extends Printable[Person]

object Person {
  implicit val printer: PrettyPrinted[Person] =
    PrettyPrinted { p =>
      s"Person[name = ${p.name}, age = ${p.age}]"
    }
}

// works also with regular classes
class Car(val name: String)
         (implicit val printer: PrettyPrinted[Car])
  extends Printable[Car]

object Car {
  implicit val printer: PrettyPrinted[Car] =
    PrettyPrinted { c =>
      s"Car[name = ${c.name}]"
    }
}
like image 30
Andrii Abramov Avatar answered Oct 08 '22 12:10

Andrii Abramov