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.

Ra

Wow, this is a GroupBy on a type level. Very interesting. Post it to the Shapeless mailing list! – Benitobenjamen

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.

Extravagance

This implementation has very interesting property. I can make it work with Monoid[ArrayBuffer] instance with mutable += operation for append, and the second operand of append is always of size 1. – Ra

I made 2 small improvements: unzipN takes singleton function as parameter now and unzipN can work on other arguments that are Functor and Foldable. def unzipN[L <: HList, Out <: HList, FF[_] : Functor : Foldable](f: Poly1)(hlists: FF[L])(implicit mapper: ops.hlist.Mapper.Aux[f.type, L, Out], monoid: Monoid[Out]): Out = hlists.map(_ map f).suml – Ra

Cool! Note that .map(...).suml can be expressed as .foldMap(...), and be careful mixing type classes like Monoid and side effects—one of the nice things about Monoid is that you can assume e.g. that the order of a reduction doesn't matter. – Extravagance

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

Beaton

How do I get back to HList from implicitly[Unzipper[list.type]].unzip(list)? – Ra

You'll need another typeclass, which is an inverse. With the code above I believe you have enough information on how to do that on your own. Otherwise start a new thread because it is another question and you have answers to your original one. – Beaton

haha. I'd rather use Travis Brown's implementation for few reasons: – Ra