Difference between Iterator and Stream in Scala?

It seems that both Iterator and Stream are lazy and allow you to keep returning elements to your heart's content. What's the difference between the two?

Stream memoises and Iterator does not. You can traverse the same Stream multiple times and get the same result each time. Iterator, on the other hand, can only be traversed once.

They are both constructs for accessing a current element, having a yet unknown list of remaining elements (the lazy tail).

Iterator is an imperative construct which you can only traverse once.

Stream is a functional construct. In theory you can traverse it multiple times (and as others mentioned, it won't recompute the already computed parts), but in practice because Streams are either infinite or very large (that is why you use it in the first place), holding reference to the full stream doesn't make much sense (you run into Out Of Memory pretty easy).

• Therefore you should always define streams using def and never put it into local variables which have a long-lived scope.
• There are also subtleties when writing recursive functions using Streams,
  • see Scala tail-recursive Stream processor function defined in trait holds reference to stream-head
  • How to write non-leaking tail-recursive function using Stream.cons in Scala?.
• There can be some unexpected behavior resulting from the fact that Scala's Stream is not lazy in its head, like
  • Stream flatMap leaks memory if mapper returns chain of empty results

Generally it is safer to the mind to avoid plain Streams. Alternatives are using EphemeralStream of Scalaz which auto-forgets unreferred parts using weak references, or using Iteratees (see also here) or something similiar.