I want to implement my custom function minWithIndex, so I looked into zipWithIndex function from scala library.
I am having trouble understanding.

I know what the function does, but cannot figure out how it does it.
Thank in advance

def zipWithIndex[A1 >: A, That](implicit bf: CanBuildFrom[Repr, (A1, Int), That]): That = {

    val b = bf(repr)

    var i = 0

    for (x <- this) {

      b += ((x, i))

      i += 1

    }

    b.result()

  }

Your question looks like actually two different questions:

1. How Scala standard library collections are designed and particularly how zipWithIndex works?




2. How to implement my custom minWithIndex?

Unfortunately the first question is probably more complicated than the second one.

Scala collections design

As of version 2.12 current scala.collection is designed to be very flexible but it comes with a cost of using many advanced features and/or design patterns. Also one might argue that it is over-engineered for the real-world usages and thus it is hard to understand for a Scala novice.

Designing collections library is a known hard problem because ideally you want to capture many different aspects. The main things is that you probably want to capture as many aspects as possible but at the same time has as little code duplication as possible. (For example consider linked-list vs array-based list. Both probably should have method like indexOf that can be implemented in terms of size and getByIndex so ideally you'd like to have only one implementation here.) This is a real design challenge.

Here is a non-exhaustive list of aspects that affected Scala's collections design (you may also find some design notes on the earlier (2.8) version here):

• Unified interfaces for different data structures implementing similar things (for example linked-list vs. array-based list are very similar while linked-list vs tree-based set are much less similar but still have something common). This is the reason for various traits such as Seq or GenTraversableLike and deep inheritance hierarchy.




• Type-safety. We want a list of integers to be a different type from a list of strings. And we'd like to know the type of the stored elements. This is why all the collections are generic.




• Performance. In every language standard collections are one of the most used pieces of code so good performance is very important. This is the reason why in several places there is an "impure" mutable implementation for a pure immutable FP interfaces.




• Separate read-only and mutable collections (especially important in the FP-languages but in others as well). This is why there are scala.collection, scala.collection.mutable and scala.collection.immutable packages.




• Support for potentially unlimited sequences such as generated (Fibonacci numbers) or coming from an external source (such as sequence of bytes read from console input). This is the reason for things like TraversableOnce or Iterable.




• Support for sequences that can't be (easily) processed twice. For example a stream of all the deals on some major stock exchange is so huge that it can't be stored and re-processed. This is the reason for TraversableOnce vs Traversable




• Internal vs external iteration (this is the reason of separation between Iterable vs Traversable)




• Eager vs. lazy computations (this is the reason for "View"-suffixed types)




• Support of the collection-like objects that are not collections. For example, you are implementing HTML-parser or even browser. Many HTML-elements can have children but being a collection of children is not the main responsibility. This is the reason for various traits with 'Gen` prefix.

Now let's get back to zipWithIndex. This is one of many methods (other similar ones are map, fitler and many others) that pose additional challenges for the designers: those methods produce new collection from the current one. On the one hand such methods can be implemented generically one time for all collections, on the other hand with naive implementation we will lose specific types and even worse we might be forced to change implementation and thus probably semantics. Consider this naive implementation of filter method:

trait Iterable[A] {

  def filter(p: A => Boolean): ? = {

    var res: List[A] = Nil

    for (x <- this)

      if (p(x)) res = x :: res

    res

  }

}

What return type to put instead of the ?? If we put just Iterable[A] it means that we immediately lost the ability to use all the methods of the List that are not available in the Iterable (such as access by index). But another thing is what if our Iterable actually was a Set. We probably want the result of the filter to be a Set again instead of a List. This is the thing that the reference above article calls the "same-result-type principle". Scala is one of the few languages that allows you to design an elegant solution for this problem with minimal code duplication. The main idea is to have a companion object for each implementation (for example Iterable and immutable.List) and also a companion trait for each intermediate trait (for example SeqFactory. One of the crucial things those companions provide is an ability to create a new instance of the "same" collection (probably with a different generic type).

And the last thing that is not covered in the referenced article is the CanBuildFrom implicit parameter. The logic behind it is following: assume you have a linked-list (List) and want to have an array-based list (Vector) zipped with index. Do you have to create an intermediate linked-list zipped with index in the process? CanBuildFrom is the trick that allows the answer to be: No, you don't have to. Implicit parameters is a fairly advanced feature of Scala and you probably should read more on it if you are not already familiar. The idea is that the compiler can automatically search for a parameter of matching type. So if there is any value matching the type is the scope, the code will compile. It means that the presence of a CanBuildFrom can be used as an evidence that you can change collection's underlying data structure at the same time as you do some data manipulation (zipWithIndex, map, filter, etc.). Each companion object provides default CanBuildFrom value with the same target data structure (for example see immutable.List.canBuildFrom).

So now we can see how IterableLike.zipWithIndex, which is the default implementation for all subtypes, is implemented

  def zipWithIndex[A1 >: A, That](implicit bf: CanBuildFrom[Repr, (A1, Int), That]): That = {

    val b = bf(repr)

    var i = 0

    for (x <- this) {

      b += ((x, i))

      i += 1

    }

    b.result()

  }

The signature says that using zipWithIndex you can convert your collection Repr of A into That - a collection of tuples (A1, Int) as long as

1. 
   A1 is a supertype of A (which is a safe upcast)


2. You have an evidence that you can build That from Repr (the bf object)

And what the method does is it asks the bf evidence to create b - a new Builder[(A1, Int), That], then fill the builder with tuples, and finally return the That collection from the builder (b.result()). Both builder and for with var i are used for performance reasons.

How to implement your own minWithIndex

The answer depends on how generic you want it to be and how much performance is important for you. Here are some options:

implicit class MinWithIndexOps[A, Repr <: IterableLike[A, Repr]](it: IterableLike[A, Repr]) {

  def minWithIndexWithZip[B >: A](implicit cmp: Ordering[B], bf: CanBuildFrom[Repr, (A, Int), Iterable[(A, Int)]]): (A, Int) = it.zipWithIndex(bf).min(Ordering.by[(A, Int), B]((kv: (A, Int)) => kv._1))



  def minWithIndexWithFold[B >: A](implicit cmp: Ordering[B]): (A, Int) = {

    if (it.isEmpty)

      throw new UnsupportedOperationException("empty.min")



    val h = it.head

    val res = it.foldLeft((h, 0, 0))((acc, cur) => acc match {

      case (minVal, minIndex, curIndex) => if (cmp.lteq(minVal, cur)) (minVal, minIndex, curIndex + 1) else (cur, curIndex, curIndex + 1)

    })

    (res._1, res._2)

  }



  def minWithIndexWithVars[B >: A](implicit cmp: Ordering[B]): (A, Int) = {

    if (it.isEmpty)

      throw new UnsupportedOperationException("empty.min")



    var minVal = it.head

    var minIndex = 0

    var i = 0

    for (cur <- it) {

      if (cmp.gt(minVal, cur)) {

        minVal = cur

        minIndex = i

      }

      i += 1

    }

    (minVal, minIndex)

  }

}





def test(): Unit = {

  val data = "qwerty" :: "asdfg" :: "zxcvb" :: Nil



  println(data.minWithIndexWithZip)

  println(data.minWithIndexWithFold)

  println(data.minWithIndexWithVars)

}

Note that here implicit keyword is used in a different meaning to create an implicit class that effectively extends every instance of IterableLike with new methods.

First implementation minWithIndexWithZip is very straightforward but probably very inefficient: you literally first do zipWithIndex and then call min (note also that the standard min uses an unusual for Scala convention of throwing exception instead of returning Option[A] and I used the same semantics in other implementations). This method is inefficient because you have to create whole new collection just to be disposed almost immediately.

minWithIndexWithFold is a different implementation that does not rely on zipWithIndex and uses foldLeft instead. fold is at the same time a very basic and very generic operation. One benefit of this code is that it is also immutable. But because of that its performance is also not good: a lot of intermediate accumulator objects will be created and disposed almost immediately.

The last minWithIndexWithVars is probably the least "pure" but the most performant version that uses straightforward imperative-like code.

I have seen scala using mutable solutions sometimes internally. Same with their implementation of zipWithIndex.

It is basically :

• iterating over the collection (for loop)


• for each element creating a tuple (a, Int) and


• appending them to mutable mutable buffer (b += ((x, i)))

So, for input List("first", "second"), you get List(("first", 1), ("second", 2)) after zipWithIndex.

scala> List("first", "second").zipWithIndex

res3: List[(String, Int)] = List((first,0), (second,1))

You can solve the same using recursive approach with immutability,

object MyZippedCollection {



  def main(args: Array[String]): Unit = {



    def zipWithIndex[a](list: List[a]): List[(a, Int)] = {



      def zipWith(index: Int, acc: List[(a, Int)], list: List[a]): List[(a, Int)] = {

        if (list.isEmpty) acc

        else zipWith(index + 1, acc :+ (list.head, index), list.tail)

      }



      zipWith(0, List.empty[(a, Int)], list)

    }



    val myList = List("scala", "fp", "haskell")



    zipWithIndex(myList).foreach { case (value, index) =>

      println(s"[$index]: $value")

    }

  }

}