Generic transform/fold/map over tuple/hlist contai

问题:

I recently asked Map and reduce/fold over HList of scalaz.Validation and got a great answer as to how to transform a fixed sized tuple of Va[T] (which is an alias for scalaz.Validation[String, T]) into a scalaz.ValidationNel[String, T]. I've since then been studying Shapeless and type level programming in general to try to come up with a solution that works on tuples of any size.

This is what I'm starting out with:

import scalaz._, Scalaz._, shapeless._, contrib.scalaz._, syntax.std.tuple._

type Va[A] = Validation[String, A]

// only works on pairs of Va[_]
def validate[Ret, In1, In2](params: (Va[In1], Va[In2]))(fn: (In1, In2) => Ret) = {
  object toValidationNel extends Poly1 {
    implicit def apply[T] = at[Va[T]](_.toValidationNel)
  }
  traverse(params.productElements)(toValidationNel).map(_.tupled).map(fn.tupled)
}

so then validate is a helper I call like this:

val params = (
  postal  |> nonEmpty[String]("no postal"),
  country |> nonEmpty[String]("no country") >=> isIso2Country("invalid country")
)

validate(params) { (postal, country) => ... }

I started out by taking any Product instead of a pair and constraining its contents to Va[T]:

// needs to work with a tuple of Va[_] of arbitrary size
def validateGen[P <: Product, F, L <: HList, R](params: P)(block: F)(
  implicit
  gen: Generic.Aux[P, L],
  va:  UnaryTCConstraint[L, Va],
  fp:  FnToProduct.Aux[F, L => R]
) = ???

I do have the feeling that simply adding the constraint only makes sure the input is valid but doesn't help at all with implementing the body of the function but I don't know how to go about correcting that.

traverse then started complaining about a missing evidence so I ended up with:

def validateGen[P <: Product, F, L <: HList, R](params: P)(block: F)(
  implicit
  gen: Generic.Aux[P, L],
  va:  UnaryTCConstraint[L, Va],
  tr:  Traverser[L, toValidationNel.type],
  fp:  FnToProduct.Aux[F, L => R]
) = {
  traverse(gen.to(params): HList)(toValidationNel).map(_.tupled).map(block.toProduct)
}

The compiler however continued to complain about a missing Traverser[HList, toValidationNel.type] implicit parameter even though it's there.

Which additional evidence do I need to provide to the compiler in order for the traverse call to compile? Has it got to do with the UnaryTCConstraint not being declared in a way that is useful to the traverse call, i.e. it cannot apply toValidationNel to params because it cannot prove that params contains only Va[_]?

P.S. I also found leftReduce Shapeless HList of generic types and tried to use foldRight instead of traverse to no avail; the error messages weren't too helpful when trying to diagnose which evidence the compiler was really lacking.

UPDATE:

As per what lmm has pointed out, I've removed the cast to HList, however, the problem's now that, whereas in the non-generic solution I can call .map(_.tupled).map(block.toProduct) on the result of the traverse call, I'm now getting:

value map is not a member of shapeless.contrib.scalaz.Out

How come it's possible that it was possible on the result of the traverse(params.productElements)(toValidationNel) call and not the generic traverse?

UPDATE 2:

Changing the Traverser[...] bit to Traverser.Aux[..., Va[L]] helped the compiler figure out the expected result type of the traversal, however, this only makes the validateGen function compile successfully but yields another error at the call site:

[error] could not find implicit value for parameter tr: shapeless.contrib.scalaz.Traverser.Aux[L,toValidationNel.type,Va[L]]
[error]     validateGen(params) { (x: String :: String :: HNil) => 3 }
[error]                         ^

I'm also getting the feeling here that the UnaryTCConstraint is completely unnecessary — but I'm still too new to Shapeless to know if that's the case.

UPDATE 3:

Having realized the type that comes out of the traverser cannot be Va[L] because L itself is already a hlist of Va[_], I've split the L type parameter to In and Out:

def validateGen[P <: Product, F, In <: HList, Out <: HList, R](params: P)(block: F)(
  implicit
  gen: Generic.Aux[P, In],
  va:  UnaryTCConstraint[In, Va],  // just for clarity
  tr:  Traverser.Aux[In, toValidationNel.type, Va[Out]],
  fn:  FnToProduct.Aux[F, Out => R]
): Va[R] = {
  traverse(gen.to(params))(toValidationNel).map(block.toProduct)
}

this compiles well — I'd be curious to find out how come the previous version with Va[L] being the return value (i.e. the 3rd param to Traverser.Aux) even compiled — however, at the call site, I now get:

Unspecified value parameters tr, fn

回答1:

You have a Traverser[L, toValidationNel.type] which is not the same thing as Traverser[HList, toValidationNel.type] (which would have to work for any HList - no chance). I don't know why you've written gen.to(params): HList, but this is throwing away type information; shouldn't that be of type L?

This will probably only kick the problem one level higher; I doubt you'll be able to get the Traverser you need automatically. But you should be able to write an implicit method that supplies one based on the UnaryTCConstraint, and it's possible shapeless already includes that and it will Just Work.

Update:

In the first example, the compiler knew the specific Traverser instance it was using, so it knew what the Out type was. In validateGen you haven't constrained anything about tr.Out, so the compiler has no way of knowing that it's a type that supports .map. If you know what the output of the traverse needs to be then you can probably require an appropriate Traverser.Aux i.e.:

tr: Traverser.Aux[L, toValidationNel.type, Va[L]]

(Just don't ask me how to make sure the type inference still works).

I think you probably don't want the .map(_.tupled), because the _ there is already a HList (I suspect it's redundant in the original validate too), but I've never used .toProduct before so maybe you have it right.

Update 2:

Right, this is as I initially suspected. Looking at the implementation of Sequencer I suspect you're right and the UnaryTCConstraint will be subsumed by the Traverser. If you're not using it then no point requiring it.

The only advice I can give is to chase through the calls that should be providing your implicits. E.g. the Traverser should be coming from Traverser.mkTraverser. So if you try calling Traverser.mkTraverser[String :: String :: HNil, toValidationNel.type, Va[String] :: Va[String] :: HNil] then you should be able to see whether it's the Mapper or the Sequencer that can't be found. Then you can recurse through the implicit calls that should happen until you find a simpler case of something that should be working, but isn't.

回答2:

After long hours of experimentation, frustration and dead brain cells, I've started from scratch without Traverser and instead gone with Mapper and Sequencer; I'll later try to see if I can make it use Traverser again (if not for practicality, at least for learning purposes):

def validate[P <: Product, F, L1 <: HList, L2 <: HList, L3 <: HList, R](params: P)(block: F)(
  implicit
  gen: Generic.Aux[P, L1],
  mp:  Mapper.Aux[toValidationNel.type, L1, L2],
  seq: Sequencer.Aux[L2, VaNel[L3]],
  fn:  FnToProduct.Aux[F, L3 => R]
): VaNel[R] = {
  sequence(gen.to(params).map(toValidationNel)).map(block.toProduct)
}

Here's proof — pun intended — that it runs http://www.scastie.org/7086.