Can I mutate a variable in place in a purely functional way?

Question

I know I can use state passing and state monads for purely functional mutation, but afaik that's not in-place and I want the performance benefits of doing it in-place.

An example would be great, e.g. adding 1 to a number, preferably in Idris but Scala will also be good

p.s. is there a tag for mutation? can't see one

Well in **Scala** you have `var` that you can mutate at any moment; but, that won't be purely functional. However, if the variable is internal to some method and its mutation is invisible to external users we still refer to that method as being referential transparent and thus mutation is just an internal _(and probably pragmatic)_ implementation details. — Luis Miguel Mejía Suárez, May 14 '21 at 14:40
@LuisMiguelMejíaSuárez yeah I'm familiar with `var` and local mutation, but I'm actually hoping to write this in Idris, where there is no `var`, hence purely-functional. I'm asking in Scala too cos if it's possible in Idris it's probably possible in Scala — joel, May 14 '21 at 14:54
Mutation = break RT = no purely functional, period. However, we do not do purely functional programming for showing off but because it helps u maintain our programs, and thus pragmatic functional programmers understand that sometimes contained mutability is not only ok but better _(for performance or readability)_, however that doesn't mean that it is purely functional, that doesn't make sense. So your question has to be reworded as _"how to do mutation in **Idris**"_ and remove **scala** for the equation; now maybe you want to look at `Ref` which is how you would share some mutable state. — Luis Miguel Mejía Suárez, May 14 '21 at 15:06
@LuisMiguelMejíaSuárez I'm not sure we're on the same page. I'm thinking along the lines of how `IO` returns an action to execute, and when you execute it, you get a resulting value which you can then access via `map` etc. Similarly, whether it's possible to have a type that signifies "this will produce a new value from the current one when executed, which we can reason about now via `map` and co.". I expect it would be similar to the state monad, but use only one memory address — joel, May 14 '21 at 15:12
@LuisMiguelMejíaSuárez `Ref` looks promising. You mean from cats? — joel, May 14 '21 at 15:22
Well your action to execute could be the modification of a variable `val Inc = IO { i += 1 }` you may also take a look to `Ref` which instead of allowing you to mutate something _per se_, but rather allows you to share some _(mutable)_ state across multiple _(concurrent)_ operations, while it doesn't really gives you the access to mutate a value it gives you the possibility to create a new state given the previous one and internally it may _(in **cats-effect** it is)_ mutating the same memory address. — Luis Miguel Mejía Suárez, May 14 '21 at 15:23
It's also not impossible for a compiler/runtime to ultimately interpret a mutation described in a purely functional way as an in-place mutation, even if the code is not written in such a way. Have you written the purely FP (e.g. state monad) code and found it wanting in performance, or is this merely a case of "because the naive implementation looks slow, I think it's slow"? — Levi Ramsey, May 14 '21 at 16:06
@LeviRamsey I've not written the code yet, but it's actually a wrapper for C++ code that does do in-place mutation — joel, May 14 '21 at 16:13
It is crucial that the API can guarantee in place mutation because the object will be a potentially very large array, up to GB of data, and performance is pretty crucial — joel, May 14 '21 at 16:36
@joel in that case you only need an `IO` that describes the mutation in place like my example. — Luis Miguel Mejía Suárez, May 14 '21 at 17:17
If `def foo() = x+1`, and `x` is mutable and visible outside of `foo`, then `foo` is not referentially transparent. Ergo, "mutation in purely functional way" is nonsensical. "Can I fry a piece of ice without it being melted"? — Dima, May 14 '21 at 20:13
Over the past few years, I've repeatedly pointed to [this chapter in The Red Book](https://livebook.manning.com/book/functional-programming-in-scala/chapter-14/13), which contains a section "Purely functional mutable state". There was also a `ST`-monad implementation flying around somewhere. I'm aware that this exists, but I've never used it for anything. — Andrey Tyukin, May 14 '21 at 21:42
@AndreyTyukin `ST` doesn't make sense in **Scala**, `ST` is basically just a `var` — Luis Miguel Mejía Suárez, May 14 '21 at 22:04
@LuisMiguelMejíaSuárez It's not about the `var`. It's about having a proof that references to that `var` don't escape. — Andrey Tyukin, May 14 '21 at 22:30
@AndreyTyukin well as with all pure FP in **Scala** you need disciple. Nothing prevents you to doing `def thisIsNotFP(): IO[Unit] = { executeSideEffects(); IO.unit }` — Luis Miguel Mejía Suárez, May 14 '21 at 22:41
@LuisMiguelMejíaSuárez Having a proof and having it enforced by the compiler are two orthogonal concerns. Of course one can `println("whatever, wherever")`, that's not the point. — Andrey Tyukin, May 14 '21 at 22:52

Matthias Berndt · Accepted Answer · 2021-05-17T17:15:07.783

No, this is not possible in Scala.

It is however possible to achieve the performance benefits of in-place mutation in a purely functional language. For instance, let's take a function that updates an array in a purely functional way:

def update(arr: Array[Int], idx: Int, value: Int): Array[Int] =
  arr.take(idx) ++ Array(value) ++ arr.drop(idx + 1)

We need to copy the array here in order to maintain purity. The reason is that if we mutated it in place, we'd be able to observe that after calling the function:

def update(arr: Array[Int], idx: Int, value: Int): Array[Int] = {
  arr(idx) = value
  arr
}

The following code will work fine with the first implementation but break with the second:

val arr = Array(1, 2, 3)
assert(arr(1) == 2)
val arr2 = update(arr, 1, 42)
assert(arr2(1) == 42) // so far, so good…
assert(arr(1) == 2) // oh noes!

The solution in a purely functional language is to simply forbid the last assert. If you can't observe the fact that the original array was mutated, then there's nothing wrong with updating the array in place! The means to achieve this is called linear types. Linear values are values that you can use exactly once. Once you've passed a linear value to a function, the compiler will not allow you to use it again, which fixes the problem.

There are two languages I know of that have this feature: ATS and Haskell. If you want more details, I'd recommend this talk by Simon Peyton-Jones where he explains the implementation in Haskell:

https://youtu.be/t0mhvd3-60Y

Support for linear types has since been merged into GHC: https://www.tweag.io/blog/2020-06-19-linear-types-merged/

this reminds me very much of how ownership in rust [can be used to provide a purely-functional API with mutation](https://stackoverflow.com/q/59696588/5986907). Perhaps that's an example of linear types — joel, May 14 '21 at 23:23
and Idris 2 seems to support it [via quantitative types](https://idris2.readthedocs.io/en/latest/tutorial/multiplicities.html#resource-protocols). Whether Idris gives the memory guarantees I'm yet to find out — joel, May 14 '21 at 23:45
Wouldn't you want affine types for this instead? If you don't use `arr2` for anything, it should still be OK. — Cactus, May 16 '21 at 11:16
@Cactus I've not come across affine types. Where might I find out more? They're not in the book (at least the index), or either docs website — joel, May 17 '21 at 15:25
@Cactus ah, found what affine means, though I'm not sure I understand the practical difference. Why would I call the function if I'm not going to use its return value? — joel, May 17 '21 at 15:45

Can I mutate a variable in place in a purely functional way?

1 Answers1