Transform shapeless HList into a smaller HList

Question

I have a shapeless HList that has the following structure:

type ABCAB = List[A] :: List[B] :: List[C] :: List[A] :: List[B] :: HNil
val abcab: ABCAB = List[A]() :: List(B) :: List[C]() :: List(A) :: List(B) :: HNil

that I would like to transform into a simpler type where lists of same type are appended, left to right:

type ABC = List[A] :: List[B] :: List[C] :: HNil        
val abc: ABC = abcab.magic                       // does magic exist in shapeless?
abc == List(A) :: List(B,B) :: List[C]() :: HNil // true

Is there some built-in functionality in shapeless v1.2.4 for this?

Answer 1

While the approach taken in the other answer (introducing a new type class) will work, it's possible to solve this problem using more general machinery—and in a way that's not that different from the way you'd solve similar problems at the value level.

We'll use a left fold. Writing the combining function is a little tricky, since we have two cases (we've already seen an element with the same type as the current one, or we haven't), and we have to use an implicit prioritization trick to avoid ambiguous implicit values:

import shapeless._

trait LowPriorityCombine extends Poly2 {
  implicit def notAlreadySeen[L <: HList, A](implicit
    p: Prepend[L, List[A] :: HNil]
  ) = at[L, List[A]](_ :+ _)
}

object combine extends LowPriorityCombine {
  implicit def alreadySeen[L <: HList, A](implicit
    s: Selector[L, List[A]],
    r: Replacer[L, List[A], List[A]]
  ) = at[L, List[A]] {
    case (acc, as) => acc.updatedElem[List[A]](acc.select[List[A]] ++ as)
  }
}

But then we're essentially done:

def magic[L <: HList](l: L)(implicit f: LeftFolder[L, HNil.type, combine.type]) =
  l.foldLeft(HNil)(combine)

We can show that it works:

val xs = List(1, 2, 3) :: List('a, 'b) :: List("X", "Y") :: List(4, 5) :: HNil
val test = magic(xs)

And then:

scala> test == List(1, 2, 3, 4, 5) :: List('a, 'b) :: List("X", "Y") :: HNil
res0: Boolean = true

As expected.

The code above is written for 1.2.4, but it should work on 2.0 with a couple of very minor modifications.

---

Update: for the record, here's a working version for 2.0:

import shapeless._, ops.hlist.{ LeftFolder, Prepend, Replacer, Selector }

trait LowPriorityCombine extends Poly2 {
  implicit def notAlreadySeen[L <: HList, A, Out <: HList](implicit
    p: Prepend.Aux[L, List[A] :: HNil, Out]
  ): Case.Aux[L, List[A], Out] = at[L, List[A]](_ :+ _)
}

object combine extends LowPriorityCombine {
  implicit def alreadySeen[L <: HList, A, Out <: HList](implicit
    s: Selector[L, List[A]],
    r: Replacer.Aux[L, List[A], List[A], (List[A], Out)]
  ): Case.Aux[L, List[A], Out] = at[L, List[A]] {
    case (acc, as) => acc.updatedElem[List[A], Out](acc.select[List[A]] ++ as)
  }
}

def magic[L <: HList](l: L)(implicit f: LeftFolder[L, HNil, combine.type]) =
  l.foldLeft(HNil: HNil)(combine)

The main difference is the new imports, but you also need some other small changes because of the extra type parameter on updatedElem.

Answer 2

Implemented for shapeless 2.0, but works with minor modifications for 1.2.4 as well:

import shapeless._

// remove this import for v1.2.4
import shapeless.ops.hlist.{Filter, FilterNot, RightReducer}

// for v1.2.4 replace `Poly` with `Poly2` and `use` with `at`
object combine extends Poly {
  implicit def lists[T] = use((c : List[T], s : List[T]) => c ::: s)
}

trait ListGroup[In <: HList] {
  type Out <: HList
  def apply(l: In): Out
}

object ListGroup {
  implicit def hnil =
    new ListGroup[HNil] {
      type Out = HNil
      def apply(l: HNil) = l
    }

  implicit def hlist[T, Tail <: HList, NOut <: HList, F <: HList, Rest <: HList](
                 implicit f: Filter[List[T] :: Tail, List[T]] { type Out = F },
                          r: RightReducer[F, combine.type] { type Out = List[T] },
                          fn: FilterNot[List[T] :: Tail, List[T]] { type Out = Rest },
                          next: ListGroup[Rest] { type Out = NOut }) =
    new ListGroup[List[T] :: Tail] {
      type Out = List[T] :: NOut
      def apply(l: List[T] :: Tail): List[T] :: NOut =
        l.filter[List[T]].reduceRight(combine) :: next(l.filterNot[List[T]])
    }
}

def magic[L <: HList](l: L)(implicit g: ListGroup[L]) = g(l)

Usage:

val hl = List(1, 2, 3) :: List('a, 'b) :: List("aa", "bb", "cc") :: List(4, 5) :: List('c, 'd, 'e) :: HNil

magic(hl)
// List(1, 2, 3, 4, 5) :: List('a, 'b, 'c, 'd, 'e) :: List(aa, bb, cc) :: HNil

For v1.2.4 replace combine object with this implementation:

object combine extends Poly2 {
  implicit def lists[T] = at((c : List[T], s : List[T]) => c ::: s)
}