Signature of new operations

collections.scala

trait Iterable[A] {
  
  // https://github.com/scala/collection-strawman/issues/221
  /**
    * Returns a collection formed by the result of applying a function to each pair of corresponding elements
    * from this collection and another collection. It is semantically equivalent to `(xs zip ys) map f`.
    * If one of the two collections is longer than the other, its remaining elements are ignored.
    */
  def zipWith[B, C](that: Iterable[B])(f: (A, B) => C): Iterable[C]

  // https://github.com/scala/collection-strawman/issues/107
  /**
    * Fold while accumulation function returns Some. Stops on first None.
    * @param init initual element to start the accumulation on
    * @param op accumulation function
    */
  def foldSomeLeft[B](init: B)(op: (B, A) => Option[B]): B
  /**
    * Same as `foldSomeLeft` but applies `op` from right to left.
    * Does not work on infinite collections (all the elements have
    * to be evaluated and reversed before the accumulation function
    * is applied).
    */
  def foldSomeRight[B](init: B)(op: (A, B) => Option[B]): B
  
  // https://github.com/scala/collection-strawman/issues/186
  /**
    * Stack-safe, right-to-left, folding operation that
    * can be short-circuited.
    */
  def lazyFoldRight[B](empty: => B)(f: A => FoldStep[B]): B
  
  sealed trait FoldStep[A]
  object FoldStep {
    case class Break[A](value: A) extends FoldStep[A]
    case class Pull[A](f: A => A) extends FoldStep[A]
  }

  // https://github.com/scala/collection-strawman/issues/42
  /**
    * Equivalent to `groupBy(key).mapValues(_.map(value))`, but more efficient.
    */
  def groupMap[K, B](key: A => K)(value: A => B): Map[K, Iterable[B]]
  /**
    * Equivalent to `groupBy(key).mapValues(_.map(value).reduce(reduce))` but more efficient.
    */
  def groupMapReduce[K, B](key: A => K)(value: A => B)(reduce: (B, B) => B): Map[K, B]
}

trait Seq[A] {
  
  // https://github.com/scala/collection-strawman/issues/208
  /** Adds the element `sep` between each element of the sequence.
    * If the sequence has less than two elements, the collection is unchanged.
    *
    * @param sep the element to intersperse
    * @tparam B the element type of the returned collection
    * @return a new collection consisting of all elements of this collection
    *         interspersed with the element `sep`
    */
  def intersperse[B >: A](sep: B): Seq[B]
  
  /** Adds the element `sep` between each element of the sequence,
    * prepending `start` and appending `end`.
    * If the sequence has less than two elements, returns `start +: this :+ end`.
    *
    * @param start the element to prepend
    * @param sep the element to intersperse
    * @param end the element to append
    * @tparam B the element type of the returned collection
    * @return a new collection consisting of all elements of this collection
    *         interspersed with the element `sep`, beginning with `start` and ending with `end`
    */
  def intersperse[B >: A](start: B, sep: B, end: B): Seq[B]
  
}

trait Map[K, V] {
  
  // https://github.com/scala/collection-strawman/issues/71
  /**
    * Combines entries of `this` Map with entries of `that` Map that have the same key,
    * using the combination function `f`
    */
  def zipByKeyWith[W, X](that: Map[K, W])(f: (V, W) => X): Map[K, X]
  /**
    * Combines entries of `this` Map with entries of `that` Map by tupling the values that have
    * the same key. This operation is similar to a SQL inner join.
    */
  def zipByKey[W](that: Map[K, W]): Map[K, (V, W)] = zipByKeyWith(that)(_ -> _)
  
  /**
    * Combines all the entries of `this` Map with all the entries of `that` Map by applying a function which is passed:
    * - `(Some(v), Some(w))` if both entries have the same key,
    * - `(Some(v), None)` if `that` has no entry with the same key as `v`’s entry,
    * - `None, Some(w)` if `this` has no entry with the same key as `w`’s entry.
    */
  def mergeByKeyWith[W, X](that: Map[K, W](f: PartialFunction[(Option[V], Option[W]), X]): Map[K, X]
  /** Operation similar to a SQL full outer join */
  def mergeByKey[W](that: Map[K, W]): Map[K, (Option[V], Option[W])] = mergeByKeyWith(that)(PartialFunction(identity))

  def leftOuterJoin[W](that: Map[K, W]): Map[K, (V, Option[W])] = mergeByKeyWith(that) { case (Some(v), optW) => v -> optW }
  def rightOuterJoin[W](that: Map[K, W]): Map[K, (Option[V], W)] = mergeByKeyWith(that) { case (optV, Some(w)) => optV -> w }
}

@julienrf can we make FoldStep.Pull an opaque type over the function so it doesn't allocate lots of useless wrappers?
FoldStep.Break would still be a case class because we need to distinguish it from the wrapped value, but that's okay because it is only called once per fold operation.