# Scala: Idiomatic way to generate a fixed length sequence (folding infinite stream?)

### Tags:

#### folding

Let's consider the problem of generating a sequence of random numbers, with the constraint that the final sequence should have a fixed length `n` and the preceding/subsequent elements should be different (i.e. neighbors should be different). My first idiomatic approach would be something like:

``````val seq = Stream.continually{ Random.nextInt(10) }
.foldLeft(Stream[Int]()){ (all: Stream[Int], next: Int) =>
if (all.length > 0 && all.last != next)
all :+ next
else
all
}
.take(n)
``````

Unfortunately, this does not work, since the foldLeft tries to consume the whole infinite stream, resulting in an endless loop. Intuitively and according to this question I would have expected this behavior only for solutions using `foldRight`? Maybe I'm just missing another idiomatic solution?

319

#### bluenote10

You can use the trick with zipping a stream with itself:

``````def randSeq(n: Int): Stream[Int] = {
// an infinite stream of random numbers
val s = Stream.continually{ Random.nextInt(10) }
s.zip(s.tail) // pair each number with it sucessor
.filter((pair) => pair._1 != pair._2) // filter out equal pairs
.map(_._1)   // break pairs again
.take(n);    // take first n
}
``````

Then you can filter out successive equal elements and finally take the desired amount.

Update: Yes, it will work. Suppose you have `[1,2,2,2,3,...]`. Zipping it will result in `[(1,2),(2,2),(2,2),(2,3),(3,..),...]`, filtering produces `[(1,2),(2,3),(3,..),...]` so the final result is `[1,2,3,...]`.

We can even prove it: After pairing, the sequence has the following property: `a(i)._2 = a(i+1)._1`. This property is preserved in the filtering step. The filtering step also ensures that `a(i)._1 != a(i)._2`. Put together we get `a(i)._1 != a(i)._2 = a(i+1)._1` so indeed `a(i)._1 != a(i+1)._1`.

The problem with your approach using `fold` is that you're building the Stream bottom-up in your fold function. This means that in order to evaluate the head of the stream you have to evaluate an infinite sequence of `:+` operations, even though the head stays the same. A proper stream must be constructed top-down - compute its head and defer the computation of the rest in its tail. For example:

``````def randSeq1(n: Int): Stream[Int] = {
def g(s: Stream[Int]): Stream[Int] =
s match {
case h #:: t => h #:: g(t.dropWhile(_ == h))
}
g(Stream.continually{ Random.nextInt(10) }).take(n);
}
``````

Here we emit the head first and defer the rest of the computation to the lazily evaluated tail.

152

#### Petr

I haven't checked it yet, but I hope you will get the idea:

``````@annotation.tailrec
def rndDistinctItems(n: Int, xs: List[Int] = Nil): List[Int] = if (n > 0) {
val next = Random.nextInt(10)
val shouldTryAgain = xs != Nil && next == xs.head
if (shouldTryAgain) rndDistinctItems(n, xs)
else rndDistinctItems(n - 1, next::xs)
} else xs
``````
22