Implicit Conversions on Generic Trait

Question

I am implementing a datastructure and want the user to be able to use any type as key as long as he provides a suitable key type wrapping it. I have a trait for this key type. The idea is to have implicit conversions from base to key type and the other way round to (virtually) just use the base type. The trait looks like this:

trait Key[T] extends Ordered[Key[T]] {
  def toBase : T

  // Further stuff needed for datastructure...
}
object Key {
  implicit def key2base[T](k : Key[T]) : T = k.toBase
}

Call site code could look like this:

def foo[K <% Key[K]]( bar : Seq[K] ) = bar.sorted(0)

Plan is that values of type K should be implicitly converted to Key[K] which is ordered or the ordering on Key[K] should be implcitly used, respectively, so everything should work out. Of course, there is no way to implement implicit base2key in the trait itself. Or is there, maybe using implicitly passed class manifests? I could not find any references considering this.

Is it possible to somehow assert statically that any type extending Key[T] will come with an implicit conversion T => Key[T]? The companion object can not have abstract methods, sadly.

Assume this works out, is the entire enterprise feasible or will the stated use case need multiple chained implicit conversions, anyway? (Chaining does not happen, as I have read.)

Addendum: With above definition, I can sort a sequence of Node(key : K, ...) (under K <% Key[K]) by using sortWith(_.key <= _.key), but not using sortBy(_.key). So, obviously, the conversion from K to Key[K] happens implicitly, even though it is never declared anywhere by me, but there is no Ordering on Key[K] available implicitly. What is going on here?

Answer 1

Here is possible solution to your problem (hope I understood your requirements correctly):

// Key stuff

trait Keyable[T] {
  def toKey(t: T): Key[T]
}

trait Key[T] extends Ordered[Key[T]] {
  def toBase() : T
}

object Key {
  implicit def key2base[T](k : Key[T]) : T = k.toBase
  implicit def base2key[T : Keyable](k : T) : Key[T] = implicitly[Keyable[T]].toKey(k)
}

// more concrete stuff - namely A

class A(val i: Int) {
  override def toString = "A {" + i + "}"
}

object A {
  implicit val aKeyable = new Keyable[A] {
    def toKey(t: A) = new Key[A] {
      def toBase() = t
      def compare(that: Key[A]) = t.i compare that.i
    }
  }
}

// testing

def foo[K : Keyable](bar: Seq[K]) = bar.sortBy(implicitly[Keyable[K]].toKey)

val list = List(new A(5), new A(1), new A(3))

println(foo(list)) // prints: List(A {1}, A {3}, A {5})

In this case Key[T] is wrapper for type T and Keyable[T] is type calss that allows to convert type T to Key[T]. I also showed how base2key can look like.

Answer 2

you ask "Is it possible to somehow assert statically that any type extending Key[T] will come with an implicit conversion T => Key[T]? The companion object can not have abstract methods, sadly."

but your example is a static assertion : when you require a view from T to Key[T], you assert at compile time that you may only call foo for types which can be lifted to keys. Or am i misunderstanding something?

regarding the addendum: you say you are surprised that "the conversion from K to Key[K] happens implicitly, even though it is never declared anywhere by me". thing is, you did declare it: T <% Key[T] (I am using T here instead of K, you seem to be mixing up the notion of base *T*ype and *K*ey here?). This is identical to

def foo[T](bar : Seq[T])(implicit view: T => Key[T]) = bar.sortWith(_ <= _)(0)

thus, when you do sortWith(_ <= _) you coerce T into Key[T] (for which <= is defined as per trait Ordered[Key[T]]).

taking your Node example, why not do

case class Node[K](key: K)
def test[K](bar: Seq[Node[K]])(implicit ord: Ordering[K]) = bar.sortBy(_.key)(0)

hope that helps...

Answer 3

In this answer, I will keep the currently best version for reference. Using this answer to more focused question; will be obsolete with 2.9 according to this one.

The Key trait remains unchanged; I add a specific function for illustration:

trait Key[T] extends Ordered[Key[T]] {
  def toBase : T
  def foo(i : Int) : Key[T]
}
object Key {
  implicit def key2base[T](k : Key[T]) : T = k.toBase
  implicit def ordering[T <% Key[T]] = new Ordering[T]{
    def compare(x: T, y: T) = x compare y
  }
}

The following works as expected (if import Key._ is done):

def min[K <% Key[K]](l : Seq[K]) : K = l.sorted.head

Let us assume we have a simple class Node[K](val key : K). Again, things work as expected:

def min[K <% Key[K]](l : Seq[Node[K]]) : Node[K] = l.sortBy(_.key).head

For another example, assume this code using only the Key[T] interface:

def test[K <% Key[K]](bar : Seq[K]) = 
  bar.map(_.foo(3)).sorted

Note that this compiles since map yields a Seq[Key[K]] directly; no conversion needed for sorting. Now, if we have a proper implementation of Key, say

class StringKey(val key : String) extends Key[String] {
  def foo(i : Int) =  StringKey(this.key + "_" + i)
  def toBase = key
  override def compare(other : Key[String]) = -1*this.key.compare(other.toBase)
}
object StringKey {
  def apply(key : String) = new StringKey(key)
  def unapply(key : String) = Some(key)
  implicit def string2key(s : String) = StringKey(s)
}

the following should work:

import StringKey.string2key
import Key.key2base
val bla : Seq[String] = test(Seq("b", "c", "a")).map(_.capitalize)
println(bla)
// expected output: Seq(C_3, B_3, A_3)

But actually, the conversion from StringKey to String is not found:

error: value capitalize is not a member of this.Key[java.lang.String]

This is strange; there is a conversion from Key[String] to String, if declared with a generic type parameter.