Discovering a functional algorithm from a mutable one
- by Garrett Rowe
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?
