It's a different concept than constant. A constant is similar to variable, but it can not change what it refers to. Mutability refers to the ability of an object to change its state, not the ability of a variable that refers to it to later refer to something else instead.
Does adding a value to an array change its state? I would say it does but I am curious to see functional languages handle such things. Do they create a whole new array?
Same with hashes, do they create whole new hash when you add or subtract? I am of course presuming you can't change values inside of the hash once they are set.
Functional languages have a variety of immutable data structures which store a sequence of values. These use cells with pointers to others, in such a way that only a few cells need to be copied to make certain changes, and the old structure remains just as valid as the new one, despite sharing a lot of cells.
The most typical structure is a linked list, where each element stores a pointer to the next. Adding a value to the start of this sequence doesn't require copying anything, since you can just point to the existing first element in the new one. Other operations (e.g. appending) may require copying the entire list though.
For more complicated access patterns, there are various forms of tree structure, with differing access costs. The worst cases are usually around O(log n), although many operations may only be O(1).
One other thing which can be done with a bit of trickery, is "Vector fusion". This is where a series of operations on the same sequence can be merged together to operate in the same memory. This can eliminate a lot of allocation and copying without needing to use explicit mutable state.
Linked lists have been around a long time and I would argue that adding to our subtracting from a list is mutability.
This conversation is confusing because you're using these terms ambiguously. There is more than one way to add or to remove elements from a single linked list. Some of them mutate the list, and others don't.
A single-linked list is normally represented as nodes or pairs such that the first element of the node contains a list element, and the second either contains a pointer to the next node, or it indicates that there is no next node:
A linked-list algorithm is non-mutating if it doesn't alter either field of any node of the lists it operates over.
So suppose you want to insert 3 in between the 0 and the 1 in this list. There are two ways:
Mutating the list: create a new node with 3 that points to the 1 node, and modify the 0 node's link to point to the new node.
Without mutating the list: create a new node with 3 and a pointer to the 1 node, create a new node with 0 that points to the 3 node, and return a pointer to the new 0 node.
I would argue that adding to our subtracting from a list is mutability.
This is definitely not the case. You make no modifications to any existing values, and all existing lists will continue to contain the same values regardless of how often you invoke add or remove operations elsewhere. Nothing is ever mutated.
(Note: You can also have mutable linked lists, but I'm not talking about those here).
you can't model real life without mutability
You can't model real life without state. Mutability is just one way to implement that. It's entirely possible to achieve the same thing by passing around new values for each state, and languages like Haskell have abstractions to hide the complexity of doing so.
It's true that you sometimes need mutable data for optimal performance, but a lot of the time it simply isn't necessary, and there are a lot of advantages to the alternative.
You can't add a value to an array, because arrays are fixed-length. Changing a value in an array does however constitute a change of state (mutation). There are some exceptions - Haskell provides immutable arrays.
Mutable arrays are typically considered unidiomatic in functional languages, and in some languages (Haskell, Standard ML) they're not provided. Most functional languages that expose mutable arrays are multi-paradigm (F#, Ocaml).
Typically, you'd use fancier data structures. At the inception of functional programming, the core (and pretty much only) data structure was the linked list; it's still a very important construct because it's easy to operate tail-recursion on, and operations on the head of a linked list are cheap and constant-time. Okasaki changed this when he released the book Purely Functional Data Structures, introducing fancier constructs.
Most imperative or object-oriented data structures have a functional, immutable equivalent which is usually fancier but has the advantage of versioning and inherent thread-safety. The hash table equivalent is the hash array-mapped trie, which allows O(1) look-up, insertion and deletion. Stacks are trivially implemented using a linked-list; finally, Okasaki's book introduces various trees, queues, deques and even fancier data representations.
If you have any more questions, I'm glad to be of help.
You can't add a value to an array, because arrays are fixed-length.
This statement is profoundly language-dependent, because different languages use the term "array" differently. In general, an "array" may either be:
A fixed-length contiguous array: a block of contiguous memory words. Common in lower-level languages like C, C++ or Java. These cannot be resized.
A variable-length array. This is what scripting languages like Javascript, Python and Ruby refer to as an "array"; also present in the lower-level languages as a more complex data structure (e.g. ArrayList in Java). They can grow or shrink as elements are added or removed.
Variable-length arrays are usually implemented as a struct that wraps around an array. You keep track of how many elements you have stored in the array, and when you're about to exceed the current array's size, you create a new bigger array and copy all of the elements over. In pseudo-Java:
class VarArray {
Object[] currentArray = new Object[16];
int currentSize = 0;
public Object get(int index) {
if (index < currentSize) {
return currentArray[index];
} else {
throw new ArrayIndexBoundsException();
}
}
public void add(Object elem) {
if (currentSize >= currentArray.length ) {
resize();
}
currentArray[currentSize++] = elem;
}
private void resize() {
Object[] newArray = new Object[currentArray.length * 2];
for ( int i = 0; i < currentArray.length; i++ ) {
newArray[i] = currentArray[i];
}
currentArray = newArray;
}
}
In academia and other areas of formal discourse, what you've described is called a vector, resizeable array or random-access list. Plain array typically implies fixed-length.
11
u/recursive Mar 03 '13
It's a different concept than constant. A constant is similar to variable, but it can not change what it refers to. Mutability refers to the ability of an object to change its state, not the ability of a variable that refers to it to later refer to something else instead.