CODEWITHSUNDEEP
scalatypeclass
MHOOO
MHOOO

Reputation: 643

How can I write a typeclass in scala on a container type, returning an element from the container?

In the following program, I'm trying to get a typeclass to work. The typeclass is Algo, and the actual implementation for it takes a Container[_ <: Id] and is supposed to return an element from that container. But for some reason the return type of the algo method inside the abstract trait & the implementation function differ, even though they should be the same. Also, the implicit def is not being found for some reason. Anyone can shed some light on what I am doing wrong?

class Element {
}
trait Container[T <: Element] {
    type ElemType = T
    val value : T
}

trait Id {
}

class ElementWithId extends Element with Id

trait Algo[T <: Container[_]] {
    def algo(t : T) : Option[T#ElemType]
}

object Algo {
    implicit def impl[C <: Container[_ <: Id]] = new Algo[C] {
        def algo(cont : C) : Option[C#ElemType] = {
            Some(cont.value)
        }
    }

    implicitly[Algo[Container[ElementWithId]]].algo(new Container[ElementWithId] {
                                                  override val value = new ElementWithId
                                              })
}

The complete error message is:

[error] test.scala:126: type mismatch;
[error]  found   : cont.value.type (with underlying type _$2)
[error]  required: _$2
[error]  Note: implicit method impl is not applicable here because it comes after the application point and it lacks an explicit result type
[error]                 Some(cont.value)
[error]                           ^
[error] test.scala:130: could not find implicit value for parameter e: Algo[Container[ElementWithId]]
[error]         implicitly[Algo[Container[ElementWithId]]].algo(new Container[ElementWithId] {
[error]                   ^
[warn] test.scala:124: inferred existential type $anon forSome { type $anon <: Algo[C]{def algo(cont: C): Option[_$2]}; type _$2 <: Id }, which cannot be expressed by wildcards,  should be enabled
[warn] by making the implicit value language.existentials visible.
[warn] This can be achieved by adding the import clause 'import scala.language.existentials'
[warn] or by setting the compiler option -language:existentials.
[warn] See the Scala docs for value scala.language.existentials for a discussion
[warn] why the feature should be explicitly enabled.
[warn]         implicit def impl[C <: Container[_ <: Id]] = new Algo[C] {
[warn]                                                      ^
[warn] one warning found
[error] two errors found
[error] (Ducktank/compile:compile) Compilation failed
[error] Total time: 1 s, completed 25.04.2013 23:22:17

Update

The solutions provided solve the above Problem, but I have forgotten to specify a requirement - for which I would like to apologize. I would like for Algo to be independent on the kind of Container. With the answers as they are now, I have to know the type bounds on the container type (i.e. that T <: Element), and then basically add the type bounds that Algo requires on top of that (i.e. that T <: Id). But I would like to keep it specific enough, that it would work on a container which has different type bounds (e.g. a Container[T <: SomeOtherElement], instead of a Container[T <: Element]). Is that possible in some way?

Upvotes: 1

Views: 922

Answers (2)

gzm0
gzm0

Reputation: 14842

This compiles:

trait Algo[T, C <: Container[T]] {
    def algo(t : C) : Option[T]
}

object Algo {
    implicit def impl[T <: Id, C <: Container[T]] = new Algo[T,C] {
        def algo(cont : C) : Option[T] = {
            Some(cont.value)
        }
    }

    implicitly[Algo[ElementWithId,Container[ElementWithId]]].algo(new Container[ElementWithId] {
                                                  override val value = new ElementWithId
                                              })
}

Wildchards seem to be somewhat difficult for the compiler to handle. So you can give him a hand :)

Upvotes: 3

Didier Dupont
Didier Dupont

Reputation: 29538

Your first problem is that in your Algo implementation, you return value, which is declared of type T, but expect it to be T#Elem (probably, you mean cont.Elem, which is more precise). The type happens to be the same, but the compiler will not check that. You can start going somewhere if you declare val value: ElemType.

You introduce a lot of complication by having both a type parameter T and a type member ElemType, you should chose one of them, either

trait Container[T <: Element] {
  val value : T // might be wiser to avoid abstract val and prefer abstract def
}

or 

trait Container {
  type Elem  // abstract
  val value: Elem // or def
}

I would rather choose for the first one. With that, the proper writing of Algo would be

trait Algo[C[X <: Element] <: Container[X]] {
  def algo[A <: Element](c: C): Option[A]
}

This supposes you may have to pass an algo somewhere not knowing in advance what will be the type of the content of the containers it will be used on, maybe because it will be used with several different type. Otherwise, just do the simpler

trait Algo[A <: Element, C <: C[A]] {
  def algo(c: C[A]): Option[A]
}

Back to the higher-order Algo[C[X] <: Container[X]], your algo must work without any constraint on the type of content of the container. If you want to be able to restrict that, you might do

trait Algo[R <: ElementType, C[X <: R] <: Container[X]] {
   def algo[A <: R](c: C[A]): Option[A]
}

or 

trait Algo4[R, C[X <: Element with R] <: Container[X]] {
  def algo[A <: Element with R] (c: C[A]) : Option[A]
}

Upvotes: 4

Related Questions