Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I've been cooking with gas since I got Daniel C Sobral's help on my last question. I am now re-reading Odersky's "Programming in Scala, 2nd Edition" (finished my first reading about this time last year).

I am eager to understand how to alter my mental modeling of problems to more fully embrace the functional programming style. However, I have spent hours looking at the code below attempting to figure out how to eliminate the var references. I am sure my imperative past is overshadowing and blinding me to functional possibilities.

I think I have retained overall "referential transparency" at each method; i.e. none of the var-ness escapes the local scope of the method (or function) within which it is defined. However, I would like to understand how I might achieve a higher level of functional programming purity, even if it is slightly unreasonable, within each method. I am more looking for ways I need to change my problem solving approaches to be more myopically functional in nature.

Specifically, how might I approach eliminate each instance of var.

Thank you for any guidance.

case class Bitmap2d(name: String, rowsByColumns: List[List[Boolean]], faceUp: Boolean) {
  //require(rowsByColumns != null) //Assumed that if null was allowed as parameter, an Option would be used
  require(validateRectangular, "all rows must have same length")

  def validateRectangular: Boolean = {
    rowsByColumns.forall(_.size == rowsByColumns.head.size)
  }
}

class Piece(name: String, charRep: Char, rowsByColumnsAndUp: List[List[Boolean]]) {
  val translations = createTranslations()

  def printTranslations() = {
    println("Name: " +  name + " Char: " + charRep)
    for (bitmap2d <- translations) {
      println("  Orientation: " + bitmap2d.name)
      for (row <- bitmap2d.rowsByColumns)
      {
        for (pixel <- row)
        {
          val value = if (pixel) "1" else "0"
          print(value);
        }
        println()
      }
    }
  }
  private def createTranslations() = {
    //generate all 7 translations
    val bitmap2dRaws =
      for (i <- 0 to 7)
        yield translateBasedOnBitsForXYR(rowsByColumnsAndUp, i)
    var bitmaps = Set[List[List[Boolean]]]()
    var result = List[Bitmap2d]()
    for (
      bitmap2dRaw <- bitmap2dRaws
      if (!bitmaps.contains(bitmap2dRaw._2))
    )
    {
      bitmaps += bitmap2dRaw._2;
      result = Bitmap2d(bitmap2dRaw._1, bitmap2dRaw._2, bitmap2dRaw._3) :: result
    }
    result.reverse
  }
  private def translationSideUp(bits: Int) = {
    val flipX = ((bits & 1) == 1)
    val flipY = ((bits & 2) == 2)
    ((flipX || flipY) && (!(flipX && flipY)))
  }
  private def translationDescription(bits: Int) = {
    var result = List[String]()
    if ((bits & 1) == 1) {
      result = "FlipX" :: result
    }
    if ((bits & 2) == 2) {
      result = "FlipY" :: result
    }
    if ((bits & 4) == 4) {
      result = "Rotate" :: result
    }
    result.reverse
  }
  private def translateBasedOnBitsForXYR(rowsByColumns: List[List[Boolean]], bits: Int) = {
    require (((bits >= 0) && (bits < 8)), "bits must contain a value between 0 (inclusive) and 8 (exclusive)")
    var result = rowsByColumns;
    if ((bits & 1) == 1) {
      result = translateAroundXAxis(result)
    }
    if ((bits & 2) == 2) {
      result = translateAroundYAxis(result)
    }
    if ((bits & 4) == 4) {
      result = translateRotate90DegreesRight(result)
    }
    (translationDescription(bits).mkString("+") , result, translationSideUp(bits))
  }
  private def translateAroundXAxis(rowsByColumns: List[List[Boolean]]) = {
    if (rowsByColumns.size > 1) {
      rowsByColumns.reverse
    }
    else {
      rowsByColumns
    }
  }
  private def translateAroundYAxis(rowsByColumns: List[List[Boolean]]) = {
    if (rowsByColumns.head.size > 1) {
      for (row <- rowsByColumns)
        yield row.reverse
    }
    else {
      rowsByColumns
    }
  }
  private def translateRotate90DegreesRight(rowsByColumns: List[List[Boolean]]) = {
    val width = rowsByColumns.head.size
    val height = rowsByColumns.size
    val linearized = //need non-recursive random access
      (
        for {
          row <- rowsByColumns
          pixel <- row
        } yield pixel
      ).toArray
    var result = List[List[Boolean]]()
    for (i <- 0 to (width - 1)) {
      var tempRow = List[Boolean]()
      for (j <- 0 to (height - 1)) {
        tempRow = linearized((width * (j + 1)) - 1 - i) :: tempRow
      }
      result = tempRow :: result
    }
    result
  }
}

UPDATE:

Per Daniel C Sobral's excellent guidance, I have working through his answer. And and now also Landei's. I've reworked the Piece class rather than just copying/pasting their answers. Below is the modified class. It's quite a bit smaller. And I've learned quite a bit about how to reframe my imperative loop based thinking to using recursion (and have only just begun to understand foldLeft).

Thank you again, Daniel and Landei for your feedback and guidance. If you see anything else that I can improve or about which I could think more functionally, please let me know and I will do the work to apply it.

import scala.annotation.tailrec
import scala.collection.immutable.TreeMap

object Piece {
  val ROTATION_DESCRIPTIONS = TreeMap(1 -> "FlipX", 2 -> "FlipY", 4 -> "Rotate")
}

class Piece(name: String, charRep: Char, rowsByColumnsAndUp: List[List[Boolean]]) {
  val translations = createTranslations()

  def printTranslations() = {
    println("Name: " +  name + " Char: " + charRep)
    for (bitmap2d <- translations) {
      println("  Orientation: " + bitmap2d.name + "-" + (if (bitmap2d.faceUp) "Up" else "Down"))
      for (row <- bitmap2d.rowsByColumns) {
        for (pixel <- row) {
          print(if (pixel) "1" else "0");
        }
        println()
      }
    }
  }
  private def createTranslations() = {
    @tailrec def recursive(bits: Int,
                           bitmapOnlys: Set[List[List[Boolean]]],
                           bitmap2ds: List[Bitmap2d]): List[Bitmap2d] = {
      if (bits > 7) {
        bitmap2ds
      }
      else {
        val translation = translateBasedOnBitsForXYR(bits);
        val add = (!bitmapOnlys.contains(translation))
        recursive(bits + 1,
                  if (add) bitmapOnlys + translation else bitmapOnlys,
                  if (add) Bitmap2d(translationDescription(bits).mkString("+"),
                      translation, translationSideUp(bits)) :: bitmap2ds else bitmap2ds
                 )
      }
    }
    recursive(0, Set[List[List[Boolean]]](), List[Bitmap2d]()).reverse
  }
  private def translationSideUp(bits: Int) = (!((bits & 1) == 1) ^ ((bits & 2) == 2))
  private def translationDescription(bits: Int) =
      Piece.ROTATION_DESCRIPTIONS.filterKeys(x => (bits & x) == x).values.toList
  private def translateBasedOnBitsForXYR(bits: Int) = {
    require (((bits >= 0) && (bits < 8)),
             "bits must contain a value between 0 (inclusive) and 8 (exclusive)")
    val tx = if ((bits & 1) == 1) translateAroundXAxis(rowsByColumnsAndUp)
             else rowsByColumnsAndUp
    val ty = if ((bits & 2) == 2) translateAroundYAxis(tx) else tx
    if ((bits & 4) == 4) translateRotate90DegreesRight(ty) else ty
  }
  private def translateAroundXAxis(rowsByColumns: List[List[Boolean]]) = {
    if (rowsByColumns.size > 1) {
      rowsByColumns.reverse
    }
    else {
      rowsByColumns
    }
  }
  private def translateAroundYAxis(rowsByColumns: List[List[Boolean]]) = {
    if (rowsByColumns.head.size > 1) {
      for (row <- rowsByColumns)
        yield row.reverse
    }
    else {
      rowsByColumns
    }
  }
  private def translateRotate90DegreesRight(rowsByColumns: List[List[Boolean]]) = {
    translateAroundYAxis(rowsByColumns.transpose)
  }
}
share|improve this question
    
This article comes out right after I spent the weekend learning exactly this. I am feeling quite appreciative: nurkiewicz.blogspot.com/2012/04/… –  chaotic3quilibrium Apr 9 '12 at 15:07
1  
Why do you define value, only used once? Wouldn't print(if (pixel) "1" else "0") be at least just as readable? (Also, I'd suggest adding some line breaks for the extra-wide lines.) –  Christopher Creutzig Apr 10 '12 at 17:44
    
@Christopher Good point. And the braces were incorrect, too. My Java code format bleeding through. I've corrected both. Tyvm for your feedback. –  chaotic3quilibrium Apr 11 '12 at 2:32
add comment

2 Answers

up vote 2 down vote accepted

One good technique at eliminating vars is recursion -- it can certainly be used in this example. Alternatively, you can identify a common pattern, such as fold, traversal, etc. For example:

var bitmaps = Set[List[List[Boolean]]]()
var result = List[Bitmap2d]()
for (
  bitmap2dRaw <- bitmap2dRaws
  if (!bitmaps.contains(bitmap2dRaw._2))
)
{
  bitmaps += bitmap2dRaw._2;
  result = Bitmap2d(bitmap2dRaw._1, bitmap2dRaw._2, bitmap2dRaw._3) :: result
}
result.reverse

Recursion:

def getResult(bitmap2dRaws: ???, bitmap: Set[List[List[Boolean]]], result: List[Bitmap2d]): List[Bitmap2d] = bitmap2dRaws match {
  case Seq(bitmap2dRaw, rest: _*) if (!bitmaps.contains(bitmap2dRaw._2) =>
    getResult(rest, bitmaps + bitmap2dRaw._2, Bitmap2d(bitmap2dRaw._1, bitmap2dRaw._2, bitmap2dRaw._3) :: result)
  case Seq(bitmap2dRaw, rest: _*) =>
    getResult(rest, bitmaps, result)
  case _ => result.reverse
}
getResult(bitmap2dRaws, Set[List[List[Boolean]], Nil)

Fold:

bitmap2dRaws.foldLeft((Set[List[List[Boolean]]], List[Bitmap2d])) {
  case ((bitmaps, result), bitmap2dRaw) if (!bitmaps.contains(bitmap2dRaw._2) =>
    (bitmaps + bitmap2dRaw._2, Bitmap2d(bitmap2dRaw._1, bitmap2dRaw._2, bitmap2dRaw._3) :: result)
  case ((bitmaps, result), _) => (bitmaps, result)
}._2.reverse

You can use the same techniques for the var inside translateRotate90DegreesRight as well.

In other places you might use Option:

private def translationDescription(bits: Int) = {
  var result = List[String]()
  if ((bits & 1) == 1) {
    result = "FlipX" :: result
  }
  if ((bits & 2) == 2) {
    result = "FlipY" :: result
  }
  if ((bits & 4) == 4) {
    result = "Rotate" :: result
  }
  result.reverse
}

becomes:

private def translationDescription(bits: Int) = {
  val flipX = if ((bits & 1) == 1) Some("FlipX") else None
  val flipY = if ((bits & 2) == 2) Some("FlipY") else None
  val rotate = if ((bits & 4) == 4) Some("Rotate") else None
  List(flipX, flipY, rotate).flatten // if this doesn't work, try flatMap(x => x)
}

Finally (unless I missed something), the var inside translateBasedOnBitsForXYR can be avoided simply by using multiple val, and if statements like this:

val xTranslation = if ((bits & 1) == 1) translateAroundXAxis(rowsByColumns) else rowsByColumns

and so on.

share|improve this answer
    
Awesome! And somewhat daunting. :) I read and reread your first answser, both the recursion and foldLeft solutions, and think I finally understood how they work. And then without copying your code, I decided to try and implement the recursive version using only your code as a reference. I wanted to be sure I pushed through all the new thinking I need to do. I will update my post with the updated code (separate from the original problem code). I have only done your first answer thus far. I will continue working through the rest of the class using your guidance and re-post in the update. –  chaotic3quilibrium Apr 8 '12 at 21:06
    
Okay. I have worked through all of your guidance. Thank you for doing both recursive and foldLeft examples. Between my way over imperative original version (which I deeply understand) and your examples, I was able to think through to both the recursion and foldLeft. I chose recursion this time. However, I will come back to using List and foldLeft to get used to using its recursive nature. Please let me know if you see anything else that can be improved on the new updated Piece object and class. –  chaotic3quilibrium Apr 8 '12 at 22:54
add comment

Just a few remarks:

This won't work - we have integer division like in Java, e.g. 7 / 5 == 1:

rowsByColumns.forall(_.size / rowsByColumns.head.size == 1)

Suggestion:

def validateRectangular = rowsByColumns.forall(_.size == rowsByColumns.head.size)

Here you're looking for an exclusive or (a.k.a. "xor"):

private def translationSideUp(bits: Int) = {
  val flipX = ((bits & 1) == 1)
  val flipY = ((bits & 2) == 2)
  ((flipX || flipY) && (!(flipX && flipY)))
}

...which would look like

private def translationSideUp(bits: Int) = ((bits & 1) == 1) ^ ((bits & 2) == 2)

Here I would use a Map instead:

private def translationDescription(bits: Int) = {
  var result = List[String]()
  if ((bits & 1) == 1) {
    result = "FlipX" :: result
  }
  if ((bits & 2) == 2) {
    result = "FlipY" :: result
  }
  if ((bits & 4) == 4) {
    result = "Rotate" :: result
  }
  result.reverse
}

For instance:

private def translationDescription(bits: Int) = 
  TreeMap(1->"FlipX", 2->"FlipY", 4->"Rotate").
    filterKeys(x => (bits & x) == x).values.toList    

Finally you can get a rotation by using List.transpose and a vertical or horizontal flip. E.g.

List(List(1,2,3),List(4,5,6)).transpose
// List[List[Int]] = List(List(1, 4), List(2, 5), List(3, 6))
share|improve this answer
    
Oops. Good catch on Bitmap2d.validateRectangular(). It was still incorrect in Eclipse even though I had updated it when Daniel pointed it out on a previous thread. I have updated in the "original" code copy as it was not intended to be reworked in this thread. –  chaotic3quilibrium Apr 8 '12 at 21:18
    
XOR was exactly what I was looking for. And I even saw the reference in Odersky's book. I just didn't connect the dots. Thank you for the specific example. Next time I do a code update in the original post, I will add that. –  chaotic3quilibrium Apr 8 '12 at 21:27
    
Regarding your specific example of using a Map, ordering of the elements is important. I noticed that you used a TreeMap directly defined in the method. Does that preserve the ordering I had in my original method? I wonder how I could look that up myself (i.e. the ScalaDoc for immutable.TreeMap)? And then you create the TreeMap in the instance method. In Java I would have created a private static final Map TRANSLATION_DESCRIPTIONS and then referred to it from this method to avoid instantiating it every time the method is called. Does the Scala compiler automatically figure this out? –  chaotic3quilibrium Apr 8 '12 at 21:32
    
I went here scala-lang.org/api/current/… to try and figure out what TreeMap does. There is little resemblance to JavaDoc (like normal expansive English explanations with some prototypical examples), so I am still not able to tell if TreeMap preserves ordering some way (although the RedBlackTree it extends seems to imply it...but jumping there in the ScalaDoc didn't help me). –  chaotic3quilibrium Apr 8 '12 at 21:36
1  
@chaotic3quilibrium TreeMap is ordered by key. One might use ListMap or LinkedHashMap instead, which will preserve insertion order -- that might be more adequate to your needs. Just make sure it is working as you expect: some of these more unusual collections are not well tested, and have bugs you'd never expect to see. –  Daniel C. Sobral Apr 8 '12 at 23:23
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.