Shapeless - Deduplicating types in Coproduct

Question

Given that I have a type of Int :+: Int :+: String :+: CNil, is there an easy way to turn it into Int :+: String :+: CNil?

Answer 1

It depends on what you mean by "easy". I'm pretty sure there's no straightforward way to perform this operation by composing coproduct operations that are available off-the-shelf in Shapeless, but writing your own type class to do this is reasonably straightforward (at least as far as these things go).

I'm going to assume a couple of things that aren't specified in your requirements:

1. You want the types in the resulting coproduct to be unique (e.g. you're not just collapsing adjacent elements as in your example).
2. In the case of non-adjacent duplicated types, you want the last duplicate to be included in the result.

It wouldn't be too hard to adjust the solution below if these assumptions aren't accurate—the core idea would be the same.

A complete solution looks like this:

import shapeless.{ :+:, CNil, Coproduct, DepFn1, Inl, Inr }
import shapeless.ops.coproduct.Inject

trait Unique[C <: Coproduct] extends DepFn1[C] {
  type Out <: Coproduct
}

object Unique extends LowPriorityUnique {
  type Aux[C <: Coproduct, Out0 <: Coproduct] = Unique[C] { type Out = Out0 }

  def apply[C <: Coproduct](implicit unC: Unique[C]): Aux[C, unC.Out] = unC

  implicit val uniqueCNil: Aux[CNil, CNil] = new Unique[CNil] {
    type Out = CNil
    def apply(c: CNil): CNil = c
  }

  implicit def uniqueCCons1[L, R <: Coproduct](implicit
    inj: Inject[R, L],
    unR: Unique[R]
  ): Aux[L :+: R, unR.Out] = new Unique[L :+: R] {
    type Out = unR.Out

    def apply(c: L :+: R): unR.Out = unR(
      c match {
        case Inl(l) => inj(l)
        case Inr(r) => r
      }
    )
  }
}

class LowPriorityUnique {
  implicit def uniqueCCons0[L, R <: Coproduct](implicit
    unR: Unique[R]
  ): Unique[L :+: R] { type Out = L :+: unR.Out } = new Unique[L :+: R] {
    type Out = L :+: unR.Out

    def apply(c: L :+: R): L :+: unR.Out = c match {
      case Inl(l) => Inl(l)
      case Inr(r) => Inr(unR(r))
    }
  }
}

We can walk through this code step-by-step.

trait Unique[C <: Coproduct] extends DepFn1[C] {
  type Out <: Coproduct
}

This is our type class. It characterizes a coproduct C, and for any instance it has an output type that's unique determined by C that is also a coproduct. From DepFn1 we get a method apply that takes a C and returns an Out; this is what we'll be implementing in our instances below.

In the companion object we have a couple of lines that are basically boilerplate—they're not strictly necessary, but they support convenient, idiomatic use of this type class:

type Aux[C <: Coproduct, Out0 <: Coproduct] = Unique[C] { type Out = Out0 }

def apply[C <: Coproduct](implicit unC: Unique[C]): Aux[C, unC.Out] = unC

The first line lets us avoid writing type refinements (Foo[X] { type Bar = Bar0 }) everywhere, and the second lets us write Unique[C] instead of implicitly[Unique[C]] (and also returns a refined result instead of the useless unrefined Unique[C]).

Next we have our base case:

implicit val uniqueCNil: Aux[CNil, CNil] = new Unique[CNil] {
  type Out = CNil
  def apply(c: CNil): CNil = c
}

This is fairly straightforward: if we get an empty coproduct, we know its elements are already unique.

Next we have a couple of inductive cases. The first, uniqueCCons1, covers the case where the head of the coproduct exists in the tail, and the second, uniqueCCons0, covers the case where it doesn't. Because uniqueCCons1 applies to a subset of the cases uniqueCCons0 covers, we have to prioritize the two instances explicitly. I'm using a subclass to give uniqueCCons0 lower priority, since I think this is the simplest approach.

The implementations of these two instances may look a little messy, but the logic isn't actually that complicated. In both cases we have an inductive Unique[R] instance; the difference is that in the 1 case we first inject the head into the tail (relying on Shapeless's Inject type class to witness that L occurs in R) and then apply unR, where in the 0 case we apply it only to the tail and leave the head unchanged.

It works like this:

scala> type C = Int :+: String :+: CNil
defined type alias C

scala> Unique[C]
res0: Unique[Int :+: String :+: shapeless.CNil]{type Out = Int :+: String :+: shapeless.CNil} = LowPriorityUnique$$anon$3@2ef6f000

scala> Unique[C].apply(Inl(1))
res1: Int :+: String :+: shapeless.CNil = Inl(1)

scala> type C2 = Int :+: String :+: Int :+: CNil
defined type alias C2

scala> Unique[C2].apply(Inr(Inr(Inl(1))))
res2: String :+: Int :+: shapeless.CNil = Inr(Inl(1))

scala> Unique[C2].apply(Inl(1))
res3: String :+: Int :+: shapeless.CNil = Inr(Inl(1))

Which matches our requirements above.

Answer 2

Is this an easy way?

  import shapeless.{:+:, =:!=, CNil, Coproduct, Inl, Inr, unexpected}

  trait Deduplicate[C <: Coproduct] {
    type Out <: Coproduct
    def apply(c: C): Out
  }
  object Deduplicate {
    type Aux[C <: Coproduct, Out0 <: Coproduct] = Deduplicate[C] { type Out = Out0 }
    def instance[C <: Coproduct, Out0 <: Coproduct](f: C => Out0): Aux[C, Out0] = new Deduplicate[C] {
      override type Out = Out0
      override def apply(c: C): Out = f(c)
    }

    implicit def zero: Aux[CNil, CNil] = instance(_ => unexpected)
    implicit def one[H]: Aux[H :+: CNil, H :+: CNil] = instance(identity)
    implicit def duplicates[H, T <: Coproduct](implicit
      dedup: Deduplicate[H :+: T]): Aux[H :+: H :+: T, dedup.Out] = instance {
      case Inl(h) => dedup(Inl(h))
      case Inr(c) => dedup(c)
    }
    implicit def noDuplicates[H, H1, T <: Coproduct](implicit
      dedup: Deduplicate[H1 :+: T],
      ev1: H =:!= H1): Aux[H :+: H1 :+: T, H :+: dedup.Out] = instance {
      case Inl(h) => Inl(h)
      case Inr(c) => Inr(dedup(c))
    }
  }
  implicit class DeduplicateOps[C <: Coproduct](c: C) {
    def deduplicate(implicit dedup: Deduplicate[C]): dedup.Out = dedup(c)
  }

  implicitly[Deduplicate.Aux[String :+: Int :+: Int :+: String :+: String :+: CNil,
    String :+: Int :+: String :+: CNil]]