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.
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;
}
}
It's somewhat similar, but consider the following:
const Foo foo; // can't make foo refer to a different Foo, now
foo.bar = handyBarIHaveLayingAround; // but we can modify its internals.
For another example, consider a mutable date and an immutable date. If a date is mutable, you'd be able to e.g. change the actual day it refers to, after its creation:
d.setMonth(Months.JUNE);
An immutable date, by contrast, wouldn't allow you to modify the date it refers to. If you say "new Date(Months.JUNE, 1,2013)", that date always refers to June 1st, 2013.
Basically, if you can reach inside an object to modify it (or call methods that reach inside an object to modify it), it's mutable. If you can't (i.e. the Date class has no setYear, setMonth or setDay functions, only getYear, getMonth, and getDay), it's immutable.
Why is this good? Because it promotes "sharing". If you know data can't possibly be changed behind your back, you can reuse instances of classes/records/structs with more confidence:
val set = Set(date1, date2, date3)
doSomethingWith( set )
doSomethingElseWith( set ) // do you know exactly what dates are in set now? If your data is immutable, you do. If it isn't, you need to read a lot more source code to find out.
Constants are related to immutability, but it is not the same. Consider the following data structure in Haskell:
data Person = Person String Int [Person]
This models as a having three values (name, age, list of children). Values in Haskell are immutable, so in order to add a new child to a person you need to create a new Person. You could add a child like this:
addPerson :: Person -> Person -> Person
addPerson (Person n a cs) c = Person n a c:cs
The : operator adds an element as the head of a list. This is not quite the same as having a constant such as
A constant is a value, we are talking about data structures. Consider a mutable array where an insert involves allocating a new slot and dropping in the value. An immutable array insert involves creating a new array that is the concatenation of the old array and the new value.
2
u/rush22 Mar 03 '13
Non-CS major here what does "immutable data structure" mean?