Walnut/Ordinary Programming/Data Structures

From Erights

(Difference between revisions)
Jump to: navigation, search
(Equality Testing for Structures: Explicitly state why == checks ordering.)
 
Line 42: Line 42:
</pre>
</pre>
 +
 +
Warning: don't try to use the editable.add() method to push an item (as you would do in Java). "add" does the same thing as "+"; it returns a new list while leaving the original unchanged.
All the methods that work on a ConstList also work on a FlexList. In addition, there are editing operations for FlexLists, including push/pop (which allows the FlexList to behave like a stack) and element replacement that uses Java array-style syntax. You can get a ConstList from a FlexList with the snapshot method. Just as Java Strings are like ConstLists in which all elements are characters, Java StringBuffers are like FlexLists in which all elements are characters.
All the methods that work on a ConstList also work on a FlexList. In addition, there are editing operations for FlexLists, including push/pop (which allows the FlexList to behave like a stack) and element replacement that uses Java array-style syntax. You can get a ConstList from a FlexList with the snapshot method. Just as Java Strings are like ConstLists in which all elements are characters, Java StringBuffers are like FlexLists in which all elements are characters.
Line 63: Line 65:
</pre>
</pre>
-
Elements in a map are retrieved using an array-like syntax, using the key as the index in the square brackets. Maps can be made from lists using asMap and asKeys; when you use asKeys, the values are nulls. The for loop works nicely with the map structures.
+
Elements in a map are retrieved using an array-like syntax, using the key as the index in the square brackets.  
 +
If you're not sure whether the key will be present, you can use the fetch method instead; this takes a function as its second argument and evaluates that if the key isn't present. e.g.
 +
 
 +
<pre>
 +
def value := table.fetch("key", def ifMissing() { return null })
 +
</pre>
 +
 
 +
You will often see this shortened further, using the "fn" syntax for anonymous functions:
 +
 
 +
<pre>
 +
def value := table.fetch("key", fn { null })
 +
</pre>
 +
 
 +
Maps can be made from lists using asMap and asKeys; when you use asKeys, the values are nulls. The for loop works nicely with the map structures.
FlexMaps can be made from ConstMaps with the diverge method:
FlexMaps can be made from ConstMaps with the diverge method:
Line 109: Line 124:
One of the biggest differences between Flex and Const structures is the test for equality. Const structures are compared by value, and as such are considered equal if their contents are identical. The test for equality is, in other words, the same as the test for equality between Java integers.
One of the biggest differences between Flex and Const structures is the test for equality. Const structures are compared by value, and as such are considered equal if their contents are identical. The test for equality is, in other words, the same as the test for equality between Java integers.
 +
 +
Note that since the <code>==</code> test guarantees that two objects are completely indistinguishable, the order of elements in maps and sets is part of the comparison; two sets with the same elements in different orders are not equal according to <code>==</code>. Use <code>&lt;=&gt;</code>, the “asBigAs” operator, instead to check whether two sets contain the same items. (Because ordering is significant, the order is also guaranteed to be preserved e.g. when iterating over the elements — it will not be arbitrarily rearranged (such as due to a rehashing of an internal hash table) as is possible in many other languages' collections.)
Two Flex structures are considered equal if and only if they are the same structure, i.e., both of the variables being tested are references to a single object. This test for equality is, in other words, the same as the test for equality between Java StringBuffers.
Two Flex structures are considered equal if and only if they are the same structure, i.e., both of the variables being tested are references to a single object. This test for equality is, in other words, the same as the test for equality between Java StringBuffers.

Latest revision as of 17:11, 25 February 2011

Data Structures

In the next section, we will learn how to interface to Java, which will allow you to use most of the data structures supplied by the underlying jvm. E does offer a few data structures of its own, however, which are not only convenient, but which have special properties useful in distributed programming.

Flex and Const, List, Map and Set

There are three built-in data structures in E, Lists, Maps, and Sets. Each of these structures comes in two flavors, Flex (editable) and Const (immutable). The ConstList is the simplest:


 # E sample
 def list := ["a",2,true]
 #This is true: list[0] == "a"
 #This is true: list[2] == true
 def newList := list + ["last"]
 #This is true: newList[3] == "last"
 for each in newList {println(`Element: $each`)}
 for i => each in newList {println(`Element number $i is $each`)}
 def listSize := newList.size()
 # get subrange starting at 0, running up to element 2, but not including element 2
 def subrange := list(0,2)
 #This is true: subrange == ["a",2]

Lists are numerically indexed starting from 0, use the "+" operator to create a new list which is the concatenation of lists. Lists work with the for loop. The "size" method returns the number of elements. The E String type is a kind of ConstList in which all the elements are characters. So, for example, the mechanism for taking a subrange shown above gives you a substring if the ConstList is a String.

You can make a FlexList from a ConstList with the diverge method:


 # E sample
 def newList := []
 def editable := newList.diverge()
 editable.push(100)
 if (editable.pop() == 100) {
     println("Yeah, push and pop make a list work like a stack")
 }
 editable[0] := "b"
 def frozen := editable.snapshot() 

Warning: don't try to use the editable.add() method to push an item (as you would do in Java). "add" does the same thing as "+"; it returns a new list while leaving the original unchanged.

All the methods that work on a ConstList also work on a FlexList. In addition, there are editing operations for FlexLists, including push/pop (which allows the FlexList to behave like a stack) and element replacement that uses Java array-style syntax. You can get a ConstList from a FlexList with the snapshot method. Just as Java Strings are like ConstLists in which all elements are characters, Java StringBuffers are like FlexLists in which all elements are characters.

Maps are composed of key/value pairs. In the following example, in the ConstMap table, "a" is a key, and 1 is a value:


 # E sample
 def table := ["a" => 1, 2 => "b"]
 # This is true: table["a"] == 1
 # This is true: table[2] == "b"
 def emptyTable := [].asMap()
 def keyTable := ["a",1,true].asKeys()
 # This is true: keyTable[true] == null 
 # This is true: keyTable.maps("a") == true
 for key => value in table {println(`Key: $key Value: $value`)}
 for each in table {println(`Value: $each`)}
 def mapSize := table.size()

Elements in a map are retrieved using an array-like syntax, using the key as the index in the square brackets. If you're not sure whether the key will be present, you can use the fetch method instead; this takes a function as its second argument and evaluates that if the key isn't present. e.g.

 def value := table.fetch("key", def ifMissing() { return null })

You will often see this shortened further, using the "fn" syntax for anonymous functions:

 def value := table.fetch("key", fn { null })

Maps can be made from lists using asMap and asKeys; when you use asKeys, the values are nulls. The for loop works nicely with the map structures.

FlexMaps can be made from ConstMaps with the diverge method:


 # E sample
 def editableMap := table.diverge()
 editableMap["c"] := 3
 editableMap["a"] := "replacement"
 editableMap.removeKey(2)
 def frozenMap := editableMap.snapshot() 

Values in a FlexMap can be added and replaced with array-like syntax. Key-value pairs can be removed with removeKey(key). The snapshot method creates a ConstMap from a FlexMap.

Sets are quite similar, with ["a","b"].asSet() producing a ConstSet with 2 elements. Documentation for all the operations on Const and Flex lists, maps, and sets can be reached directly from the Javadoc For E index.

A String is actually a ConstList of characters. You can create a FlexList of elements of a specific type by specifying the type in the diverge/snapshot method:


 # E sample
 def aString := [].diverge(char)

This aString will not accept elements which are not of type char; the variable aString has many of the characteristics of a StringBuffer from Java.

One feature of E that Java/C programmers will find surprising but useful is the ability to define multiple variables by using a list:


 # E sample
 def [a,b] := [2,3] 
 #a holds the value 2
 #b holds the value 3

While this is an amusing way to initialize a random bunch of variables at once, the structure is most valuable when creating groups of variables that have no meaning in the absence of one another. The method Ref.promise(), described in Distributed Computing, is an important user of this pattern.

Equality Testing for Structures

One of the biggest differences between Flex and Const structures is the test for equality. Const structures are compared by value, and as such are considered equal if their contents are identical. The test for equality is, in other words, the same as the test for equality between Java integers.

Note that since the == test guarantees that two objects are completely indistinguishable, the order of elements in maps and sets is part of the comparison; two sets with the same elements in different orders are not equal according to ==. Use <=>, the “asBigAs” operator, instead to check whether two sets contain the same items. (Because ordering is significant, the order is also guaranteed to be preserved e.g. when iterating over the elements — it will not be arbitrarily rearranged (such as due to a rehashing of an internal hash table) as is possible in many other languages' collections.)

Two Flex structures are considered equal if and only if they are the same structure, i.e., both of the variables being tested are references to a single object. This test for equality is, in other words, the same as the test for equality between Java StringBuffers.

Personal tools
more tools