Abstraction over a sequence of types

Question

Assuming we have a type T[A,B], can we express the following type constraint, let's call it HT:

every type satisfying HT must be of form T[P1, P2] :: T[P2, P3] :: T[P3, P4] :: ... :: T[PN-1, PN] :: HNil

for some type x = P1 :: P2 :: ... :: PN :: HNil.

I am trying to find an abstraction over a typed sequential processing pipeline.

Answer 1

The most convenient way to do this kind of thing is usually to write your own type class. Here's a quick working sketch:

import shapeless._

trait T[I, O] extends (I => O)

trait Pipeline[P <: HList] {
  type In
  type Out
  type Values <: HList
}

object Pipeline {
  type Aux[P <: HList, In0, Out0, Values0 <: HList] = Pipeline[P] {
    type In = In0; type Out = Out0; type Values = Values0
  }

  def apply[P <: HList](
    implicit pipeline: Pipeline[P]
  ): Aux[P, pipeline.In, pipeline.Out, pipeline.Values] = pipeline

  implicit def onePipeline[I, O]: Aux[T[I, O] :: HNil, I, O, I :: O :: HNil] =
    new Pipeline[T[I, O] :: HNil] {
      type In = I
      type Out = O
      type Values = I :: O :: HNil
    }

  implicit def longerPipeline[I, O, P <: HList, Out0, Values0 <: HList](
    implicit pipeline: Aux[P, O, Out0, Values0]
  ): Aux[T[I, O] :: P, I, Out0, I :: Values0] =
    new Pipeline[T[I, O] :: P] {
      type In = I
      type Out = Out0
      type Values = I :: Values0
    }
}

And then (reformatted for clarity):

scala> Pipeline[T[String, Int] :: T[Int, Char] :: HNil]
res5: Pipeline[T[String, Int] :: T[Int, Char] :: HNil] {
  type In = String
  type Out = Char
  type Values = String :: Int :: Char :: HNil
} = Pipeline$$anon$2@38fd077c

scala> Pipeline[T[String, Int] :: T[Char, Char] :: HNil]
<console>:19: error: could not find implicit value for parameter
  pipeline: Pipeline[[T[String, Int] :: T[Char, Char] :: HNil]
              Pipeline[T[String, Int] :: T[Char, Char] :: HNil]
                      ^

The invalid pipeline doesn't compile, and for the valid one we get the endpoints and intermediate values correctly inferred.