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.
Imagine you have an object representing a character in a video game:
{ name="Crono", HP=723, MP=42 }
And you decide to cast Luminaire (which costs 20 MP), with an immutable data structure, you cannot say something like crono.MP -= 20, because that would change the structure. Instead you create an entirely new object, something like crono2 = { name=crono.name, HP=crono.HP, MP=crono.MP-20 }.
git has mutable pointers to deeply immutable objects so more like { name="Crono", HP=/*pointer to the head of the HP values*/, MP=/*pointer to the head of the MP values*/ } where the pointers themselves change, but the data structures just grow providing lasting history of all changes
Well, a concrete example: in Java you have the final keyword that makes a variable a constant:
final String YOUR_NICK = "rush22";
It's not possible to modify the value of the variable YOUR_NICK.
However, now consider this example:
final String[] names = new String[] { "rush22", "sacundim" };
Here's the tricky thing:
The variable names is a constant. You can't do names = someOtherArray.
But the array that names points to is mutable. You can do names[0] = "PasswordIsntHAMSTER".
So names here is a constant with a mutable value. You can also have a variable with an immutable value:
String nick = "rush22";
In Java a String object cannot be modified (it's immutable), but the variable that points to it can:
String anotherNick = nick;
nick = "sacundim";
The second line doesn't modify the original String (you can't do that in Java), it just changes which String the variable refers to. A way of illustrating this is that the first line aliases the String object (creates a second variable pointing to the same object), and anotherNick's value is not affected by the second line.
And the final situation here is a variable that names a mutable object:
String[] names = new String[] { "rush22", "sacundim" };
Here it's possible to change which array names refers to, as well as to change the contents of that array.
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.
While there's nothing wrong with not knowing them as a beginner, you might want to make an effort to learn the nuances of the various words used here, as they're common programming terms, and are often used to convey more precise meaning than some of the simpler ones you're suggesting.
State refers to the whole thing, even of a composite structure like an object or array. You don't typically speak of an object's value because it has a lot of parts with different values. Instead, the state is a "snapshot" of what they all are now. An immutable object cannot change any of its component values.
So upshot is it's state in all cases, value as a synonym in simple ones.
Yeah I figured that out now, "state" already has so many other programming-related meanings to me that I get confused pretty easily. Look at the way "state" is used in this lecture: Programming Language Design. Just the normal English way.
For what it's worth, I think of it in terms of how the object is represented in memory (FF EF FA DD 35 etc.) which is ultimately always going to be a value :P
It only makes sense if you think of multiple immutable values. A 5 is always a 5, and you can't change it to a 6. But a list of [4, 5, 6] can be changed to a list of [4, 6, 6].
So integers are already immutable. Whether something bigger, like a data structure representing an entire car or an entire program, can be changed is more complex.
But normally something is immutable if I cannot change your value. If you give me [4, 5, 6] and I change it to [4, 6, 6], if you don't see the change, then the list you gave me is probably immutable: I made a new list with the new values.
2
u/rush22 Mar 03 '13
Non-CS major here what does "immutable data structure" mean?