0

I'm working with below stuff as a way to learn functional programming and scala, I came from a python background.

case class Point(x: Int, y:Int)
object Operation extends Enumeration {
  type Operation = Value
  val TurnOn, TurnOff, Toggle = Value
}

object Status extends Enumeration {
  type Status = Value
  val On, Off = Value
}

val inputs: List[String]
def parseInputs(s: String): (Point, Point, Operation)

Idea is that we have a light matrix(Point), each Point can be either On or Off as describe in Status. My inputs is a series of command, asking to either TurnOn, TurnOff or Toggle all the lights from one Point to another Point (The rectangular area defined using two points are bottom-left corner and upper-right corner).

My original solution is like this:

type LightStatus = mutable.Map[Point, Status]
val lightStatus = mutable.Map[Point, Status]()

def updateStatus(p1: Point, p2: Point, op: Operation): Unit = {
  (p1, p2) match {
    case (Point(x1, y1), Point(x2, y2)) =>
      for (x <- x1 to x2)
        for (y <- y1 to y2) {
          val p = Point(x, y)
          val currentStatus = lightStatus.getOrElse(p, Off)
          (op, currentStatus) match {
            case (TurnOn, _) => lightStatus.update(p, On)
            case (TurnOff, _) => lightStatus.update(p, Off)
            case (Toggle, On) => lightStatus.update(p, Off)
            case (Toggle, Off) => lightStatus.update(p, On)
          }
        }
  }
}

for ((p1, p2, op) <- inputs.map(parseInputs)) {
  updateStatus(p1, p2, op)
}

Now I have lightStatus as a map to describe the end status of the entire matrix. This works, but seems less functional to me as I was using a mutable Map instead of an immutable object, so I tried to re-factor this into a more functional way, I ended up with this:

inputs.flatMap(s => parseInputs(s) match {
  case (Point(x1, y1), Point(x2, y2), op) =>
    for (x <- x1 to x2;
         y <- y1 to y2)
    yield (Point(x, y), op)
}).foldLeft(Map[Point, Status]())((m, item) => {
  item match {
    case (p, op) =>
      val currentStatus = m.getOrElse(p, Off)
      (op, currentStatus) match {
        case (TurnOn, _) => m.updated(p, On)
        case (TurnOff, _) => m.updated(p, Off)
        case (Toggle, On) => m.updated(p, Off)
        case (Toggle, Off) => m.updated(p, On)
      }
  }
})

I have couple questions regarding this process:

  1. My second version doesn't seem as clean and straightforward as the first version to me, I'm not sure if this is because I'm not that familiar with functional programming or I just wrote bad functional code.
  2. Is there someway to simplify the syntax on second piece? Especially the (m, item) => ??? function in the foldLeft part? Something like (m, (point, operation)) => ??? gives me syntax error
  3. The second piece of code takes significantly longer to run, which surprise me a bit as these two code essentially is doing the same thing, As I don't have too much Java background, Any idea what might be causing the performance issue?

Many thanks!

Improve this question

1 Answer 1

Reset to default
3

From a Functional Programming perspective, your code suffers from the fact that...

  1. The lightStatus Map "maintains state" and thus requires mutation.
  2. A large "area" of status changes == a large number of data updates.

If you can accept each light status as a Boolean value, here's a design that requires no mutation and has fast status updates even over very large areas.

case class Point(x: Int, y:Int)

class LightGrid private (status: Point => Boolean) {
  def apply(p: Point): Boolean = status(p)

  private def isWithin(p:Point, ll:Point, ur:Point) =
    ll.x <= p.x && ll.y <= p.y && p.x <= ur.x && p.y <= ur.y

  //each light op returns a new LightGrid
  def turnOn(lowerLeft: Point, upperRight: Point): LightGrid =
    new LightGrid(point =>
      isWithin(point, lowerLeft, upperRight) || status(point))

  def turnOff(lowerLeft: Point, upperRight: Point): LightGrid =
    new LightGrid(point =>
      !isWithin(point, lowerLeft, upperRight) && status(point))

  def toggle(lowerLeft: Point, upperRight: Point): LightGrid =
    new LightGrid(point =>
      isWithin(point, lowerLeft, upperRight) ^ status(point))
}
object LightGrid {  //the public constructor
  def apply(): LightGrid = new LightGrid(_ => false)
}

usage:

val ON  = true
val OFF = false
val lg = LightGrid().turnOn(Point(2,2), Point(11,11)) //easy numbers
                    .turnOff(Point(8,8), Point(10,10))
                    .toggle(Point(1,1), Point(9,9))
lg(Point(1,1))    //ON
lg(Point(7,7))    //OFF
lg(Point(8,8))    //ON
lg(Point(9,9))    //ON
lg(Point(10,10))  //OFF
lg(Point(11,11))  //ON
lg(Point(12,12))  //OFF
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

So what you're saying is that... in this case it might better to go for mutable map instead of strictly following functional principles? And as for your questions, unfortunately in the follow up I would need to maintain the brightness of each light so technically I cannot do a simple true / false
Not all usecases are great fit for functional programming. One of these is when you are supposed to maintain signnificantly large and dynamic state data. If you follow FP, you will have to always recreate the new state which might lead to significatly more garbage collection (specially in case of nested state models) compared to the mutable solution.
@sarveshseri -- Even if the state is big and complex, if you're preserving most of it, the new state will share most of its structure with the old state. I don't think GC will be a showstopper. In the non-FP approach, if you're reaching into large data structures to tweak them, you'll have a difficult time proving to yourself that all and only pieces of code that can reach the tweaked part are supposed to see the tweaked version.
@airfoyle GC impact depends on the change frequency and strcuture of your data.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.