Scala: What is the difference between Traversable and Iterable traits in Scala collections?

I have looked at this question but still don't understand the difference between Iterable and 开发者_StackOverflow社区Traversable traits. Can someone explain ?

---

Think of it as the difference between blowing and sucking.

When you have call a Traversables foreach, or its derived methods, it will blow its values into your function one at a time - so it has control over the iteration.

With the Iterator returned by an Iterable though, you suck the values out of it, controlling when to move to the next one yourself.

---

To put it simply, iterators keep state, traversables don't.

A Traversable has one abstract method: foreach. When you call foreach, the collection will feed the passed function all the elements it keeps, one after the other.

On the other hand, an Iterable has as abstract method iterator, which returns an Iterator. You can call next on an Iterator to get the next element at the time of your choosing. Until you do, it has to keep track of where it was in the collection, and what's next.

---

tl;dr Iterables are Traversables that can produce stateful Iterators

---

First, know that Iterable is subtrait of Traversable.

Second,

• Traversable requires implementing the foreach method, which is used by everything else.

• Iterable requires implementing the iterator method, which is used by everything else.

For example, the implemetation of find for Traversable uses foreach (via a for comprehension) and throws a BreakControl exception to halt iteration once a satisfactory element has been found.

trait TravserableLike {
  def find(p: A => Boolean): Option[A] = {
    var result: Option[A] = None
    breakable {
      for (x <- this)
        if (p(x)) { result = Some(x); break }
    }
    result
  }
}

In contrast, the Iterable subtract overrides this implementation and calls find on the Iterator, which simply stops iterating once the element is found:

trait Iterable {
  override /*TraversableLike*/ def find(p: A => Boolean): Option[A] =
    iterator.find(p)
}

trait Iterator {
  def find(p: A => Boolean): Option[A] = {
    var res: Option[A] = None
      while (res.isEmpty && hasNext) {
        val e = next()
        if (p(e)) res = Some(e)
      }
    res
  }
}

It'd be nice not to throw exceptions for Traversable iteration, but that's the only way to partially iterate when using just foreach.

From one perspective, Iterable is the more demanding/powerful trait, as you can easily implement foreach using iterator, but you can't really implement iterator using foreach.

---

In summary, Iterable provides a way to pause, resume, or stop iteration via a stateful Iterator. With Traversable, it's all or nothing (sans exceptions for flow control).

Most of the time it doesn't matter, and you'll want the more general interface. But if you ever need more customized control over iteration, you'll need an Iterator, which you can retrieve from an Iterable.

---

Daniel's answer sounds good. Let me see if I can to put it in my own words.

So an Iterable can give you an iterator, that lets you traverse the elements one at a time (using next()), and stop and go as you please. To do that the iterator needs to keep an internal "pointer" to the element's position. But a Traversable gives you the method, foreach, to traverse all elements at once without stopping.

Something like Range(1, 10) needs to have only 2 integers as state as a Traversable. But Range(1, 10) as an Iterable gives you an iterator which needs to use 3 integers for state, one of which is an index.

Considering that Traversable also offers foldLeft, foldRight, its foreach needs to traverse the elements in a known and fixed order. Therefore it's possible to implement an iterator for a Traversable. E.g. def iterator = toList.iterator