CODEWITHSUNDEEP
scalatypeclass
sarveshseri
sarveshseri

Reputation: 13985

Unable to define typeclass

I am trying to create a typeclass which adds sorted-merge functionality to lists.

trait SortedMerge[A, B[A] <: List[A]] {
  def sortedMerge(l1: B[A], l2: B[A]): B[A]
}

implicit val IntSortedMerge = new SortedMerge[Int, List[Int]] {
  override def sortedMerge(l1: List[Int], l2: List[Int]): List[Int] = {
    @tailrec
    def merge(l1: List[Int], l2: List[Int], l: List[Int]): List[Int] = {
      (l1, l2) match {
        case (Nil, Nil) => l
        case (Nil, _) => l ++ l2
        case (_, Nil) => l ++ l1
        case (h1 :: t1, h2 :: t2) if (h1 < h2) => merge(t1, l2, l :+ h1)
        case (h1 :: t1, h2 :: t2) => merge(l1, t2, l :+ h2)
      }
    }

    merge(l1, l2, List[Int]())
  }
}


def sortedMerge[A, List[A]](l1: List[A], l2: List[A])
  (implicit merger: SortedMerge[A, List[A]]) = merger.sortedMerge(l1, l2)

I am getting the following error,

error: List[Int] takes no type parameters, expected: one
   val IntSortedMerge = new SortedMerge[Int, List[Int]] {
                                             ^

What am I doing wrong here?

Upvotes: 1

Views: 67

Answers (2)

charlie
charlie

Reputation: 1527

This compiles fine: 

trait SortedMerge[A, B <: List[A]] {
  def sortedMerge(l1: B, l2: B): B
}

implicit val IntSortedMerge = new SortedMerge[Int, List[Int]] {
    // ... omitted
}

def sortedMerge[A, B <: List[A]](l1: B, l2: B)
    (implicit merger: SortedMerge[A, B]) = merger.sortedMerge(l1, l2)

Usage: 

println(sortedMerge[Int, List[Int]](List(2, 4), List(1, 3)))

Prints: 

List(1, 2, 3, 4)

Upvotes: 1

vsminkov
vsminkov

Reputation: 11270

The reason you are getting this error is because of this bound [A, B[A] <: List[A]]. Second type parameter should be higher-kinded type. So your code cold be rewritten in this way

import scala.language.higherKinds

val IntSortedMerge = new SortedMerge[Int, List] {
  // stuff
}

def sortedMerge[A](l1: List[A], l2: List[A])
  (implicit merger: SortedMerge[A, List]) = merger.sortedMerge(l1, l2)

EDIT

In your case you can actually drop second type parameter because you are expecting (?) only lists:

trait SortedMerge[A] {
  def sortedMerge(l1: List[A], l2: List[A]): List[A]
}

val IntSortedMerge = new SortedMerge[Int] {
  // stuff
}

def sortedMerge[A](l1: List[A], l2: List[A])
  (implicit merger: SortedMerge[A]) = merger.sortedMerge(l1, l2)

But you also can weaken bound to something like [A, B[A] <: Seq[A]] which will allow you to build SortedMerge for any Seq subclass.

Upvotes: 2

Related Questions