List with type constraints on consecutive elements

Question

Is it possible to define a list type where every pair of consecutive elements satisfies some relation (constraint). For example, a list of functions such that the functions can be composed:

val f1: A => B = ???
val f2: B => C = ???
val f3: C => D = ???

type SafeList = ??? // how to define this?

val fs: SafeList = f1 :: f2 :: f3 :: HNil // OK

val fs: SafeList = f1 :: f3 :: HNil       // ERROR

Answer 1

It's not usually possible to describe interesting constraints like this using a type alias—instead you want a type class that will serve as evidence that a type has some property.

With Shapeless it's often possible to accomplish this using type classes that the library provides, but I don't think that's the case here. Fortunately it's not too hard to write your own:

import shapeless._

// Evidence that an hlist is made up of functions that can be composed.
trait Composable[L <: HList] {
  type In
}

object Composable {
  type Aux[L <: HList, In0] = Composable[L] { type In = In0 }

  implicit def composable0[A, B]: Aux[(A => B) :: HNil, A] =
    new Composable[(A => B) :: HNil] {
      type In = A
    }

  implicit def composable1[A, B, T <: HList]
    (implicit tc: Aux[T, B]): Aux[(A => B) :: T, A] =
      new Composable[(A => B) :: T] {
        type In = A
      }
}

def composable[L <: HList: Composable] {}

What we're doing here is describing how to build up evidence inductively, with a singleton HList as the base case. At each step we use the In type member to keep track of what the output type of the next (i.e. earlier in the list) function must be.

And to confirm that it does what we expect:

scala> composable[(Int => String) :: (String => Char) :: HNil]

scala> composable[(Int => Long) :: (Long => Char) :: (Char => String) :: HNil]

scala> composable[(Int => String) :: (Symbol => Char) :: HNil]
<console>:23: error: could not find implicit value for evidence parameter...

The first two work just fine, while the third doesn't compile.