CODEWITHSUNDEEP
functional-programming
devintern
devintern

Reputation: 31

how do functional languages handle manipulating array arguments if arguments are non mutable?

I am reading about functional languages and I can't understand this particular thing. Suppose a function takes an array of numbers and has to square each number. What if we need to remove or insert some elements? Do we have to return a copy of the mutated array for every operation? If so how are arrays of hundreds of millions of objects manipulated reasonably?

Upvotes: 3

Views: 863

Answers (1)

Mark Saving
Mark Saving

Reputation: 1787

There are several ways that functional languages handle array arguments.

  1. Don't actually use arrays.

Instead of using arrays, one should almost always use some other data structure. Lists, binary search trees, finger trees, functional queues, and other data structures are commonly employed in functional code instead of arrays. It often takes some thought to pick the best data structure.

  1. Have a "special escape hatch" for using mutation.

In Haskell, there is a magical thing known as the ST monad. This allows you to write code in Haskell which manipulates mutable arrays in an imperative style while still guaranteeing that the mutation can't "leak out" the escape hatch. For example, if I have a function f :: Int -> Int and I call f 3 twice, I am guaranteed to get the same results each time even if the function internally uses a mutable array. This is not the case in a language like Java, since calling f(3) might read from and write to mutable state, but in Haskell, you can use mutation fairly freely without compromising purity using ST.

  1. Use linear types.

This is a relatively recent addition to Haskell. Consider a function modify :: Int -> a -> Array a -> Array a, where modify idx new_val original_array should return a new array which is a copy of original_array, except that position idx has been overwritten with value new_val. If we never read from the array original_array after we call the modify function on it, then it's ok for the compiler to secretly modify original_array rather than creating a new array without breaking the abstraction of the code. Linear types basically enforce this restriction within the language. It's rather sophisticated and takes some getting used to, but it allows you to use an underlying mutable data structure safely with functional abstractions. It's more limited than ST but doesn't involve any "imperative thinking".

  1. Use immutable arrays.

You might just bite the bullet and use arrays that must be copied on modification. This is very rarely optimal, but the language may offer some abstractions that make this less bearable and more asymptotically efficient in certain circumstances.

Upvotes: 2

Related Questions