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?

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))
}

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.