Immutable state in FP

Question

This question came to mind when following some tutorials on Scala, but i think is interesting in general when it comes to functional programming.

I am unsure about the importance of immutability in FP. I can think of 2 different cases:

1) A class method does not return the actual fields but a copy of them. For example if we have a class Dog which we need to keep immutable, then its function:

getToys() { return new ArrayList(this.toys); }

instead of:

getToys() { return this.toys; }

This case makes perfect sense to me, in the 2nd case client code could actually corrupt the object. My skepticism lies in the 2nd case:

2) In Scala and most other FP languages we prefer a recursive call:

sum(x: List[Int], acc: Int) { 
  if(x.isEmpty) return acc;
  sum(x.tail, acc + x.head); 
}

against a traditional for loop incrementing an accumulator. The reasoning is that this accumulator is a mutable variable.

That variable is never exposed outside the function so why care to make it immutable?

EDIT:

It seems like the most important best practice is referential transparency and not strict immutability, meaning roughly that we don't care about mutable state as long as it is not discoverable by client code. However people still claim that even when mutable state affects local variables (as in my 1st example) the code is more readable or easier to reason about.

Personally, i would argue that a loop is more readable than a recursion.

So the real question is: Why is code using immutable variables considered easier to read / reason about?

Regarding 1) the point is that you don't need to return copies if your data structures are immutable in the first place. — sepp2k, Jun 25 '16 at 11:44
Possible duplicate of [A grasp of immutable datastructures](http://stackoverflow.com/questions/8346119/a-grasp-of-immutable-datastructures) — Łukasz, Jun 25 '16 at 11:46
Index variables are usually not exposed, you are right. As long as we talk about trivial Indexes used only for iterations we are save. It's still not just a best practice because this is the only way you can safely use global indexes and still be Thread save for example. — Julian, Jun 25 '16 at 11:51
Answering your last question: `def m() = { var x = 1; ... (20 lines of some code); x }`. How many lines you need to scan to know what is returned? (hint: 20+) What if it was `val x = 1`? — Victor Moroz, Jun 25 '16 at 18:51

Martijn · Accepted Answer · 2016-06-26T14:51:10.330

In Scala and most other FP languages we prefer a recursive call ... against a traditional for loop incrementing an accumulator. The reasoning is that this accumulator is a mutable variable.

You assume recursion is preferred over a traditional loop incrementing an accumulator. I agree functional programmers favour recursion, but not for the reason you think. In many cases, recursion is just a natural and concise way to express a problem. Note that since tail call optimisation removes the overhead of allocating a new stack frame, performance is not argument against recursion.

You compared recursion to a for loop incrementing an accumulator. Most programmers will prefer looping over a collection without an index (e.g. for (i <- 0 to 10) { .. } in Scala or for (T x : collection) { .. } in Java. The for construct abstracts over iterating over a collection, making it possible to a) more clearly communicate your intent and b) reduce the risk of errors (such as one-off errors). Abstracting even further, we could express your example of summing a list of integers using the higher-order fold:

scala> (1 to 10).foldLeft(0)(_+_)
res0: Int = 55

Now back to your original question: why are immutable variables easier to read and reason about? This may come as a surprise, but programmers are also just humans. Humans are bad a reasoning about systems with many moving parts. Immutability reduces the number of moving parts, making it easier to reason about programs.

score 1 · Answer 2 · answered Jun 26 '16 at 04:25

You're right that immutability isn't the greatest concern if the reference doesn't escape the function, but there are other considerations. Imperative loops have extraordinarily generic and imprecise semantics, and therefore most people simply find them too sloppy once they learn the alternatives.

For instance, imperative loops have no return types. The input types of their arguments are not checked. Many types of imperative loops force the programmer to deal unnecessarily with indices that have nothing to do with the problem statement. There are only a handful of varieties of imperative loops that are meant to cover every conceivable situation, so they are overly generic. You cannot create your own new kind of of imperative loop that fits your specific situation better. They almost always must be built into the language itself.

For some strange reason, everyone seems to make it a false choice between recursion and imperative loops, but recursion is really the worst tool in a functional programmer's belt. We avoid it unless absolutely necessary, or unless an algorithm is naturally expressed recursively. There are dozens of higher-order functions that can be used to more precisely express most day-to-day code much more clearly than recursion, while retaining all the benefits, like Martjin's foldLeft example.

The type checking benefits alone are worth it to use foldLeft instead of a for loop. Empty lists are handled effortlessly. There is no weird accumulator that must be initialized with a scope outside the loop. You don't have to come up with weird names for all those temporary variables that you don't care about anyway. It's just plain cleaner.

You may say this is a special simple case, but with care, avoiding imperative loops can give you this sort of experience in the vast majority of situations, and the ones where the recursion ends up complex, the imperative solution typically would have been just as complex. When you make a real comparison of all the alternatives, imperative loops only come out favorably because people are familiar with them.

Immutable state in FP

2 Answers2