title: Effective check for value existence in the Scala Stream (in functional manner)
body: <p>I've come upon <a href="http://www.reddit.com/r/scala/comments/35oawi/checking_for_value_existed_earlier_in_the_stream/" rel="nofollow">this question on reddit</a> - I become quite puzzled with it, but I have no idea (and seems there were no satisfying answer). I dare to copy it here:</p>
  
  <p>Suppose we have a stream with each element depending on its predecessor, like for siimple pseudo-random sequence, e.g.:</p>
  
  <pre><code>def neum(a:Int): Stream[Int] = Stream.iterate(a)(a =&gt; (a*a/100)%10000)
  </code></pre>
  
  <p><em>This is a von-Neumann's randomizer from the <a href="http://www.codeabbey.com/index/task_view/neumanns-random-generator" rel="nofollow">exercise</a> referenced by the question</em></p>
  
  <p>and starting with given value we want to know when the sequence comes to a loop. We can easily do this in imperative form, using a Set for storing values:</p>
  
  <pre><code>// like in java
  Set&lt;Integer&gt; values = new HashSet&lt;&gt;();
  while (true) {
      int x = nextValueInSequence(x)
      if (values.contains(x)) {
          break;
      }
      values.add(x);
  }
  </code></pre>
  
  <p>However with Scala it is interesting to come up with "functional" solution. But the author of the question seems to have no idea how this could be achieved preserving <code>O(N)</code> time complexity. Me too. The only comment there looks like suggesting straightforward <code>O(N^2)</code> solution.</p>