These are chat archives for typelevel/cats

12th
Mar 2015
Pascal Voitot
@mandubian
Mar 12 2015 07:18
sorry it was time to sleep
what do you mean by type level CPS?
Miles Sabin
@milessabin
Mar 12 2015 09:17
Just that ... computing a type using continuation passing style. Each of Generic1, IsHCons1 and IsCCons1 are parametrized with one or two "continuation" type classes type arguments which are resolved to instances at the computed higher kinded type.
So, specifically, Generic1 computes Functor for it's higher-kinded representation type; and IsHCons1 and IsCCons1 compute Functor for their respective heads and tails.
Pascal Voitot
@mandubian
Mar 12 2015 09:50
let me wrap my mind around this idea
one question first: def apply[F[_]](implicit f: Lazy[Functor[F]]): Functor[F] = f.value
Does the Lazy solve a lot of issues?
Miles Sabin
@milessabin
Mar 12 2015 09:52
Yes. It stops recursive implicits from diverging at compile time and blowing the stack at run time. It ties recursive implicit knots.
Pascal Voitot
@mandubian
Mar 12 2015 09:53
interesting
Miles Sabin
@milessabin
Mar 12 2015 09:53
It's probably the main enabler of the new derivation stuff from 2.1.0 on.
But that's not really what I meant wrt CPS.
Pascal Voitot
@mandubian
Mar 12 2015 09:53
but do you use Lazy all the time now?
as soon as you have recursive implicits?
Miles Sabin
@milessabin
Mar 12 2015 09:54
Basically adding Lazy everywhere means that recursive implicit resolution works the way you would naively expect it to ;-)
Pascal Voitot
@mandubian
Mar 12 2015 09:54
or are there very special cases where it should be used?
Miles Sabin
@milessabin
Mar 12 2015 09:55
You should use it anywhere that otherwise scalac thinks an implicit resolution diverges, but you "know" that in fact it doesn't.
Pascal Voitot
@mandubian
Mar 12 2015 09:55
:)
ok I see... normally scalac explodes quite quickly in these cases so you can see when you have to use Lazy then
Miles Sabin
@milessabin
Mar 12 2015 09:56
scalac will always think that knot tying is divergent, so anything that requires knot tying should use Lazy.
Yup.
Julien Truffaut
@julien-truffaut
Mar 12 2015 09:57
@milessabin what do you mean by "knot tying"?
Miles Sabin
@milessabin
Mar 12 2015 09:58
Anything where you're building a cyclic structure, or encoding recursion over one.
Pascal Voitot
@mandubian
Mar 12 2015 09:58
ie a lot of things in shapeless :)
I've been hitting my head against walls due to this
Julien Truffaut
@julien-truffaut
Mar 12 2015 09:58
ok so where you have an implicit that takes an implicit for example?
Pascal Voitot
@mandubian
Mar 12 2015 09:59
I could solve my issues with multiple levels of implicits traits
"that takes an implicit on itself"
Miles Sabin
@milessabin
Mar 12 2015 10:05

Consider something like,

trait Tree[T]
case class Leaf[T](t: t) extends Tree[T]
case class Node[T](l: Tree[T], r: Tree[T]) extends Tree[T]

To resolve an implicit recursively for Tree[T] you need implicits for Leaf[T] (fine) and Node[T] ... the latter needs an implicit for Tree[T] for its l and r elements, which if coded directly will immediately cause scalac to decide "Divergent!" and bail.
Lazy prevents that.

Julien Truffaut
@julien-truffaut
Mar 12 2015 10:07
ah I see, it is bit like scalac asking you to annotate the type of a recursive function
Miles Sabin
@milessabin
Mar 12 2015 10:07
The general line is: recursive data types have recursive folds, so encoding them implicitly requires lazy knot tying.
Julien Truffaut
@julien-truffaut
Mar 12 2015 10:08
just to be sure, when you mention Lazy it is from shapeless not cats, right?
Miles Sabin
@milessabin
Mar 12 2015 10:08
Yup.
Pascal Voitot
@mandubian
Mar 12 2015 10:32
@milessabin in Generic1, R[t] is the HList or Coproduct right?
Miles Sabin
@milessabin
Mar 12 2015 10:32
Yup.
The problem I'd been having was getting that type out of the generic to feed into subsequent implicits.
Pascal Voitot
@mandubian
Mar 12 2015 10:33
So Generic1 makes the main Functor from F[T] and then passes to IsHCons1 or IsCCons1
that makes Functor on each part
Miles Sabin
@milessabin
Mar 12 2015 10:34
Yup.
Pascal Voitot
@mandubian
Mar 12 2015 10:34
thus the CPS
very very nice :)
Miles Sabin
@milessabin
Mar 12 2015 10:34
Yup: Instead of getting the types out to feed into the next implicit resolution I feed the next implicit resolution into the preceding step.
It's a workaround for SI-2712, but it looks quite elegant in any case :-)
Pascal Voitot
@mandubian
Mar 12 2015 10:39
I need to think about the details now, I caught the idea but the details the detailssssss