Benchmark `Traverse1[NonEmptyList].traverse1`

NelTraverseBench.scala

package cats.bench

import cats.{Apply, Foldable}
import cats.data.NonEmptyList
import cats.instances.option._
import cats.instances.list._
import cats.syntax.cartesian._
import cats.syntax.semigroup._
import org.openjdk.jmh.annotations.{Benchmark, Scope, State}

@State(Scope.Benchmark)
class NelTraverseBench {

  val numbers: NonEmptyList[Int] = NonEmptyList(0, List.range(1, 100))

  val f: Int => Option[Int] = Some(_)

  @Benchmark
  def traverse1(): Option[NonEmptyList[Int]] =
    _traverse1(numbers)(f)
  
  @Benchmark
  def _traverse1noOf(): Option[NonEmptyList[Int]] =
    _traverse1noOf(numbers)(f)

  @Benchmark
  def _traverse1prime(): Option[NonEmptyList[Int]] =
    _traverse1prime(numbers)(f)


  def _traverse1[G[_], A, B](as: NonEmptyList[A])(f: A => G[B])(implicit G: Apply[G]): G[NonEmptyList[B]] =
    as.map(a => G.map(f(a))(NonEmptyList.of(_)))
      .reduceLeft((acc, a) => (acc |@| a).map( _ |+| _ ))

  def _traverse1noOf[G[_], A, B](as: NonEmptyList[A])(f: A => G[B])(implicit G: Apply[G]): G[NonEmptyList[B]] =
    as.map(a => G.map(f(a))(NonEmptyList(_, Nil)))
      .reduceLeft((acc, a) => (acc |@| a).map( _ |+| _ ))

  def _traverse1prime[G[_], A, B](nel: NonEmptyList[A])(f: A => G[B])(implicit G: Apply[G]): G[NonEmptyList[B]] =
    Foldable[List].reduceRightToOption[A, G[List[B]]](nel.tail)(a => G.map(f(a))(_ :: Nil)) { (a, lglb) =>
      G.map2Eval(f(a), lglb)(_ :: _)
    }.map { 
      case None => G.map(f(nel.head))(NonEmptyList(_, Nil))
      case Some(gtail) => G.map2(f(nel.head), gtail)(NonEmptyList(_, _))
    }.value

}