Discovering a functional algorithm from a mutable one

Question

This isn't necessarily a Scala question, it's a design question that has to do with avoiding mutable state, functional thinking and that sort. It just happens that I'm using Scala.

Given this set of requirements:

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

• Final output is either SUCCEED or FAIL

• There can be multiple objects 'listening' to the stream at any particular time, and they can begin listening at different times so they all may have a different concept of the 'first' number; therefore listeners to the stream need to be decoupled from the stream itself.

Pseudocode:

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
  }
}

This will work but smells to me. StreamListener.evaluate is not referentially transparent. And the use of the NoResult token just doesn't feel right. It does have the advantage though of being clear and easy to use/code. Besides there has to be a functional solution to this right?

I've come up with 2 other possible options:

• Having evaluate return a (possibly new) StreamListener, but this means I would have to make Result a subtype of StreamListener which doesn't feel right.

• Letting evaluate take a Stream[Int] as a parameter and letting the StreamListener be in charge of consuming as much of the Stream as it needs to determine failure or success. The problem I see with this approach is that the class that registers the listeners should query each listener after each number is generated and take appropriate action immediately upon failure or success. With this approach, I don't see how that could happen since each listener is forcing evaluation of the Stream until it completes evaluation. There is no concept here of a single number generation.

Is there any standard Scala/FP idiom I'm overlooking here?

Answer 1

I don't know Scala, but e.g. in Haskell lists are lazy and can represent 'streams', and 'call by need' ensures the list/stream is only evaluated as far as needed (and each cell only once).

In F#, in the PowerPack there is a LazyList module that behaves the same way. That is, you can define an infinite stream of values, pattern match on it like a head/rest list, only evaluate 'as needed', and different consumers can have different 'pointers' into it at different locations (like an immutable head/rest list, only the evaluation effects are synchronized for the most-advanced 'pointer' on the 'frontier' of evaluation).

So I think you just need the right 'data structure' like a lazy list, and the rest falls out naturally. (Side note: your function as spec'd can get stuck in an infinite loop (non-termination), which is a kind of effect maybe.)

Answer 2

Considering your first possible option, I'm not sure why you would make Result a sub-type of StreamListener instead of making just the specific sub-types of Result that are relevant be 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, aren't you just shuffling the mutability up to the calling code to track the references to Results/StreamListeners?