Maintain references to a source even when performing operations such as map or flatMap.

projection-scalatest.scala

import org.scalatest.enablers.{Emptiness, Sequencing}

import scala.collection.GenTraversable
import scalaz.~>

trait ProjectionScalaTest {
  object listToStream extends (List ~> Stream) {
    override def apply[A](fa: List[A]): Stream[A] = fa.toStream
  }

  object streamToVector extends (Stream ~> Vector) {
    override def apply[A](fa: Stream[A]): Vector[A] = fa.toVector
  }

  implicit def sequencing[F[+_], A, B](implicit s: Sequencing[F[(A, B)]]): Sequencing[Projection[F, A, B]] =
    new Sequencing[Projection[F, A, B]] {
      override def containsInOrderOnly(projection: Projection[F, A, B], eles: Seq[Any]): Boolean =
        s.containsInOrderOnly(projection.source, eles)

      override def containsTheSameElementsInOrderAs(leftProjection: Projection[F, A, B], rightSequence: GenTraversable[Any]): Boolean =
        s.containsTheSameElementsInOrderAs(leftProjection.source, rightSequence)

      override def containsInOrder(projection: Projection[F, A, B], eles: Seq[Any]): Boolean =
        s.containsInOrder(projection.source, eles)
    }

  implicit def emptiness[F[+_], A, B](implicit e: Emptiness[F[(A, B)]]): Emptiness[Projection[F, A, B]] =
    new Emptiness[Projection[F, A, B]] {
      override def isEmpty(projection: Projection[F, A, B]): Boolean =
        e.isEmpty(projection.source)
    }
}

projection-unit-test.scala

import oncue.collections.recommendations.test.UnitSpec

import scala.concurrent.duration.Duration
import scala.concurrent.{Await, Future}
import scalaz.{Bifunctor, Functor, Plus, PlusEmpty, ~>}

class ProjectionTest extends UnitSpec with ProjectionScalaTest {
  import scalaz.std.list.listInstance
  import scalaz.std.vector.vectorInstance
  import scalaz.std.stream.streamInstance

  "Projection" must "materialize a Functor" in {
    val canMaterialize = implicitly[Functor[({type L[B] = Projection[List, Int, B]})#L]]

    val p = Projection(List(1, 2, 3))
    Projection.functorFrom(p) must be (p.F)

    val f = Projection.functor[List, Int]
    f.map(p)(i => i * 2) must contain inOrderOnly ((1, 2), (2, 4), (3, 6))
  }

  it must "materialize a Bifunctor" in {
    val canMaterialize = implicitly[Bifunctor[({type L[A, B] = Projection[List, (Int, A), B]})#L]]
    val bf = Projection.bifunctor[List, Int]

    val p1 = Projection(List(1, 2, 3))

    // We have mapped the original by multiplying by 100 and the projected value by
    // converting to a string and appending "!"
    val p2 = bf.bimap(p1)(_ * 100, _ + "!")
    p2 must contain inOrderOnly (((1, 100), "1!"), ((2, 200), "2!"), ((3, 300), "3!"))
  }

  it must "materialize a Plus" in {
    import scalaz.syntax.plus._

    val canMaterialize = implicitly[Plus[({type L[B] = Projection[List, Int, B]})#L]]
    val plus = Projection.plus[List, Int]

    val p1 = Projection(List(1, 2, 3))

    val p2 = plus.plus(p1, p1)
    val p3 = p1 <+> p1 // ToPlusOps[({type L[B] = Projection[List, Int, B]})#L, Int](p1)(plus) <+> p1

    p2 must equal (p3)
    p2 must contain theSameElementsInOrderAs List((1, 1), (2, 2), (3, 3), (1, 1), (2, 2), (3, 3))
  }

  it must "materialize a PlusEmpty" in {
    val canMaterialize = implicitly[PlusEmpty[({type L[A] = Projection[List, A, A]})#L]]
    val plusEmpty = Projection.plusEmpty[List]

    val p1 = Projection(List(1, 2, 3))

    val p2 = plusEmpty.empty[Int]
    p2 must be (empty)

    val p3 = plusEmpty.plus(p1, p1)
    p3 must contain theSameElementsInOrderAs List((1, 1), (2, 2), (3, 3), (1, 1), (2, 2), (3, 3))
  }

  it must "materialize a Bifoldable" in {
    import scalaz.std.anyVal.intInstance
    import scalaz.syntax.bifoldable._

    val sum = Projection(List(1, 2, 3)).bifoldMap(identity)(identity)
    sum mustBe 12
  }

  it must "translate correctly" in {
    val p1 = Projection(List(1, 2, 3))
    val p2 = p1.translate(listToStream)
    p2.result must contain theSameElementsInOrderAs Stream(1, 2, 3)
  }

  it must "accumulate correctly" in {
    import scalaz.std.anyVal.intInstance

    val p1 = Projection(List(1, 2, 3, 4))
    val p2 = p1.accumulate(i => Projection(List.fill(i)(i)))

    p2 must contain theSameElementsInOrderAs List((1, 1), (2, 4), (3, 9), (4, 16))
  }

  it must "have a cross-product number of items as are flatMapped" in {
    val p1 = Projection(List(1, 2, 3))
    val p2 = Projection.mapped[List, String, String](List("A" -> "A!", "B" -> "B!", "C" -> "C!"))
    val p3 = p1.flatMap(_ => p2)

    p3.length mustBe 9
    p3 must contain theSameElementsInOrderAs List(((1, "A"), "A!"), ((1, "B"), "B!"), ((1, "C"), "C!"), ((2, "A"), "A!"), ((2, "B"), "B!"), ((2, "C"), "C!"), ((3, "A"), "A!"), ((3, "B"), "B!"), ((3, "C"),"C!"))

    val p4 =
      for {
        i <- p1
        s <- p2
      } yield s

    p4 must equal (p3)
  }

  it must "support foreach" in {
    val buf = collection.mutable.Buffer[Int]()
    for (i <- Projection(Vector(1, 2, 3)))
      buf.append(i)
    buf must contain theSameElementsInOrderAs List(1, 2, 3)
  }

  it must "have a valid extractor" in {
    val p1 = Projection(Vector(1, 2, 3))
    val Projection(fromExtractor) = p1
    val fromMatch = p1 match {
      case Projection(source) => source
    }

    fromExtractor must equal (fromMatch)
  }

  it must "be traversable" in {
    import scala.concurrent.ExecutionContext.Implicits.global

    // Manually.

    val p1 = Projection(List(1, 2, 3))
    val p2 = p1.map(i => Future {
      Thread.sleep(i * 100L)
      i + "!"
    })

    val result = Await.result(Future.sequence(p2.result), Duration.Inf)
    result must contain theSameElementsInOrderAs List("1!", "2!", "3!")

    val source = p2.map(_.value.flatMap(_.toOption).getOrElse("")).source
    source must contain theSameElementsInOrderAs List(1 -> "1!", 2 -> "2!", 3 -> "3!")

    // Use traverse.

    import scalaz.syntax.traverse._
    import scalaz.std.scalaFuture.futureInstance

    val p3: Future[Projection[List, Int, Int]] = p1.traverse(i => Future(i * 100))
    val p4 = Await.result(p3, Duration.Inf)
    p4 must contain theSameElementsInOrderAs List(1 -> 100, 2 -> 200, 3 -> 300)
  }

  it must "support views" in {
    val p1View = Projection(List(1, 2, 3)).view
    val p2View = p1View
      .translate(listToStream)
      .map(i => i + "00")
      .map(_.toDouble)
      .translate(streamToVector)
      .mapOrigin(i => i + "!")
      .mapOrigin(_ + "?")
      .map(_ + 1.0D)

    val p2 = p2View.run
    p2 must contain theSameElementsInOrderAs Vector((1, "1!?") -> 101.0D, (2, "2!?") -> 201.0D, (3, "3!?") -> 301.0D)
  }
}

projection.scala

import scalaz.{Applicative, Bifoldable, Bifunctor, Bind, Foldable, Functor, Monad, Monoid, NaturalTransformation, Plus, PlusEmpty, Show, Traverse, ~>}

/**
  * `Projection` provides a means for retaining references to a source while transforming it.
  *
  * Losing the original reference and having to re-establish the original ordering can be
  * cumbersome or inherently lossy. Safe means for ensuring fidelity to ordering and references
  * are provided by this class with unsafe type class implementations available in the companion
  * object that are lossy (they lose reference to the original).
  *
  * A view is available for queuing up transformations in an approach similar to the
  * [[scalaz.Coyoneda]].
  *
  * `Projection` itself is immutable, but immutability of this class is fundamentally dependent
  * on the type constructor `F`.
  *
  * @param source Instance of a type constructor `F` which provides a mapping from the origin to the result type
  * @param F Provides a [[scalaz.Functor]] for the type constructor `F`
  * @tparam F Type constructor which must be covariant in its type parameter
  * @tparam A Type of the origin reference
  * @tparam B Type that is projected and mapped. `A` is preserved across transformations while `B` changes.
  */
sealed class Projection[F[+_], +A, +B](val source: F[(A, B)])(implicit private[util] val F: Functor[F]) extends Equals { self =>
  import scalaz.syntax.functor._
  import scalaz.syntax.monoid._
  import scalaz.syntax.foldable._

  /**
    * Tracks transformations on a [[Projection]] without actually applying them. Instead, they are composed as they
    * are defined and only run when [[Projection!.View!.run]] is called.
    */
  class View[G[+_], +A1, +C](private[this] val opTranslate: F ~> G, private[this] val opMap: B => C, private[this] val opMapOrigin: A => A1) {
    val projection: Projection[F, A, B] = self

    def translate[H[+_] : Functor](nat: G ~> H): View[H, A1, C] =
      new View[H, A1, C](nat compose opTranslate, opMap, opMapOrigin)

    def map[D](fn: C => D): View[G, A1, D] =
      new View[G, A1, D](opTranslate, fn compose opMap, opMapOrigin)

    def mapOrigin[A2](fn: A1 => A2): View[G, A2, C] =
      new View[G, A2, C](opTranslate, opMap, (a: A) => {
        val a2 = opMapOrigin(a)
        val a3 = fn(a2)
        a3
      })

    /**
      * If `A1` represents a tuple, then map over the second element.
      */
    def mapOriginP[A2, A3, A4](fn: A3 => A4)(implicit ev: A1 <:< (A2, A3)): View[G, A4, C] =
      new View[G, A4, C](opTranslate, opMap, (a: A) => {
        val a2 = opMapOrigin(a)
        val (a3, a4) = ev(a2)
        fn(a4)
      })

    override def toString: String =
      s"Projection.View(" + source.toString + ")"

    override def hashCode(): Int =
      java.util.Objects.hash(
        source,
        opTranslate,
        opMap,
        opMapOrigin
      )


    def run(implicit GF: Functor[G]): Projection[G, (A, A1), C] =
      // Better than self.map(opMap).mapi(opMapOrigin).translate(opTranslate)
      // because it eliminates intermediate Projection instances.
      new Projection[G, (A, A1), C](opTranslate(source map { x =>
        val (a, b) = x
        val c = opMap(b)
        val a1 = opMapOrigin(a)
        ((a, a1), c)
      }))

    def runUnassociate(implicit GF: Functor[G]): Projection[G, A, C] =
    // Better than self.map(opMap).translate(opTranslate)
    // because it eliminates intermediate Projection instances.
      new Projection[G, A, C](opTranslate(source map { x =>
        val (a, b) = x
        val c = opMap(b)
        // Specifically does not use opMapOrigin.
        (a, c)
      }))
  }

  /** Construct a view of this [[Projection!]] that queues transformations without applying them. */
  def view = new View[F, A, B](NaturalTransformation.refl[F], identity, identity)

  def origin: F[A] = source map (_._1)

  def result: F[B] = source map (_._2)

  def length(implicit Fold: Foldable[F]): Int =
    Fold.length(source)

  /**
    * If `A` represents a tuple, then remove the second element and only propagate the first.
    */
  def unassociate[A1, A2](implicit ev: A <:< (A1, A2)): Projection[F, A1, B] =
    new Projection[F, A1, B](source map { x =>
      val (a, b) = x
      val (a1, a2) = ev(a)
      (a1, b)
    })

  def map[C](fn: B => C): Projection[F, A, C] =
    new Projection[F, A, C](source map (x => (x._1, fn(x._2))))

  def mapOrigin[A2](fn: A => A2): Projection[F, (A, A2), B] =
    new Projection[F, (A, A2), B](source map (x => ((x._1, fn(x._1)), x._2)))

  /**
    * If `A` represents a tuple, then map over the second element.
    */
  def mapOriginP[A1, A2, C](fn: A2 => C)(implicit ev: A <:< (A1, A2)): Projection[F, (A1, C), B] =
    new Projection[F, (A1, C), B](source map { x =>
      val (a, b) = x
      val (a1, a2) = ev(a)
      val c = fn(a2)
      ((a1, c), b)
    })

  def mapx[B2 >: B, C](fn: (A, B2) => C): Projection[F, A, C] =
    new Projection[F, A, C](source map (x => (x._1, fn(x._1, x._2))))

  def bimap[C, D](f: A => C)(g: B => D): Projection[F, (A, C), D] =
    new Projection[F, (A, C), D](source map (x => ((x._1, f(x._1)), g(x._2))))

  def translate[G[+_] : Functor](nat: F ~> G): Projection[G, A, B] =
    new Projection[G, A, B](nat(source))

  def foreach(fn: B => Unit): Unit = {
    source map (x => fn(x._2))
    ()
  }

  /**
    * Uses a given [[scalaz.Monoid]] to accumulate projected values produced by the given function `fn` and
    * re-associating the accumulated value with the original value `A`.
    */
  def accumulate[C, D : Monoid](fn: B => Projection[F, C, D])(implicit Fold: Foldable[F]): Projection[F, A, D] =
    new Projection[F, A, D](source.map { x =>
      val a = x._1
      val b = x._2
      val p = fn(b)
      val d = p.source.foldLeft(mzero) { (lastD, y) =>
        // Discards Cs and only looks at the projected value of the resulting Projection.
        val d = y._2
        lastD |+| d
      }
      (a, d)
    })

  def flatMap[C, D](fn: B => Projection[F, C, D])(implicit B: Bind[F]): Projection[F, (A, C), D] =
    new Projection[F, (A, C), D](B.bind(source) { x =>
      val a = x._1
      val b = x._2
      val p = fn(b)
      p.F.map(p.source) { y =>
        val c = y._1
        val d = y._2
        ((a, c), d)
      }
    })

  override def toString: String =
    s"Projection(${source.toString})"

  override def hashCode(): Int =
    source.hashCode

  override def equals(obj: Any): Boolean =
    obj match {
      case o: AnyRef if this eq o => true
      case p: Projection[_, _, _] => source equals p.source
      case _ => source equals obj
    }

  override def canEqual(that: Any): Boolean =
    equals(that)
}

object Projection extends LowPriorityProjectionImplicits {
  import scalaz.syntax.equal._

  def apply[F[+_] : Functor, A](given: F[A]): Projection[F, A, A] =
    new Projection[F, A, A](multiplyM(given))

  def mapped[F[+_] : Functor, A, B](given: F[(A, B)]): Projection[F, A, B] =
    new Projection[F, A, B](given)

  def unapply[F[+_], A, B](given: Projection[F, A, B]): Option[F[(A, B)]] =
    Some(given.source)

  def multiply[F[_], A](a: A)(implicit A: Applicative[F]): F[(A, A)] =
    A.point((a, a))

  def multiplyM[F[_], A](fa: F[A])(implicit F: Functor[F]): F[(A, A)] =
    F.map(fa)(a => (a, a))

  implicit def multiplyProjection[F[+_], A, B](given: Projection[F, A, B]): Projection[F, (A, A), B] =
    given.bimap(a => a)(identity)

  implicit def show[F[+_], A, B]: Show[Projection[F, A, B]] =
    Show.shows(_.toString)

  implicit def equal[F[+_], A, B](implicit eq: scalaz.Equal[F[(A, B)]]): scalaz.Equal[Projection[F, A, B]] =
    scalaz.Equal.equal((p1, p2) => p1.source === p2.source)

  implicit def functorFrom[F[+_], A, B](projection: Projection[F, A, B]): Functor[F] =
    projection.F

  implicit def functor[F[+_], A]: Functor[Projection[F, A, ?]] =
    new Functor[Projection[F, A, ?]] {
      override def map[B, C](fa: Projection[F, A, B])(f: B => C): Projection[F, A, C] =
        fa map f
    }

  implicit def bifunctor[F[+_], A]: Bifunctor[λ[(B, C) => Projection[F, (A, B), C]]] =
    new Bifunctor[λ[(B, C) => Projection[F, (A, B), C]]] {
      override def bimap[B, C, D, E](fab: Projection[F, (A, B), C])(f: B => D, g: C => E): Projection[F, (A, D), E] =
        new Projection(fab.F.map(fab.source) { x =>
          val a = x._1._1
          val b = x._1._2
          val c = x._2
          val d = f(b)
          val e = g(c)
          ((a, d), e)
        })(fab.F)
    }

  implicit def plus[F[+_] : Plus, A]: Plus[Projection[F, A, ?]] =
    new Plus[Projection[F, A, ?]] {
      import scalaz.syntax.plus._

      override def plus[B](a: Projection[F, A, B], b: => Projection[F, A, B]): Projection[F, A, B] =
        new Projection(a.source <+> b.source)(a.F) // Arbitrarily choose a's Functor
    }

  implicit def plusEmpty[F[+_] : Functor : PlusEmpty]: PlusEmpty[λ[A => Projection[F, A, A]]] =
    new PlusEmpty[λ[A => Projection[F, A, A]]] {
      import scalaz.syntax.plusEmpty._

      override def empty[A]: Projection[F, A, A] =
        new Projection(multiplyM(mempty[F, A]))

      override def plus[A](a: Projection[F, A, A], b: => Projection[F, A, A]): Projection[F, A, A] =
        new Projection(a.source <+> b.source)
    }

}

sealed trait LowPriorityProjectionImplicits extends LowPriorityUnsafeProjectionImplicits {
  implicit def traverse[F[+_], A](implicit T: Traverse[F]): Traverse[Projection[F, A, ?]] =
    new Traverse[Projection[F, A, ?]] {
      import scalaz.syntax.traverse._

      override def traverseImpl[G[_] : Applicative, B, C](fa: Projection[F, A, B])(f: B => G[C]): G[Projection[F, A, C]] =
        T.traverseImpl(fa.source)(x => f(x._2).map(c => (x._1, c))).map(new Projection(_))
    }
}

sealed trait LowPriorityUnsafeProjectionImplicits {
  /**
    * ''WARNING:'' Converting to a [[scalaz.Bifoldable]] is an unsafe operation because it loses
    * the original mappings. This is provided for convenience but does thwart the intent of
    * [[Projection]].
    */
  implicit def unsafeBifoldable[F[+_] : Foldable]: Bifoldable[Projection[F, ?, ?]] =
    new Bifoldable[Projection[F, ?, ?]] {
      import scalaz.syntax.foldable._
      import scalaz.syntax.monoid._

      override def bifoldMap[A, B, M : Monoid](fa: Projection[F, A, B])(f: A => M)(g: B => M): M =
        fa.source.foldLeft(mzero)((m, x) => m |+| f(x._1) |+| g(x._2))

      override def bifoldRight[A, B, C](fa: Projection[F, A, B], z: => C)(f: (A, => C) => C)(g: (B, => C) => C): C =
        fa.source.foldRight(z)((x, c) => g(x._2, c))
    }

  /**
    * ''WARNING:'' Converting to a [[scalaz.Bind]] is an unsafe operation because it loses
    * the original mapping. This is provided for convenience but does thwart the intent of
    * [[Projection]].
    *
    * The definition of [[scalaz.Bind!.bind]] prevents differences between the return type of
    * the function given to `bind` and the method return type. The return type must allow us to
    * carry forward the original value. Since the signature disallows this, it is considered
    * destructive or unsafe.
    */
  implicit def unsafeBind[F[+_] : Bind, A]: Bind[Projection[F, A, ?]] =
    new Bind[Projection[F, A, ?]] {
      import scalaz.syntax.bind._

      override def bind[B, C](fa: Projection[F, A, B])(f: B => Projection[F, A, C]): Projection[F, A, C] =
        new Projection[F, A, C](fa.source.flatMap(x => f(x._2).source))

      override def map[B, C](fa: Projection[F, A, B])(f: B => C): Projection[F, A, C] =
        fa map f
    }

  implicit def unsafeFoldable[F[+_] : Foldable, A]: Foldable[Projection[F, A, ?]] =
    new Foldable[Projection[F, A, ?]] {
      import scalaz.syntax.foldable._

      override def foldMap[B, C : Monoid](fa: Projection[F, A, B])(f: B => C): C =
        fa.source.foldMap(x => f(x._2))

      override def foldRight[B, C](fa: Projection[F, A, B], z: => C)(f: (B, => C) => C): C =
        fa.source.foldRight(z)((x, c) => f(x._2, c))
    }

  implicit def unsafeApplicative[F[+_]](implicit M: Monad[F]): Applicative[λ[A => Projection[F, A, A]]] =
    new Applicative[λ[A => Projection[F, A, A]]] {
      import scalaz.syntax.monad._

      override def point[A](a: => A): Projection[F, A, A] =
        new Projection[F, A, A](Projection.multiplyM(a.point)(M))(M)

      override def ap[A, B](fa: => Projection[F, A, A])(fAp: => Projection[F, A => B, A => B]): Projection[F, B, B] =
        new Projection[F, B, B]({
          val fa0 = fa
          val applied = fa0.source.flatMap[(B, B)] { x =>
            val f0 = fAp

            val projectedA = x._2

            val afterProjection: F[(B, B)] = f0.F.map(f0.source) { y =>
              val projectedFn: A => B = y._2
              val originB: B = projectedFn(projectedA)
              (originB, originB)
            }

            afterProjection
          }

          applied
        })(M)
    }
}