CODEWITHSUNDEEP
scalashapelesshlist
Uspenskiy Vladimir
Uspenskiy Vladimir

Reputation: 149

How to implement zipWithIndex on HLists

Writting algorithm on HList, I need a zipWithIndex function. It is not at the shapeless library by now, so I decided to implement it.

It is quite obvious that it might be implemented as 

hlist.zip(indexes)

where indexes is the HList of the indexes (0..n), that probably could be obtained this way:

val indexes = Nat._0 until hlist.length

Issue here is that Nat doesn't have until method. I haven't found any Witness for the HList index to use with HList.map.

What is the method I could use to obtain HList of Nats starting with Nat._0 till hlist.length?

Upvotes: 4

Views: 414

Answers (1)

Travis Brown
Travis Brown

Reputation: 139028

It might make sense to add something like this to Shapeless:

import shapeless._, ops.hlist.Prepend

trait Range[A <: Nat, B <: Nat] extends DepFn0 { type Out <: HList }

object Range {
  type Aux[A <: Nat, B <: Nat, Out0 <: HList] = Range[A, B] { type Out = Out0 }

  implicit def emptyRange[A <: Nat]: Aux[A, A, HNil] = new Range[A, A] {
    type Out = HNil
    def apply(): Out = HNil
  }

  implicit def slightlyBiggerRange[A <: Nat, B <: Nat, OutAB <: HList](implicit
    rangeAB: Aux[A, B, OutAB],
    appender: Prepend[OutAB, B :: HNil],
    witnessB: Witness.Aux[B]
  ): Aux[A, Succ[B], appender.Out] = new Range[A, Succ[B]] {
    type Out = appender.Out
    def apply(): Out = appender(rangeAB(), witnessB.value :: HNil)
  }
}

def range[A <: Nat, B <: Nat](implicit r: Range[A, B]): r.Out = r()

Now you can write zipWithIndex pretty cleanly:

import ops.hlist.{ Length, Zip }

def zipWithIndex[L <: HList, S <: Nat, R <: HList, Out <: HList](l: L)(implicit
  len: Length.Aux[L, S],
  range: Range.Aux[nat._0, S, R],
  zipper: Zip.Aux[L :: R :: HNil, Out]
): Out = l.zip(range())

And then:

import nat._

type Expected = (Int, _0) :: (Symbol, _1) :: (String, _2) :: HNil

val xs: Expected = zipWithIndex(1 :: 'a :: "foo" :: HNil)

You could also use a fold or a ZippedWithIndex[L <: HList] type class, both of which might be a little more concise, but less clearly composed out of independently useful pieces like Range.

Upvotes: 6

Related Questions