Cleanliness, Referential Transparency and the State Monad

Question

I am currently developing a numerical algorithm that as part of its operations requires multiple updates of the doubles vector. Due to the fact that the algorithm should be as efficient as possible both in space and in time, I do not want to encode the traditional type of FP code, which creates each version of each data structure under the hood after each operation. I also do not want to create mutable data structures and have them globally. Therefore, I decided to use a mutable data structure, but then decided to perform mutable operations in the State monad. Since this is my first hit when using State monad, I want to confirm whether I have or not

• saved link transparency
• maintained functional cleanliness

The update function translates the state of the data structure. Since the destructive update is localized inside this function, and the data structure descriptor cannot be received from the outside, I think this function is pure and referential transparency.

 def update(i : Int,d : Double) = State[ArraySeq[Double], Unit]{ case xs: ArraySeq[Double] => {xs(i) = d; (xs, ())} } 

The app function is a toy function that will consume a double sequence and change its state:

 def app : State[ArraySeq[Double], Unit] = for{ _ <- update(0, 3.142) // do a heap of stuff on ArraySeq }yield() 

Call:

 app(Vector(0.0, 1.0, 2.0, 3.0, 4.0).to[ArraySeq])._1.to[Vector] 

Result:

 res0: Vector[Double] = Vector(3.142, 1.0, 2.0, 3.0, 4.0) 

Answer 1

I think you could say that your update itself is pure, in the sense that it represents only some mutation, but as soon as you run it, all bets are disabled:

 scala> val xs = List(1.0, 2.0, 3.0).to[ArraySeq] xs: scala.collection.mutable.ArraySeq[Double] = ArraySeq(1.0, 2.0, 3.0) scala> update(0, 10).eval(xs) res0: scalaz.Id.Id[Unit] = () scala> xs res1: scala.collection.mutable.ArraySeq[Double] = ArraySeq(10.0, 2.0, 3.0) 

This is a bad scene, and it is the opposite of pure or referential transparency.

State doesn't actually buy anything in your example - the fact that you invoke the app in such a way that you have an ArraySeq that no one can mutate. You can also bite the bullet and work with the variable data structure in the usual way in the area that you control, i.e. Write the app as follows:

 def app(xs: Vector[Double]): Vector[Double] = { val arr = xs.to[ArraySeq] // Perform all your updates in the usual way arr.toVector } 

It is actually pure and referentially transparent, but it is also more honest than the State version. If I see a value of type State[Foo, Unit] , my assumption will be that this value is some operation that changes Foo to a new Foo without changing the original Foo . This is the entire state monad - it provides a good way to model operations with immutable data structures and compose them in a way that looks like a mutation. If you mix it with an actual mutation, you are likely to confuse hell with someone using your code.

If you really want real mutation and purity at the same time, you can watch Scalaz STArray . This is a very smart solution to this problem, and in languages ​​like Haskell, this is an approach that makes a lot of sense. My own opinion is that this is almost always the wrong decision in Scala. If you really need the performance of a mutable array, just use a local mutable array and make sure you don't miss it into the outside world. If you don’t need this kind of performance (and most of the time you don’t), use something like State .