CODEWITHSUNDEEP
scalaimplicit-conversion
marius_neo
marius_neo

Reputation: 1595

Scala implicit conversions and parameters

I'm trying to solve an exercise from the book Scala by example , chapter 15 Implicit Parameters and Conver- sions which can be found here :

and have the following code sample : 

object DemoImplicitConversions {
  def main(args: Array[String]) {
    val xs = List(new Num(1), new Num(4), new Num(2), new Num(6),new Num(3))
    val sortedXs = sort(xs)(num2ordered)
    print(sortedXs.mkString(","))
  }

  type OrderedView[A] = A => Ordered[A]

  // View bound : [A <% Ordered[A]] - means that sort is applicable to lists of type A such that there exists an
  // implicit conversion from A to Ordered[A]

  def sort[A: OrderedView](xs: List[A])(c: OrderedView[A]): List[A] =
    if (xs.isEmpty || xs.tail.isEmpty) xs
    else {
      val (ys, zs) = xs.splitAt(xs.length / 2)
      merge(ys, zs)(c)
    }

  def merge[A: OrderedView](xs: List[A], ys: List[A])(c: OrderedView[A]): List[A] =
    if (xs.isEmpty) ys
    else if (ys.isEmpty) xs
    else if (c(xs.head) < ys.head) xs.head :: merge(xs.tail, ys)(c)
    else ys.head :: merge(xs, ys.tail)(c)

  implicit def num2ordered(x: Num): Ordered[Num] = new Ordered[Num] {
    override def compare(y: Num): Int =
      if (x.value < y.value) -1
      else if (x.value > y.value) 1
      else 0

  }
}

case class Num(value: Int)  {
  override def toString: String = value.toString
}

Unfortunately I don't find a way to have implicitly the converter assigned to the method sort so that the client code can look like :

def main(args: Array[String]) {
    val xs = List(new Num(1), new Num(4), new Num(2), new Num(6),new Num(3))
    val sortedXs = sort(xs)
    printList(sortedXs)
  }

If I add the implicit keyword for the converter parameter of the methods merge and sort I get

ambiguous implicit values

compilation error message.

Upvotes: 2

Views: 208

Answers (2)

Ben Reich
Ben Reich

Reputation: 16324

The type constraint you're placing on A is called a context bound. As you correctly write in your comment, A : OrderedView means that there is available an implicit value of A[OrderedView]. Your mistake is how you try to get that instance. You wrote the method signature as:

def merge[A: OrderedView](xs: List[A], ys: List[A])(c: OrderedView[A]): List[A]

But when using a context bound, it should be:

def merge[A: OrderedView](xs: List[A], ys: List[A]): List[A]

And then use the implicitly operator to get the instance you want. So your methods could look like:

def sort[A: OrderedView](xs: List[A]): List[A] = (merge _).tupled(xs.splitAt(xs.length / 2))

def merge[A: OrderedView](xs: List[A], ys: List[A]): List[A] = {
  //This is how we get the c instance      
  val c = implicitly[OrderedView[A]] 
  ...
}

Your other option is to get rid of the context view and use an implicit parameter instead (and then don't use implicitly in the method body):

def merge[A](xs: List[A], ys: List[A])(implicit c: OrderedView[A]): List[A]

These are exactly equivalent. In fact, the context bound is basically translated into this version during compilation. What you had was mixing these idioms, by using a context bound and using another parameter list (although yours was not implicit, which is required).

In your example, you don't even need an explicit instance of OrderedView[A]. Since it is available in implicit scope (as guaranteed by the context bound), it is automatically applied when necessary. So, you can even simplify things further:

def merge[A: OrderedView](xs: List[A], ys: List[A]): List[A] =
    if (xs.isEmpty) ys
    else if (ys.isEmpty) xs
    //Here, the implicit conversion occurs on xs.head
    else if (xs.head < ys.head) xs.head :: merge(xs.tail, ys)
    else ys.head :: merge(xs, ys.tail)

Also, you could use a view bound here, instead of the context bound. Then, you don't even need to introduce the OrderedView type alias:

def sort[A <% Ordered[A]](xs: List[A]): List[A]
def merge[A <% Ordered[A]](xs: List[A], ys: List[A]): List[A]
//Or, equivalently:
def sort[A](xs: List[A])(implicit ev: A => Ordered[A]): List[A]
def merge[A](xs: List[A], ys: List[A])(implicit ev: A => Ordered[A]): List[A]

Read more about context bounds (and view bounds) here.

As an unrelated note, you should also explore using match statements, which are pretty powerful in Scala:

def merge[A <% Ordered[A]](xs: List[A], ys: List[A]): List[A] = (xs, ys) match {
      case (Nil, _) => ys
      case (_, Nil) => xs
      case (xhd::xtl, yhd::ytl) if xhd < yhd => xhd :: merge(xtl, ys)
      case (_, yhd::ytl) => yhd :: merge(xs, ytl)
}

Upvotes: 4

Vladimir Matveev
Vladimir Matveev

Reputation: 127711

This definition:

def sort[A: OrderedView](xs: List[A])(c: OrderedView[A]): List[A]

is in fact equivalent to this:

def sort[A](xs: List[A])(c: OrderedView[A])(implicit ev: OrderedView[A]): List[A]

That is, your c: OrderedView[A] parameter is absolutely independent on the context bound, it is just another parameter.

You just need either to omit the context bound:

def sort[A](xs: List[A])(implicit c: OrderedView[A]): List[A]

or omit the parameter:

def sort[A: OrderedView](xs: List[A]): List[A]

In the latter case, however, if you want to access the implicit parameter you will have to do it with implicitly:

implicitly[OrderedView[A]](xs.head)

Maybe you won't even need to call it explicitly as an implicit conversion will fire automatically.

Upvotes: 1

Related Questions