1.5 Data Structures¶
FriCAS has a large variety of data structures available. Many data structures are particularly useful for interactive computation and others are useful for building applications. The data structures of FriCAS are organized into category hierarchies.
A list, Lists are discussed in Section ListXmpPage, is the most commonly used data structure in FriCAS for holding objects all of the same type. The name list is short for linked-list of nodes. Each node consists of a value (first) and a link (rest) that points to the next node, or to a distinguished value denoting the empty list. To get to, say, the third element, FriCAS starts at the front of the list, then traverses across two links to the third node.
Write a list of elements using square brackets with commas separating the elements.
u := [1,-7,11]
Type: List Integer
This is the value at the third node. Alternatively, you can say u.3.
first rest rest u
Type: PositiveInteger
Many operations are defined on lists, such as: empty?, to test that a
list has no elements; cons(x,l), to create a new list with first element
x and rest l; reverse, to create a new list with elements in reverse
order; and sort, to arrange elements in order.
An important point about lists is that they are mutable: their
constituent elements and links can be changed in place. To do this, use
any of the operations whose names end with the character !.
The operation concat!(u,v) replaces the last link of the list
u to point to some other list v. Since u refers to the original list,
this change is seen by u.
concat!(u,[9,1,3,-4]); u
Type: List Integer
A cyclic list is a list with a cycle: a link pointing back to an earlier node of the list. To create a cycle, first get a node somewhere down the list.
lastnode := rest(u,3)
Type: List Integer
Use setrest! to change the link emanating from that node to
point back to an earlier part of the list.
setrest!(lastnode,rest(u,2)); u
Type: List Integer
A stream is a structure that (potentially) has an infinite number of distinct elements. Think of a stream as an infinite list where elements are computed successively. Streams are discussed in Section{StreamXmpPage}.
Create an infinite stream of factored integers. Only a certain number of initial elements are computed and displayed.
[factor(i) for i in 2.. by 2]
Type: Stream Factored Integer
FriCAS represents streams by a collection of already-computed elements together with a function to compute the next element on demand. Asking for the n-th element causes elements 1 through n to be evaluated.
%.36
Type: Factored Integer
Streams can also be finite or cyclic. They are implemented by a linked list structure similar to lists and have many of the same operations. For example, first and rest are used to access elements and successive nodes of a stream.
A one-dimensional array is another data structure used to hold objects of the same type OnedimensionalArray is discussed in Section OneDimensionalArrayXmpPage. Unlike lists, one-dimensional arrays are inflexible - they are implemented using a fixed block of storage. Their advantage is that they give quick and equal access time to any element.
A simple way to create a one-dimensional array is to apply the operation oneDimensionalArray to a list of elements.
a := oneDimensionalArray [1, -7, 3, 3/2]
Type: OneDimensionalArray Fraction Integer
One-dimensional arrays are also mutable: you can change their constituent elements in place.
a.3 := 11; a
Type: OneDimensionalArray Fraction Integer
However, one-dimensional arrays are not flexible structures. You cannot
destructively concat! them together.
concat!(a,oneDimensionalArray [1,-2])
Warning
There are 5 exposed and 0 unexposed library operations named concat! having 2 argument(s) but none was determined to be applicable. Use HyperDoc Browse, or issue )display op concat! to learn more about the available operations. Perhaps package-calling the operation or using coercions on the arguments will allow you to apply the operation.
Cannot find a definition or applicable library operation named concat! with argument type(s) OneDimensionalArray Fraction Integer OneDimensionalArray Integer
Perhaps you should use ”@” to indicate the required return type, or ”$” to specify which version of the function you need.
Examples of datatypes similar to OneDimensionalArray are: Vector
(vectors are mathematical structures implemented by one-dimensional
arrays), String (arrays of characters, represented by byte vectors), and
Bits (represented by bit vectors).
A vector of 32 bits, each representing the Boolean value true.
bits(32,true)
Type: Bits
A flexible array (FlexibleArray is discussed in Section FlexibleArrayXmpPage ) is a cross between a list and a one-dimensional array. Like a one-dimensional array, a flexible array occupies a fixed block of storage. Its block of storage, however, has room to expand. When it gets full, it grows (a new, larger block of storage is allocated); when it has too much room, it contracts.
Create a flexible array of three elements.
f := flexibleArray [2, 7, -5]
Type: FlexibleArray Integer
Insert some elements between the second and third elements.
insert!(flexibleArray [11, -3],f,2)
Type: FlexibleArray Integer
Flexible arrays are used to implement heaps. A heap is an example of a
data structure called a priority queue, where elements are ordered with
respect to one another. A heap (Heap is discussed in Section
HeapXmpPage ) is organized so as to
optimize insertion and extraction of maximum elements. The extract!
operation returns the maximum element of the heap, after destructively
removing that element and reorganizing the heap so that the next maximum
element is ready to be delivered.
An easy way to create a heap is to apply the operation heap to a list of values.
h := heap [-4,7,11,3,4,-7]
Type: Heap Integer
This loop extracts elements one-at-a-time from h until the heap is exhausted, returning the elements as a list in the order they were extracted.
[extract!(h) while not empty?(h)]
Type: List Integer
A binary tree is a tree with at most two branches tree per node: it is either empty, or else is a node consisting of a value, and a left and right subtree (again, binary trees). (BinarySearchTrees are discussed in Section BinarySearchTreeXmpPage ) Examples of binary tree types are BinarySearchTree, PendantTree, TournamentTree, and BalancedBinaryTree.
A binary search tree is a binary tree such that, tree:binary search for each node, the value of the node is binary search tree greater than all values (if any) in the left subtree, and less than or equal all values (if any) in the right subtree.
binarySearchTree [5,3,2,9,4,7,11]
Type: BinarySearchTree PositiveInteger
A balanced binary tree is useful for doing modular computations. balanced binary tree Given a list lm of moduli, tree:balanced binary modTree(a,lm) produces a balanced binary tree with the values at its leaves.
modTree(8,[2,3,5,7])
Type: List Integer
A set is a collection of elements where duplication and order is irrelevant. Sets are discussed in Section SetXmpPage Sets are always finite and have no corresponding structure like streams for infinite collections.
Create sets using braces { and } rather than brackets.
fs := set[1/3,4/5,-1/3,4/5]
Type: Set Fraction Integer
A multiset is a set that keeps track of the number of duplicate values. Multisets are discussed in Section MultiSetXmpPage
For all the primes p between 2 and 1000, find the distribution of pmod5.
multiset [x rem 5 for x in primes(2,1000)]
Type: Multiset Integer
A table is conceptually a set of key-value pairs and is a generalization of a multiset. For examples of tables, see AssociationList, HashTable, KeyedAccessFile, Library, SparseTable, StringTable, and Table. The domain Table(Key, Entry) provides a general-purpose type for tables with values of type Entry indexed by keys of type Key.
Compute the above distribution of primes using tables. First, let t denote an empty table of keys and values, each of type Integer.
t : Table(Integer,Integer) := empty()
Type: Table(Integer,Integer)
We define a function howMany to return the number of values of a given
modulus k seen so far. It calls search(k,t) which returns the number of
values stored under the key k in table t, or failed if no such value is
yet stored in t under k.
In English, this says
Define howMany(k) as follows. First, let n be the value of search(k,t). Then, if n has the value “failed”, return the value 1; otherwise return n+1.
howMany(k) == (n:=search(k,t); n case "failed" => 1; n+1)
Type: Void
Run through the primes to create the table, then print the table. The expression t.m := howMany(m) updates the value in table t stored under key m.
for p in primes(2,1000) repeat (m:= p rem 5; t.m:= howMany(m)); t
Compiling function howMany with type Integer -> Integer
Type: Table(Integer,Integer)
A record is an example of an inhomogeneous collection of objects. See ugTypesRecords for details. A record consists of a set of named selectors that can be used to access its components.
Declare that daniel can only be assigned a record with two prescribed fields.
daniel : Record(age : Integer, salary : Float)
Type: Void
Give daniel a value, using square brackets to enclose the values of the fields.
daniel := [28, 32005.12]
Type: Record(age: Integer,salary: Float)
Give daniel a raise.
daniel.salary := 35000; daniel
Type: Record(age: Integer,salary: Float)
A union is a data structure used when objects have multiple types.See ugTypesUnions for details.
Let dog be either an integer or a string value.
dog: Union(licenseNumber: Integer, name: String)
Type: Void
Give dog a name.
dog := "Whisper"
Type: Union(name: String,...)
All told, there are over forty different data structures in FriCAS. Using the domain constructors described in Chapter ugDomains you can add your own data structure or extend an existing one. Choosing the right data structure for your application may be the key to obtaining good performance.