Structural Programming in Scala with Shapeless: How to use the SYB implementation correctly?

Question

I want to use the SYB implementation in the Shapeless library to write the following generic traversal function:

class Data

// Perform the desired manipulation on the given data 
object manipulate extends ->((data: Data) => data)

def traverseAndManipulate[B](expr: B): B = {
  everywhere(manipulate)(expr)
}

Unfortunately, this code produces the following type error (using Shapeless 2.0.0-M1 and Scala 2.10.2):

type mismatch;
[error]  found   : shapeless.EverywhereAux[SYB.manipulate.type]
[error]  required: ?{def apply(x$1: ? >: B): ?}
[error] Note that implicit conversions are not applicable because they are ambiguous:
[error]  both method inst1 in trait PolyInst of type [A](fn: shapeless.Poly)(implicit cse: fn.ProductCase[shapeless.::[A,shapeless.HNil]])A => cse.Result
[error]  and macro method apply in object Poly of type (f: Any)shapeless.Poly
[error]  are possible conversion functions from shapeless.EverywhereAux[SYB.manipulate.type] to ?{def apply(x$1: ? >: B): ?}
[error]     everywhere(manipulate)(expr)

I assume, that the type parameter B needs to be constrained in some way, to make the implicit macros of the Shapeless library applicable, but I have no idea how.

Can such a traversal function be written using Shapeless?

Answer 1

You need to make an implicit witness for the everywhere combinator available in the body of your method,

def traverseAndManipulate[B](expr: B)
  (implicit e: Everywhere[manipulate.type, B]) = everywhere(manipulate)(expr)

Note that for reasons that I'm not able to fathom just at the moment, giving traverseAndManipulate an explicit result type of B causes the compiler to report a similar ambiguity. The result type is however correctly inferred as B. If you prefer to have an explicit result type, the following should be equivalent,

def traverseAndManipulate[B](expr: B)
  (implicit e: Everywhere[manipulate.type, B] { type Result = B }): B = e(expr)