Walnut/Ordinary Programming/Data Structures - Revision history

Kevin Reid: /* Equality Testing for Structures */ Explicitly state why == checks ordering.

2011-02-25T17:11:07Z

Equality Testing for Structures: Explicitly state why == checks ordering.

New page

[[Category:Walnut|2]]
===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:

<pre>

<nowiki># 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]</nowiki>

</pre>

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:

<pre>

<nowiki># 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() </nowiki>

</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.

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

<pre>

<nowiki># 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()</nowiki>

</pre>

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:

<pre>

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

</pre>

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 [http://www.erights.org/javadoc/index.html 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:

<pre>

<nowiki># E sample
def aString := [].diverge(char)</nowiki>

</pre>

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:

<pre>

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

</pre>

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 <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><=></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.

ThomasLeonard: /* Equality Testing for Structures */

2011-02-22T14:08:00Z

Equality Testing for Structures

←Older revision		Revision as of 14:08, 22 February 2011
Line 124:		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, in E, the order of elements in maps and sets is sometimes significant (e.g. when iterating over the elements) and so two sets with the same elements in different orders are not equal according to ==. Use <=>, the "asBigAs" operator, to check that two sets contain the same items.

	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.

ThomasLeonard: /* Flex and Const, List, Map and Set */

2010-09-17T15:44:06Z

Flex and Const, List, Map and Set

←Older revision		Revision as of 15:44, 17 September 2010
Line 65:		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:

ThomasLeonard: Warn about list.add()

2009-07-21T08:30:19Z

Warn about list.add()

←Older revision		Revision as of 08:30, 21 July 2009
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.

Kevin Reid: Reverted edits by 140.113.152.201 (Talk); changed back to last version by Mscheffler

2009-01-04T15:50:59Z

Reverted edits by 140.113.152.201 (Talk); changed back to last version by Mscheffler

←Older revision		Revision as of 15:50, 4 January 2009
Line 1:		Line 1:
-	~~eracelsit~~
	[[Category:Walnut\|2]]		[[Category:Walnut\|2]]
	===Data Structures===		===Data Structures===

140.113.152.201: baschid

2009-01-04T06:13:38Z

baschid

←Older revision		Revision as of 06:13, 4 January 2009
Line 1:		Line 1:
		+	eracelsit
	[[Category:Walnut\|2]]		[[Category:Walnut\|2]]
	===Data Structures===		===Data Structures===

Mscheffler at 10:17, 29 November 2006

2006-11-29T10:17:46Z

←Older revision		Revision as of 10:17, 29 November 2006
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 65:		Line 63:
	</pre>		</pre>

-	Elements in a map are retrieved using an array-like syntax, using the key as the index in the square brackets.	+	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.
-	~~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 124:		Line 109:

	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><=></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.