Do a covariant filter on an HList

Question

I intend to filter on an HList in a covariant manner - I would like to include subclasses as well. So the covariant filter on Foo should capture elements of Foo as well as Bar. I've constructed this example trying out <:!<, to see if it does what I would like it to do.

http://scastie.org/6465

/***
scalaVersion := "2.11.2"

libraryDependencies ++= Seq(
  "com.chuusai" %% "shapeless" % "2.0.0"
)
*/

import shapeless._

final class HListOps[L <: HList](l: L) {
  trait CoFilter[L <: HList, U] extends DepFn1[L] { type Out <: HList }

  object CoFilter {
    def apply[L <: HList, U](implicit filter: CoFilter[L, U]): Aux[L, U, filter.Out] = filter

    type Aux[L <: HList, U, Out0 <: HList] = CoFilter[L, U] { type Out = Out0 }

    implicit def hlistCoFilterHNil[L <: HList, U]: Aux[HNil, U, HNil] =
      new CoFilter[HNil, U] {
        type Out = HNil
        def apply(l: HNil): Out = HNil
      }

    implicit def hlistCoFilter1[L <: HList, H](implicit f: CoFilter[L, H]): Aux[H :: L, H, H :: f.Out] =
      new CoFilter[H :: L, H] {
        type Out = H :: f.Out
        def apply(l: H :: L): Out = l.head :: f(l.tail)
      }

    implicit def hlistCoFilter2[H, L <: HList, U](implicit f: CoFilter[L, U], e: U <:!< H): Aux[H :: L, U, f.Out] =
      new CoFilter[H :: L, U] {
        type Out = f.Out
        def apply(l: H :: L): Out = f(l.tail)
      }
  }

  def covariantFilter[U](implicit filter: CoFilter[L, U]): filter.Out = filter(l)
}

object Main extends App {

  class Foo(val foo: Int)
  class Bar(val bar: Int) extends Foo(bar)
  val l = new Foo(1) :: new Bar(2) :: new Foo(3) :: new Bar(4) :: HNil
  implicit def hlistOps[L <: HList](l: L): HListOps[L] = new HListOps(l)
  print(l.covariantFilter[Bar] != l)

}

Gives me

[error] /tmp/rendererbI8Iwy0InO/src/main/scala/test.scala:47: could not find implicit value for parameter filter: _1.CoFilter[shapeless.::[Main.Foo,shapeless.::[Main.Bar,shapeless.::[Main.Foo,shapeless.::[Main.Bar,shapeless.HNil]]]],Main.Bar]
[error]   print(l.covariantFilter[Bar] != l)

Answer 1

There are a couple of issues here. The first is that your type class is defined inside of your extension class, but you need the instance at the point where you're calling covariantFilter. Maybe the compiler could find it for you, but it doesn't. It's a lot cleaner not to nest the type class anyway, though.

The second issue is that your two hlistCoFilterN cases don't actually capture all the stuff you want. You only tell the compiler what to do in cases where the type of the head is the filter type and where the filter type is not a subtype of the type of the head. What about where the type of the head is a subtype of the filter type? You probably want something like this:

import shapeless._

trait CoFilter[L <: HList, U] extends DepFn1[L] { type Out <: HList }

object CoFilter {
  def apply[L <: HList, U](implicit f: CoFilter[L, U]): Aux[L, U, f.Out] = f

  type Aux[L <: HList, U, Out0 <: HList] = CoFilter[L, U] { type Out = Out0 }

  implicit def hlistCoFilterHNil[L <: HList, U]: Aux[HNil, U, HNil] =
    new CoFilter[HNil, U] {
      type Out = HNil
      def apply(l: HNil): Out = HNil
    }

  implicit def hlistCoFilter1[U, H <: U, T <: HList]
    (implicit f: CoFilter[T, U]): Aux[H :: T, U, H :: f.Out] =
      new CoFilter[H :: T, U] {
        type Out = H :: f.Out
        def apply(l: H :: T): Out = l.head :: f(l.tail)
      }

  implicit def hlistCoFilter2[U, H, T <: HList]
    (implicit f: CoFilter[T, U], e: H <:!< U): Aux[H :: T, U, f.Out] =
      new CoFilter[H :: T, U] {
        type Out = f.Out
        def apply(l: H :: T): Out = f(l.tail)
      }
}

implicit final class HListOps[L <: HList](val l: L)  {
  def covariantFilter[U](implicit filter: CoFilter[L, U]): filter.Out = filter(l)
}

(For the record, you could also remove the H <:!< U constraint and move hlistCoFilter2 to a LowPriorityCoFilter trait. I find this version a little clearer about its intent, but getting rid of the constraint would arguably be cleaner.)

Now if you have the following:

class Foo(val foo: Int)
class Bar(val bar: Int) extends Foo(bar)
val l = new Foo(1) :: new Bar(2) :: new Foo(3) :: new Bar(4) :: HNil

Your filter will work like this:

scala> l.covariantFilter[Foo] == l
res0: Boolean = true

scala> l.covariantFilter[Bar] == l
res1: Boolean = false

Which I think is what you want.