Type based recursion can be used to solve for a variety of problems at compile time. One of those problems is how to apply a function to an object based upon the type signatures of each. In this post I'll delve into how this is done in the AutoLifts library, mixing the type class pattern to derive the final results.
The Idea
The first thing we need is a structure to recurse over. Given the following:
it is clear that we need to nest the function in three levels of a call to map. Granted, given that each of the levels could be done as a Functor (as each of them has a Functor) we could lift the function up so that it could be applied to the base type. This forms the basis for a recursion; each type nesting can be examined and using a Functor, mapped over.
Let's start with a function definition coupled with a type class. Furthermore, for ease of use place the definition of the function on an implicit class:
Then using the magic of implicit resolution order, we can place the definition of the type class in it's own companion object like so:
The companion object extends a "LowPriority" trait which contains an implicit def called "recur." This is in addition to the implicit which produces the same type class in the main body. No divergent implicit error will be thrown, however, as this is again using the priority rules on implicit resolution order to force the compiler to prefer the definition found in the body of the companion and only then, if the types do not satisfy, check the extended trait.
The "recur" method requires that another search for the same type class with different type parameters be conducted. This acts as a loop, with the compiler pattern matching at the type level to chose which branch to proceed down. Eventually the looping terminates at the "base" method or fails because no implicit parameter could be generated.
Since this is a recursive routine, there must be an accumulator. The Out type parameter is that accumulator, gathering up the type information of the final result. It is not known ahead of time what that type is until the compiler finishes up the recursive search, each level of recursion refining it slightly. Note, the type class itself could not be defined without specifying something as the return type of the "apply" method (and is much better than the generic and near useless Any.)
The above is fine for when the function arguments are very strict and always known to be exact. Scala allows for inheritance and as such the definition of Function1 is permissive with the argument type, contravariant, and result type, covariant. While the above definition doesn't care about the covariance of the result type, mimicking the contravariant nature of the function at the type level requires a slight change:
Adding a fourth type parameter to the "base" method which is bounded by the argument of the enclosing type solves the issue.
Finally, the last thing to do is to add an Aux type so that the compiler carries the type information in an explicit manner to the final result type.
If this Aux type were not added, the compiler's type inferencer would "lose" the type information contained in the Out type parameter.
Conclusion
The actual implementation in the AutoLifts library differs slightly and can be seen in the three different libs each using Algebird, Cats and Scalaz respectively. If you'd like to get a more in depth understanding of how this works, I would refer you to a talk I gave over a year ago in the video section of this website.