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

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

While zipping the stream with its own head is a really nice trick, I prefer the sliding operator:

val s = Stream.continually { Random.nextInt(10) } sliding(2) collect { case Stream(a,b) if a!=b => a } take 100 

Beware: You get an Iterator out of this, not a Stream. A Stream memorizes its result (and is therefor iterable multiple times). A iterator might be iterable only once.

Answer 4

So, how about this:

scala> val M = 10
M: Int = 10

scala> val seq = Stream.iterate(Random.nextInt(M)){ x => 
         val nxt = Random.nextInt(M-1); if(nxt >= x) nxt + 1 else nxt 
       }