scala - generic unzip for HList

Question

I have the following Scala problem:

Write a function that will take a list of HLists

List(23 :: “a” :: 1.0d :: HNil, 24 :: “b” :: 2.0d :: HNil)    # this is list of hlists

and return back HList of Lists

List[Int](23, 24) :: List[String](“a”, “b") :: List[Double](1.0d, 2.0d) :: HNil # this is hlist of lists

This is sort of like generic unzipN. Is it at all possible for arbitrary HList?

Thank you.

Answer 1

There are lots of ways to solve this problem, and defining a custom type class (as in Nikita's answer) is a perfectly good one. I personally find the following approach a little clearer, though. First let's make any heterogenous list made up of monoids into a monoid:

import shapeless._
import scalaz._, Scalaz._

implicit object hnilMonoid extends Monoid[HNil] {
  val zero = HNil
  def append(f1: HNil, f2: => HNil) = HNil
}

implicit def hconsMonoid[H: Monoid, T <: HList: Monoid] = new Monoid[H :: T] {
  val zero = Monoid[H].zero :: Monoid[T].zero
  def append(f1: H :: T, f2: => H :: T) =
    (f1.head |+| f2.head) :: (f1.tail |+| f2.tail)
}

I'm using Scalaz's Monoid, although you could pretty easily write your own—it's just a type class that witnesses that a type has a addition-like operation with an identity element. Crucially for this example lists (of anything) are monoids under concatenation, with the empty list as the identity element.

Next for a simple polymorphic function that wraps whatever you give it in a list:

object singleton extends Poly1 { implicit def anything[A] = at[A](List(_)) }

And then we tie it all together:

def unzipN[L <: HList, Out <: HList](hlists: List[L])(implicit
  mapper: ops.hlist.Mapper.Aux[singleton.type, L, Out],
  monoid: Monoid[Out]
): Out = hlists.map(_ map singleton).suml

Now we can define our example:

val myList = List(23 :: "a" :: 1.0d :: HNil, 24 :: "b" :: 2.0d :: HNil)

And we're done:

scala> println(unzipN(myList))
List(23, 24) :: List(a, b) :: List(1.0, 2.0) :: HNil

With this approach most of the machinery is very general, and it's easy to get an intuition for what each step does. Consider the following simplified example:

val simple = List(1 :: "a" :: HNil, 2 :: "b" :: HNil)

Now simple.map(_ map singleton) is just the following:

List(List(1) :: List("a") :: HNil, List(2) :: List("b") :: HNil)

But we know how to "add" things of type List[Int] :: List[String] :: HNil, thanks to our monoid machinery at the top. So we can just take the sum of the list using Scalaz's suml, and we're done.

This is all using Shapeless 2.0, but it would look pretty similar in 1.2.

Answer 2

To solve this you'll need a custom typeclass:

import shapeless._

trait Unzipper[ -input ]{
  type Output
  def unzip( input: input ): Output
}
object Unzipper {
  implicit def headTail
    [ head, tail <: HList ]
    ( implicit tailUnzipper: Unzipper[ List[ tail ] ]{ type Output <: HList } )
    =
    new Unzipper[ List[ head :: tail ] ]{
      type Output = List[ head ] :: tailUnzipper.Output
      def unzip( list: List[ head :: tail ] ) = 
        list.map(_.head) :: tailUnzipper.unzip(list.map(_.tail))
    }
  implicit val nil =
    new Unzipper[ List[ HNil ] ]{
      type Output = HNil
      def unzip( list: List[ HNil ] ) = HNil
    }
}

val list = List(23 :: "a" :: 1.0d :: HNil, 24 :: "b" :: 2.0d :: HNil)
println( implicitly[Unzipper[list.type]].unzip(list) )

Outputs:

List(23, 24) :: List(a, b) :: List(1.0, 2.0) :: HNil