Beginner questions about type classes

Question
41

Ah – yeah, that’s fair, and Scala 3 should help a bit with that.

Haven’t experienced that myself, but it’s certainly plausible. Because the machinery is a bit unobvious, it’s both easy to get something wrong, and sometimes difficult to see what’s failing when it doesn’t work.

42

I have yet another problem with this same piece of code.

scastie type class code

A while back @jducoeur and @sangamon helped to write this type class for me. The idea is that it should work for everything that that foldLeft works for. I’ve just discovered it doesn’t work for Map.

Can someone help me again? I tried to do the simple thing in the code as indicated here, but I get a compiler error. I don’t understand how this is supposed to work, as Map has two type parameters, whereas the other containers the code is defined for only take one type parameter.

object TreeReducible {
    implicit def traversableOnceTreeReducible[T[X] <: scala.collection.GenTraversableOnce[X]]: TreeReducible[T] = new TreeReducible[T] {
    override def foldLeft[A, B](m: T[A])(z: B)(op: (B, A) => B): B = m.foldLeft(z)(op)
  }

  implicit val arrayTreeReducible: TreeReducible[Array] = new TreeReducible[Array] {
    override def foldLeft[A, B](m: Array[A])(z: B)(op: (B, A) => B): B = m.foldLeft(z)(op)
  }
  // I TRIED TO ADD THIS
  implicit val mapTreeReducible: TreeReducible[Map] = new TreeReducible[Map] {
    override def foldLeft[K,V,B](m: Map[K,V])(z:B)(op:(B,(K,V))=>B):B = m.foldLeft(z)(op)
  }
}

Error:(52, 73) Map takes two type parameters, expected: one
  implicit val mapTreeReducible: TreeReducible[Map] = new TreeReducible[Map] {
43

I believe it can’t be done in the generic case, because, as the error says, Map takes a second parameter.

Don’t have time to fully work this right now (somebody else might be able to jump in), but I would try changing the signature to implicit def mapTreeReducible[K]: TreeReducible[Map[K, _]]. (Note that it needs to become implicit def since it now takes a type parameter.)

I’m not 100% confident of the solution here, but the general issue is that you are trying to put a two-parameter block into a one-parameter hole. So you need to fix one of those parameters while leaving the other one to match the X in your T[X].

44

In the general case @jducoeur describes, one might use type lambdas (or, because these are syntactically somewhat tedious, the kind projector compiler plugin) as described in this blog post - it actually uses a Map instance for a single-parameter type class as the motivating example.

This case is different, however. We don’t want to “project” Map to one of its type parameters, we want to use it as a collection of (K, V) tuples - i.e. we already have a TreeReducible instance for Map…

implicitly[TreeReducible[GenTraversableOnce]]
  .foldLeft(Map(1 -> 2))(0)((a, c) => a + c._2)

…it’s just that the compiler doesn’t make the connection and we’ll always have to spell it out.

def foo[M[_] : TreeReducible, A](m: M[A]): Unit = ???
foo[GenTraversableOnce, (Int, Int)](Map(1 -> 2))

I have no idea how to declare an implicit that would be picked up automatically for Map - I’d be really curious.

1 Like