Difference between Iterator and Stream in Scala?

Question

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?

score 53 · Accepted Answer · edited May 04 '13 at 09:01

53

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.

edited May 04 '13 at 09:01

Peter Mortensen

30,738
21
105
131

answered Oct 07 '09 at 03:33

Walter Chang

11,547
2
47
36

1

With regards to the memoization - if I access the Nth element, is the access time O(1) or O(N)? – ryeguy Oct 07 '09 at 04:14
7

@ryeguy It's O(n) because Stream builds a linked list to cache element values. – Walter Chang Oct 07 '09 at 04:44
1

OK, so what's the difference between Stream and Iterable then? – Martin Konicek May 30 '11 at 22:30
3

Does it mean that in the case of an infinitely long stream, memory usage will keep on increasing since Stream memoises the result and never throw them away? – lolski Apr 10 '15 at 06:12
2

@lolski: Yes, that is the case if you somewhere have a reference to the *first cell* of the stream. If you on the other hand overwrite the reference to the first cell as you read more elements, then earlier elements will get garbage collected. So you have to be a little careful so you don't hold on the the first element when you work with large streams. – Lii Aug 07 '16 at 08:45

score 24 · Answer 2 · edited May 23 '17 at 12:18

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.

I'm curious: why EphemeralStream is not a default implementation? You can always reconstruct forgotten part from data lineage (its a functional language). This sounds like a big design flaw. — tribbloid, May 08 '17 at 22:01

Difference between Iterator and Stream in Scala?

2 Answers2

Linked