Add zipWith to NonEmptyList

[LukaJCB]

There's currently no way to zip two (or more) NELs, I think it is a very common use case and would be a worthwhile addition. We could even maybe generalize it to Reducible. Will have to look into that. What do you think?

[LukaJCB]

After trying to generalize and optimize for some time, I came to the conclusion that the simplest solution is this:

def zipWith[B, C](nel: NonEmptyList[B])(f: (A, B) => C): NonEmptyList[C] = 
  NonEmptyList.fromListUnsafe((nelA.toList, nelB.toList).zipped.map(f))

It's possible to zip two Foldable f, Monoidk f, but no clue how to do it without.

[LukaJCB]

There's also this:

def zipWith[F[_]: Traverse, A, B, C](fa: F[A], fb: F[B])(f: (A, Option[B]) => C): F[C]

But I'm not sure if I like it. I'd probably prefer to define on NEL and NEV individually.

[johnynek]

I think the issue here with being generic is that zipWith is just map2, but as you know (see #1837 ) there are sometimes conflicting Apply definitions. In this case, the "zip" apply is not the same as the flatMap apply. So, once we have the Parallel typeclass, we can have a ZipNonEmptyList Applicative which is the parallel version.

For now, the zipWith on NonEmptyList, what about:

def zipWith[B, C](that: NonEmptyList[B])(f: (A, B) => C): NonEmptyList[C] = {
  def zwRev(as: List[A], bs: List[B], acc: List[C]): List[C] = {
    case (Nil, _) => acc
    case (_, Nil) => acc
    case (a :: as, b :: bs) => zwRev(as, bs, f(a, b) :: acc)
  }
  NonEmptyList(f(this.head, that.head), zwRev(this.tail, that.tail, Nil).reverse)
}

in this way we avoid the double allocations of .zipped and .map.

Worth it for library code that will be used over and over.

[LukaJCB]

.zipped doesn't actually allocate AFAIK. But yeah, I agree your implementation is nicer. I'll create a PR :)

[LukaJCB]

Did a quick benchmark with sbt-jmh, here are the results for zipping 100k elements :)

NonEmptyList:

[info] # Run complete. Total time: 00:13:36
[info]
[info] Benchmark         Mode  Cnt    Score   Error  Units
[info] Main.testRecur   thrpt  200  544.180 ± 6.412  ops/s
[info] Main.testZipped  thrpt  200  427.152 ± 4.361  ops/s

NonEmptyVector:

[info] # Run complete. Total time: 00:13:42
[info] 
[info] Benchmark         Mode  Cnt    Score   Error  Units
[info] Main.testRecur   thrpt  200   34.495 ± 0.265  ops/s
[info] Main.testZipped  thrpt  200  614.801 ± 6.028  ops/s

Not super surprising, since pattern matching on Vectors is pretty inefficient. But good to know your algorithm is faster than the standard library for NELs ;)

PR including tests to follow!

[johnynek]

pretty sad that the naive functional zipWith is faster than the standard library.

thanks for tacking this so well (benchmarks, great PR)!