Scala: An idiomatic way to generate a fixed-length sequence (folding an infinite stream?)

Question

Consider the task of creating a sequence of random numbers with the restriction that the final sequence must have a fixed length n , and the previous / subsequent elements must be different (i.e., the neighboring ones must be different). My first idiomatic approach would be something like this:

 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, because foldLeft tries to use the entire infinite stream, which leads to an infinite loop. Intuitively and in accordance with this question, would I expect this behavior only for solutions using foldRight ? Maybe I just miss another idiomatic solution?

Answer 1

You can use the self-running thread trick:

 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 consecutive equal elements and finally take the desired amount.

Update: Yes, it will work. Suppose you have [1,2,2,2,3,...] . Its completion will lead to [(1,2),(2,2),(2,2),(2,3),(3,..),...] , filtering creates [(1,2),(2,3),(3,..),...] , so the final result is [1,2,3,...] .

We can even prove this: after pairing, the sequence has the following property: a(i)._2 = a(i+1)._1 . This property is saved during the filtering phase. The filtering step also provides a(i)._1 != a(i)._2 . Putting it together, we get a(i)._1 != a(i)._2 = a(i+1)._1 so really a(i)._1 != a(i+1)._1 .

---

The problem with your approach using fold is that you are creating a bottom-up stream in your fold function. This means that to evaluate the stream header, you need to evaluate an endless sequence of operations :+ , although the head remains unchanged. The correct flow should be built from top to bottom - calculate its head and postpone the calculation of the rest in the tail. For instance:

 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 first radiate the head and set aside the rest of the calculation on a lazily priced tail.

Answer 2

I have not tested it yet, but I hope you understand:

 @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 stripping the thread with my own head is a really good 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: From this you will get an Iterator, not a stream. A thread remembers its result (and therefore, it repeats several times). An iterator can 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 }