# Attempting to eliminate var (and imperative style) from my Piece class

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 == 1)
}
}

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

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

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.

-
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

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

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