Detection of functional algorithm from volatile

Question

This is not necessarily a Scala issue, it is a design issue that is related to the prevention of a volatile state, functional thinking and such. It just happens that I use Scala.

Given this set of requirements:

• The input comes from an essentially infinite stream of random numbers between 1 and 10

• End result: SUCCEED or FAIL

• At any given time, there can be several listening to several objects, and they can start listening at different times, so that they all can have a different concept of the “first” number; therefore, stream listeners should be separate from the stream itself.

pseudo code:

if (first number == 1) SUCCEED else if (first number >= 9) FAIL else { first = first number rest = rest of stream for each (n in rest) { if (n == 1) FAIL else if (n == first) SUCCEED else continue } } 

Here is a possible mutable implementation:

 sealed trait Result case object Fail extends Result case object Succeed extends Result case object NoResult extends Result class StreamListener { private var target: Option[Int] = None def evaluate(n: Int): Result = target match { case None => if (n == 1) Succeed else if (n >= 9) Fail else { target = Some(n) NoResult } case Some(t) => if (n == t) Succeed else if (n == 1) Fail else NoResult } } 

It will work, but it smells to me. StreamListener.evaluate is not link transparent. And using the NoResult token just doesn't seem right. This has the advantage, although clear and user-friendly / code. Also, should there be a functional solution to this right?

I came up with two more options:

• Evaluating return a (possibly new) StreamListener, but that means I will need to make Result a subtype of StreamListener, which doesn't feel good.

• When evaluating, we will take Stream [Int] as a parameter and let StreamListener be responsible for consuming as much of the stream as possible, as it is necessary to determine failure or success. The problem that I see with this approach is that the class that registers the listeners must request each listener after creating each number and take the appropriate action immediately after a failure or success. With this approach, I don’t see how this can happen, as each listener forces Stream to evaluate until it completes the evaluation. There is no concept of generating a single number.

Is there any standard Scala / FP idiom I am looking at here?

Answer 1

Given your first possible option, I'm not sure why you would make Result a subtype of StreamListener instead of only making specific Result subtypes that are relevant to StreamListeners.

 sealed trait Result sealed trait FinalizedResult extends Result trait StreamListener { def evaluate(n: Int): Result } case object Uninitialized extends Result with StreamListener { def evaluate(n: Int): Result = { n match { case i if (n == 1) => Succeed case i if (n >= 9) => Fail case _ => Initialized(n) } } } case class Initialized(target: Int) extends Result with StreamListener { def evaluate(n: Int): Result = { n match { case i if (n == target) => Succeed case i if (n == 1) => Fail case _ => this } } } case object Succeed extends FinalizedResult case object Fail extends FinalizedResult 

But then you are not just dragging volatility to the calling code to track links to Results / StreamListeners?

Answer 2

I do not know Scala, but, for example, in Haskell lists, they are lazy and can represent "threads", and "calling as needed" ensures that the list / stream is evaluated only as necessary (and each cell only once).

In F #, PowerPack has a LazyList module that behaves the same. That is, you can determine the endless stream of values, the coincidence of patterns on it, as a list of goals / list, evaluate only “as needed”, and different consumers can have different “pointers” in different places (for example, a list of remains, only the evaluation effects are synchronized for the most advanced "pointer" on the "border" of the evaluation).

So I think you just need the right data structure, like a lazy list, and the rest is natural. (Lateral note: your function as spec'd may get stuck in an infinite loop (without interruption), which may be a bit of an effect.)