Can someone help me understand the illegal start of definition error in Scastie?
When I run this code in IntelliJ I get a very different error about an implicit. I was trying to copy the code to Scastie, to ask a question about the implicit error.
Error:(38, 62) could not find implicit value for parameter pairable: treereduce.TreeParallelReduce.Pairable[List]
println("result Nil List = " + pairMapReduce(List[Int]())(init = 0, id, addInt))
You can’t use package in Scastie.
Scastie wraps its code in an object, and a package declaration inside an object is invalid.
In Scastie, worksheet mode is enabled by default. which doesn’t allow package statements. There’s a button in the top toolbar to disable it. You’ll also have to change the build settings to Scala 2.12 for the imports to work.
Regarding the implicit-not-found error: Your code does not define a Pairable[List]. The other Pairable instances for supertypes like the Pairable[Seq] do not apply, because Pairable isn’t covariant in F. You also cannot make it covariant, because F is used in argument types. I don’t know any simple solution that doesn’t require implementing it for every Seq subclass you want to use. If you use cats (or another fp library), you can use the existing instances for Functor and Foldable:
implicitly def genPairable[F[_]:Foldable:Functor]: Pairable[F] = new Pairable[F] {
override def map[A, B](p: F[A], f: A => B): F[B] = Functor[F].map(p)(f)
override def foldLeft[A, B](p: F[A], z: B)(f: (B, A) => B): B = Foldable[F].foldLeft(p, z)(f)
}
or even just require Foldable and Functor in pairMapReduce instead of Pairable and define the paired method with the Foldable dependency:
def paired[A, B, F[_] : Foldable](tree: F[A], f: A => B): (List[(B, B)], Option[B]) = {
val none: Option[B] = None
val nil: List[(B, B)] = Nil
Foldable[F].foldLeft(tree, (nil, none)) {
case ((stack: List[(B, B)], Some(b: B)), a: A) => (((b, f(a)) :: stack), none)
case ((stack: List[(B, B)], None), a: A) => (stack, Some(f(a)))
} match {
case (stack, leftover) => (stack.reverse, leftover)
}
}
The latter solution doesn’t require an additional typeclass to be defined, but has the drawback, that cats doesn’t provide instances for mutable data types.
Another thing that will probably cause problems is your instance for Array, because Arrays aren’t using type parameters on the JVM (although they look that way in Scala). This means, that you cannot create an Array of a generic type, which is why
def map[A, B](a:Array[A])(f: A => B): Array[B] = a.map(f) will give a compiler error, because map will return an ArraySeq. Creating an Array[B] requires an implicit ClassTag[B], but that would no longer be compatible with your signature in the typeclass. So you probably can’t have the same implementation for Arrays and other collection types.
Very interesting.
I tried changing
implicit val seqPairable: Pairable[Seq] = new Pairable[Seq] {
override def map[A, B](seq: Seq[A], f: A => B): Seq[B] = seq.map(f)
override def foldLeft[A, B](seq: Seq[A], z: B)(f: (B, A) => B): B = seq.foldLeft(z)(f)
to
implicit def seqPairable[T[X] <: Seq[X]]: Pairable[T] = new Pairable[T] {
override def map[A, B](seq: T[A], f: A => B): T[B] = seq.map(f)
override def foldLeft[A, B](seq: T[A], z: B)(f: (B, A) => B): B = seq.foldLeft(z)(f)
}
and commented out the Array stuff for the moment.
updated Scastie
That seems to get me a bit closer. But still doesn’t work. The error is that Seq[B] was found where T[B] was expected. Is this the contravariance problem?
type mismatch;
found : Seq[B]
required: T[B]
Looks like it, yeah. Consider: you’re returning the result of seq.map(), which is a Seq[B]. But your function definition says that you should be returning T[B] – a specific subtype of Seq[B]. So basically, the compiler has no way to know that it’s the right subclass of Seq.
I think you’re intuitively expecting T.map() to return T[B]. But that’s not the way Seq is defined – it just says that map() returns a Seq type, but not necessarily the same type…
It’s the problem that the signature of map on Seq returns a Seq, not a specific subtype of Seq. That’s the way the collections are designed. You can try something like def map[A, B](seq: T[A], f: A => B)(implicit bf: CanBuildFrom[Seq[A], B, T[B]]): T[B] = seq.map(f)(bf) It’s really complicated. See https://www.scala-lang.org/blog/2017/05/30/tribulations-canbuildfrom.html for some background.
CanBuildFrom ? Is this the motivation for all the talk about removing all references to CanBuildFrom in Dotty?
CanBuildFrom was actually already removed with the collection rework in 2.13, so this may work differently / better with 2.13, but I haven’t tried it.
It seems that using IterableOps as base class works for 2.12 and 2.13, as it provides map and flatMap with a parameterized return type:
implicit def iterablePairable[T[X] <: IterableOps[X, T, T[X]]]: Pairable[T] = new Pairable[T] {
override def map[A, B](seq: T[A], f: A => B): T[B] = seq.map(f)
override def foldLeft[A, B](seq: T[A], z: B)(f: (B, A) => B): B = seq.foldLeft(z)(f)
}
Sorry, I don’t understand your suggestion fully.
Are you suggesting that I simply all my implicit variable definitions with the definition of iterablePairable, Or that I follow this pattern for all my implicit variable definitions?
The idea is that you replace your seqPairable with this more-general iterablePairable, which looks like it could work.
It’s intriguing – I hadn’t previously come across how this works in 2.13, but basically, by stepping higher up the hierarchy (Seq <: SeqOps <: IterableOps) you now get a more-flexible version of .map(), that looks like it can actually do what you want, without the 2.12 insanity of CanBuildFrom…