When are dependent types needed in Shapeless?

Question

As I understand dependent types allow you to leave output types unspecified:

E.g., if you have a type class:

trait Last[In] {
  type Out
}

then you could summon an instance while leaving the output type unspecified:

implicitly(Last[String :: Int :: HNil]) // output type calculated as Int

And the Aux pattern allows you to specify the output type again:

implicitly(Last.Aux[String :: Int :: HNil, Int])

which you need in an implicit parameter list in order to do something useful with the output type (to work around a Scala limitation on dependent types).

But if you always need to specify (or assign a type param to) the output type, why bother using dependent types (and then Aux) in the first place?

I tried copying the Last type class from Shapeless' src, replacing type Out by an additional type param in the trait and removing Aux. It still works.

What is the situation when I actually need them?

@DmytroMitin I get that Sum[A, B] is not the same as Sum[A, B] { type Out = C } or Sum.Aux[A, B, C]. I'm asking why do I need type Out at all rather than just Sum[A, B, C]. — Vituel

Dmytro Mitin Dmytro Mitin · Accepted Answer · 2018-07-02T21:41:14

I get that Sum[A, B] is not the same as Sum[A, B] { type Out = C } or Sum.Aux[A, B, C]. I'm asking why do I need type Out at all rather than just Sum[A, B, C].

The difference is in partial application. For trait MyTrait { type A; type B; type C } you can specify some of types and not specify others (expecting that compiler infers them). But for trait MyTrait[A, B, C] you can only either specify all of them or not specify any of them. For Sum[A, B] { type Out } you would prefer to specify A, B and not specify Out (expecting that compiler infers its value based on implicits existing in scope). Similarly for trait Last[In] { type Out } you would prefer to specify In and not specify Out (expecting that compiler infers its value). So type parameters are more like inputs and type members are more like outputs.

https://www.youtube.com/watch?v=R8GksuRw3VI

Abstract types versus type parameters and linked questions

But when exactly, would I prefer to specify In and not specify Out?

Let's consider the following example. It's a type class for addition of natural numbers:

sealed trait Nat
case object Zero extends Nat
type Zero = Zero.type
case class Succ[N <: Nat](n: N) extends Nat

type One = Succ[Zero]
type Two = Succ[One]
type Three = Succ[Two]
type Four = Succ[Three]
type Five = Succ[Four]

val one: One = Succ(Zero)
val two: Two = Succ(one)
val three: Three = Succ(two)
val four: Four = Succ(three)
val five: Five = Succ(four)

trait Add[N <: Nat, M <: Nat] {
  type Out <: Nat
  def apply(n: N, m: M): Out
}

object Add {
  type Aux[N <: Nat, M <: Nat, Out0 <: Nat] = Add[N, M] { type Out = Out0 }
  def instance[N <: Nat, M <: Nat, Out0 <: Nat](f: (N, M) => Out0): Aux[N, M, Out0] = new Add[N, M] {
    override type Out = Out0
    override def apply(n: N, m: M): Out = f(n, m)
  }

  implicit def zeroAdd[M <: Nat]: Aux[Zero, M, M] = instance((_, m) => m)
  implicit def succAdd[N <: Nat, M <: Nat, N_addM <: Nat](implicit add: Aux[N, M, N_addM]): Aux[Succ[N], M, Succ[N_addM]] =
    instance((succN, m) => Succ(add(succN.n, m)))
}

This type class works both on type level

implicitly[Add.Aux[Two, Three, Five]]

and value level

println(implicitly[Add[Two, Three]].apply(two, three))//Succ(Succ(Succ(Succ(Succ(Zero)))))
assert(implicitly[Add[Two, Three]].apply(two, three) == five)//ok

Now let's rewrite it with type parameter instead of type member:

trait Add[N <: Nat, M <: Nat, Out <: Nat] {
  def apply(n: N, m: M): Out
}

object Add {
  implicit def zeroAdd[M <: Nat]: Add[Zero, M, M] = (_, m) => m
  implicit def succAdd[N <: Nat, M <: Nat, N_addM <: Nat](implicit add: Add[N, M, N_addM]): Add[Succ[N], M, Succ[N_addM]] =
    (succN, m) => Succ(add(succN.n, m))
}

On type level it works similarly

implicitly[Add[Two, Three, Five]]

But on value level now you have to specify type Five while in the former case it was inferred by compiler.

println(implicitly[Add[Two, Three, Five]].apply(two, three))//Succ(Succ(Succ(Succ(Succ(Zero)))))
assert(implicitly[Add[Two, Three, Five]].apply(two, three) == five)//ok

So the difference is in partial application.

But if you add a + syntax sugar as you normally would to make it practical (shapeless also does it for everything), the dependent type doesn't seem to matter

Syntax helps not always. For example let's consider a type class that accepts a type (but not value of this type) and produces a type and value of this type:

trait MyTrait {
  type T
}

object Object1 extends MyTrait
object Object2 extends MyTrait

trait TypeClass[In] {
  type Out
  def apply(): Out
}

object TypeClass {
  type Aux[In, Out0] = TypeClass[In] { type Out = Out0 }
  def instance[In, Out0](x: Out0): Aux[In, Out0] = new TypeClass[In] {
    override type Out = Out0
    override def apply(): Out = x
  }

  def apply[In](implicit tc: TypeClass[In]): Aux[In, tc.Out] = tc

  implicit val makeInstance1: Aux[Object1.T, Int] = instance(1)
  implicit val makeInstance2: Aux[Object2.T, String] = instance("a")
}

println(TypeClass[Object1.T].apply())//1
println(TypeClass[Object2.T].apply())//a

but if we make Out a type parameter then upon call we'll have to specify Out and there's no way to define extension method and infer type parameter In from element type since there are no elements of the types Object1.T, Object2.T.

When are dependent types needed in Shapeless?

1 Answers