Discovering a functional algorithm from a mutable one

Posted by Garrett Rowe on Stack Overflow See other posts from Stack Overflow or by Garrett Rowe
Published on 2010-05-10T21:13:12Z Indexed on 2010/05/10 22:04 UTC
Read the original article Hit count: 302

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?

© Stack Overflow or respective owner

Related posts about scala

Related posts about functional-programming