Scala implicit for arbitrarily deep Functor composition

Question

I'm trying to provide extension methods to an existing class Elem in Scala. However, I also want the operations to be available to any M[Elem], as long as a Scalaz Functor for M is in scope. The behavior is always to apply the operation to the functor by using map.

import scalaz._
import Scalaz._

class Elem

implicit class Ops[F[_]: Functor, A <% Elem](self: F[A]) {
  def foo = self.map(_ => "bar")
}

val elem = new Elem

// TODO (nice to have): can we avoid this "explicit implicit" conversion?
implicit def idOps[A <% Elem](self: A) = new Ops[Id, A](self)

elem.foo                        // bar
Option(elem).foo                // Some(bar)
List(elem).foo                  // List(bar)

I want to go further and make my extension methods available to arbitrarily deep functors, such as List[Option[Elem]] and Option[Option[Option[Elem]]]. I was able to write an implicit providing Ops for the composition of two functors, but I was not able to generalize it to arbitrary nesting depths:

// TODO: can we improve this to provide arbitrarily deep functor composition?
implicit def compositeOps[F[_]: Functor, G[_]: Functor, A <% Elem](self: F[G[A]]) = {
  implicit val FG = implicitly[Functor[F]].compose[G]
  new Ops[({ type FG[X] = F[G[X]] })#FG, A](self)
}

List(Option(elem)).foo          // List(Some(bar))
Option(List(Option(elem))).foo  // doesn't compile

Is there any way to achieve this?

Tenpenny

Answer 1

You can make an implicit helper available recursively:

sealed trait Helper[FA] {
  type A
  type F[_]
  def w(fa: FA): F[A]
  val f: Functor[F]
}
trait Helper1 {
  implicit def nil[A] = new Helper[A] {
    type A = A
    type F[X] = X
    def w(a: A) = a
    val f = implicitly[Functor[Id]]
  }
}
object Helper extends Helper1 {
  implicit def cons[FA1, RA](implicit u: Unapply[Functor, FA1]{type A = RA},
    rest: Helper[RA]) = new Helper[FA1] {
    type A = rest.A
    type F[X] = u.M[rest.F[X]]
    def w(fa: FA1) = u.TC.map(u.apply(fa))(rest.w)
    val f = rest.f.compose(u.TC) //or the other way around, I can never remember
  }
}
implicit def compositeOps[FA, A1](self: FA)(
  implicit helper: Helper[FA]{type A = A1}, conv: A1 => Elem) = {
    implicit val FG = helper.f
    new Ops[helper.F, helper.A](helper.w(self))
}

Jewry

Thanks for the response! I found two issues with your solution: 1) I really need an implicit conversion from A to a fixed Elem type as in the example. Is there any way to work with that and your Helper other than including the A => Elem implicit as a val in the body of Helper? 2) The compiler can't find Helper instances for subclasses of the functors themselves, e.g. I cannot apply Ops to a Some. Is there any way to lift that restriction? I am aware that this already happens with Scalaz type classes, but in my case it is particularly important to be able to do that. – Ardie

1) <% is just sugar for an implicit A => Elem; I've added that to the compositeOps in the example. 2) It's not really possible; this is an ongoing debate in scalaz, but if we declared things to be co/contravariant then this would lead to cases where Any was inferred instead of what should be a type error. It is possible to declare a Functor[Some] but that will probably get you into trouble. The recommended approach is to use "smart constructors" like scalaz's some that return the appropriate types (in this case Option[A] rather than Some[A]). – Jewry

I knew about <%, but I didn't know how to obtain the type of A1 and didn't think of doing {type A = A1}. And I guess I'll work around the subclasses issue then. Thank you! – Ardie

Answer 2

We can create a trait to represent what you want

trait DeepFunctor[X, A] {
  type Result[_]
  def map[B](x: X)(f: A => B): Result[B]
}

Note that it allows X to be mapped into a Result[B]. X could be anything at this point.

The simplest version is where we say that X equals A. The result should then be Id[B]. It's put in a trait to make sure it has low priority.

trait LowerPriorityDeepFunctor {
  implicit def identity[A] =
    new DeepFunctor[A, A] {
      type Result[x] = Id[x]
      def map[B](x: A)(f: A => B) = f(x)
    }
}

Note that there is no need to ask for the Functor of Id.

The more complex version is where X is some container for which a Functor is defined.

object DeepFunctor extends LowerPriorityDeepFunctor {
  implicit def deep[F[_], X, A](
    implicit F: Functor[F], inner: DeepFunctor[X, A]) =
    new DeepFunctor[F[X], A] {
      type Result[x] = F[inner.Result[x]]
      def map[B](x: F[X])(f: A => B) = F.map(x)(inner.map(_)(f))
    }
}

The result of the deep method is a DeepFunctor for F[X]. Since we know nothing about X we request a DeepFunctor for X. This will recursively search for DeepFunctor instances until it reaches identity.

Your Ops class now becomes relatively simple

implicit class Ops[X](self: X) {
  def foo[A](implicit F: DeepFunctor[X, A]) = F.map(self)(_ => "bar")
}

Note that the _ is now of type A. If you want to restrict to a certain type you can define A as A <: SomeType. If you want to be able to support an implicit conversion you can use an extra implicit argument ev: A => SomeType. If you want to make A a specific type, you can remove the A and put SomeType in the DeepFunctor directly.

Pa

This looks like a clean and relatively easy to understand solution! The only thing that bothers me a little is that I have to request an implicit DeepFunctor in each method and not in the class itself, as I have much more than one operation like foo and I would have to change all their signatures. I tried to move A and F to the class signature but I had no luck, as the result for each method is type-dependent on the DeepFunctor and client code would not resolve its type to the original functor composition. Do you see any way I can avoid this? If not that's OK :) – Ardie

@RuiGonçalves Yeah, it seems the problem is caused by type Result[x] = F[inner.Result[x]]. I think this is a compiler bug, but I don't know for sure. If the implicit is moved to the class itself, the Result[x] type is lost. I tried moving the Result type to the DeepFunctor[X, A, R[_]] but that messed up implicit resolution. Theoretically this is a stack overflow question on it's own. I however have no time left to create a simple reproducable example that shows this problem. – Pa