This notebook is licenced under CC BY-SA 4.0.

FriCAS Tutorial (Data structures)

Ralf Hemmecke <ralf@hemmecke.org>

Sources at Github.

In [1]:
)set message type off
)set output algebra off
setFormat!(FormatMathJax)$JFriCASSupport
)set message type on
In [2]:
)version

Value = "FriCAS a9422d32eb6f6b03d98ac6adfc9bf05ec0f5e8bd compiled at Sa 03 Apr 2021 00:29:13 CEST"

Language-defined Types

A record is a data structure with a fixed number of named entries.

In [2]:
r: Record(name: String, age: Integer) := ["Albert", 42]
Out[2]:
\[ \left[name=\texttt{"Albert"}, age=42\right] \]
Record(name: String,age: Integer)

Getting and setting entries is done by using a dot notation.

In [3]:
r.name
Out[3]:
\[ \texttt{"Albert"} \]
In [4]:
r.age := 75
Out[4]:
\[ 75 \]
In [5]:
r
Out[5]:
\[ \left[name=\texttt{"Albert"}, age=75\right] \]
Record(name: String,age: Integer)

Union is a data structure that can hold any value of the given types, but no value of any other type. In mathematical terms, it corresponds to the disjoint union.

In [6]:
u: Union(str: String, int: Integer, flo: Float) := 4::Integer
Out[6]:
\[ 4 \]
Union(int: Integer,...)
In [7]:
u := "some text"
Out[7]:
\[ \texttt{"some text"} \]
Union(str: String,...)
In [8]:
(u case int, u case str)
Out[8]:
\[ \left[\texttt{false}, \texttt{true}\right] \]

Tuples are immutable, i.e., you cannot change an entry. All entries must be of the same type.

In [9]:
t := (3, -1, 17)
Out[9]:
\[ \left[3, -1, 17\right] \]
In [10]:
s := ("Das", "ist", "ein", "Haus")
Out[10]:
\[ \left[\texttt{"Das"}, \texttt{"ist"}, \texttt{"ein"}, \texttt{"Haus"}\right] \]

Tuples can be used in parallel assignments.

In [11]:
(x,y,z) := (-1,0,1);
Out[11]:
In [12]:
(z,y,x)
Out[12]:
\[ \left[1, 0, -1\right] \]

Library-defined Data Types

FriCAS comes with a lot of data structures. There are lists, arrays, hash tables, trees, streams, etc.

List

The type List(T) denotes linked lists whose elements all belong to type T.

In [13]:
li := [2,4,5,-6]
Out[13]:
\[ \left[2, 4, 5, -6\right] \]
In [14]:
ls := ["I", "am", "a", "list", "of", "strings"]
Out[14]:
\[ \left[\texttt{"I"}, \texttt{"am"}, \texttt{"a"}, \texttt{"list"}, \texttt{"of"}, \texttt{"strings"}\right] \]

All elements of a list must belong to the same type. This is advantageous, since the type of the list asserts something about its members.

In [15]:
concat ls
Out[15]:
\[ \texttt{"Iamalistofstrings"} \]

The following operation fails immediately without ever touching one single element of the list. Now imagine what happens in a typeless system for a list with 1000 elements that are all strings except the last one.

In [17]:
concat li

There are 2 exposed and 0 unexposed library operations named concat having 1 
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) 
                                List(Integer)
 
Perhaps you should use "@" to indicate the required return type, or "$" to 
specify which version of the function you need.

FriCAS does not allow to insert an element of the wrong type into the list.

In [18]:
concat("foo", li)

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) 
                                   String
                                List(Integer)
 
Perhaps you should use "@" to indicate the required return type, or "$" to 
specify which version of the function you need.
In [16]:
concat(3, li)
Out[16]:
\[ \left[3, 2, 4, 5, -6\right] \]

One can access a particular element of the list with the dot notation.

In [17]:
li.3
Out[17]:
\[ 5 \]

The length of a list can be computed by the # operation.

In [18]:
#li
Out[18]:
\[ 4 \]

Lists can be constructed by list comprehension.

In [19]:
[3*x for x in 1..10]
Out[19]:
\[ \left[3, 6, 9, 12, 15, 18, 21, 24, 27, 30\right] \]

The vertical bar denotes a "such-that" clause, i.e. an element only belongs to the list, if the boolean expression in the such-that clause is satisfied.

In [20]:
[3*x+1 for x in 1..20 | odd? x]
Out[20]:
\[ \left[4, 10, 16, 22, 28, 34, 40, 46, 52, 58\right] \]

List can contain more complicated structures. Note the parallel iteration scheme in the following expression.

In [21]:
[concat(x ,concat(y, li)) for x in 1..3 for y in -1..-100 by -2]
Out[21]:
\[ \left[\left[1, -1, 2, 4, 5, -6\right], \left[2, -3, 2, 4, 5, -6\right], \left[3, -5, 2, 4, 5, -6\right]\right] \]

Array

Arrays allow for constant time access since its elements are stored in a contiguous block of memory.

In [22]:
a := oneDimensionalArray [2,3,9,-1,-3,2,7]
Out[22]:
\[ \left[2, 3, 9, -1, -3, 2, 7\right] \]
In [23]:
removeDuplicates a
Out[23]:
\[ \left[2, 3, 9, -1, -3, 7\right] \]

Hash Table

Hash tables allow a (nearly) constant time access. They can be thought of as a partial function from the key space to the value space. Table relies on the underlying Lisp hashing facilities and, therefore, uses AssociationList with linear access time if the Key type is not recognized to be hashable via Lisp.

In [24]:
upper := table() $ Table(String, String)
Out[24]:
\[ \texttt{table}\left(\right) \]
In [25]:
upper."a" := "A"
Out[25]:
\[ \texttt{"A"} \]
In [26]:
for i in 1..3 repeat upper("bcd".i) := "BCD".i
Out[26]:
In [27]:
upper
Out[27]:
\[ \texttt{table}\left(\texttt{"d"}=\texttt{"D"}, \texttt{"c"}=\texttt{"C"}, \texttt{"b"}=\texttt{"B"}, \texttt{"a"}=\texttt{"A"}\right) \]
In [28]:
upper."c"
Out[28]:
\[ \texttt{"C"} \]

XHashTable is an efficient implementation of a hash table structure with (almost) linear element access time due to the use of a hash function and direct array access.

In contrast to Table, XHashTable works for all key types that export a hash function.

Now we can repeat the commands from above with Table replaced by XHashTable.

In [33]:
upper := table() $ XHashTable(String, String) ;
upper."a" := "A"
for i in 1..3 repeat upper("bcd".i) := "BCD".i
upper
upper."c"
Out[33]:
Out[33]:
\[ \texttt{"A"} \]
Out[33]:
Out[33]:
\[ \texttt{table}\left(\texttt{"a"}=\texttt{"A"}, \texttt{"d"}=\texttt{"D"}, \texttt{"c"}=\texttt{"C"}, \texttt{"b"}=\texttt{"B"}\right) \]
Out[33]:
\[ \texttt{"C"} \]

Segment

Segmented lists provide a way to enter data efficiently.

In [34]:
sl := [2..5,3,-1,-2..5, 10..20]
Out[34]:
\[ \left[2\mathbin{\operatorname{..}}5, 3\mathbin{\operatorname{..}}3, \left(-1\right)\mathbin{\operatorname{..}}\left(-1\right), \left(-2\right)\mathbin{\operatorname{..}}5, 10\mathbin{\operatorname{..}}20\right] \]
In [35]:
expand sl
Out[35]:
\[ \left[2, 3, 4, 5, 3, -1, -2, -1, 0, 1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20\right] \]

Segments can also be stored in a variable and remembered for later. With the by keyword one can specify a stepsize. Of course, the stepsize can be negative.

In [36]:
sg := 4 .. 20 by 3
Out[36]:
\[ 4\mathbin{\operatorname{..}}20\texttt{ by }3 \]
In [37]:
[x^2 for x in sg | even? x]
Out[37]:
\[ \left[16, 100, 256\right] \]

Segments need not have an upper bound.

In [38]:
sp := 0..
Out[38]:
\[ 0{\operatorname{..}} \]

Stream

Infinite data structures can be handled. A stream is like an infinite list. Elements are computed on demand.

In [39]:
even := [2*n for n in sp]
Out[39]:
\[ \left[0, 2, 4, 6, 8, 10, 12, 14, 16, 18, \ldots \right] \]
In [40]:
odd := [2*n+1 for n in 0..]
Out[40]:
\[ \left[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, \ldots \right] \]

The for construction can be combined with a second one in order to run over two structures in parallel.

In [41]:
first9even := [n for n in even for k in 1..9]
Out[41]:
\[ \left[0, 2, 4, 6, 8, 10, 12, 14, 16\right] \]

In case the stream is finite, it can be converted into a list.

In [42]:
entries first9even
Out[42]:
\[ \left[0, 2, 4, 6, 8, 10, 12, 14, 16\right] \]

Heap

The domain Heap is a special data structure that allows to insert elements in $O(\log n)$ time and extracts the maximum from the heap also in $O(\log n)$. Heaps are most appropriate for algorithms that need a priority queue.

In [43]:
h := heap  ["a", "c", "d", "b","f", "h", "z","b"]
Out[43]:
\[ \left[\texttt{"z"}, \texttt{"f"}, \texttt{"h"}, \texttt{"b"}, \texttt{"c"}, \texttt{"a"}, \texttt{"d"}, \texttt{"b"}\right] \]
In [44]:
[extract! h for n in 1..3]
Out[44]:
\[ \left[\texttt{"z"}, \texttt{"h"}, \texttt{"f"}\right] \]
In [45]:
h
Out[45]:
\[ \left[\texttt{"d"}, \texttt{"c"}, \texttt{"a"}, \texttt{"b"}, \texttt{"b"}\right] \]
In [46]:
insert!("b2",h)
Out[46]:
\[ \left[\texttt{"d"}, \texttt{"c"}, \texttt{"b2"}, \texttt{"b"}, \texttt{"b"}, \texttt{"a"}\right] \]
In [47]:
members h
Out[47]:
\[ \left[\texttt{"d"}, \texttt{"c"}, \texttt{"b2"}, \texttt{"b"}, \texttt{"b"}, \texttt{"a"}\right] \]

Because of the algorithms used to implement a heap, it makes no sense to provide a mechanism to extract the $n$-th element directly.

In [47]:
h.3

There are no library operations named h 
Use HyperDoc Browse or issue
                                 )what op h
to learn if there is any operation containing " h " in its name.
Cannot find a definition or applicable library operation named h with 
argument type(s) 
                               PositiveInteger
 
Perhaps you should use "@" to indicate the required return type, or "$" to 
specify which version of the function you need.

It is also impossible to create a heap over a domain that does not provide an ordering operation.

In [48]:
PrimeField 7 has OrderedSet
Heap(PrimeField 7)
Out[48]:
\[ \texttt{false} \] 
 Heap(PrimeField(7)) is not a valid type.

Multiset

A multiset stores elements together with its occurences. It is like an unordered list with duplicates allowed.

In [49]:
li := [1,2,4,5,6,2,5,1,4,2,5]
Out[49]:
\[ \left[1, 2, 4, 5, 6, 2, 5, 1, 4, 2, 5\right] \]
In [50]:
multiset li
Out[50]:
\[ \left\{2\texttt{ : }1, 3\texttt{ : }2, 2\texttt{ : }4, 3\texttt{ : }5, 6\right\} \]

Set

A set is an unordered list with duplicates removed.

In [51]:
s := set li
Out[51]:
\[ \left\{1, 2, 4, 5, 6\right\} \]

One can ask for the size of the set.

In [52]:
#s
Out[52]:
\[ 5 \]

Apply the usual set operations like union, intersection, set difference, etc.

In [54]:
union(s, set [3,4,5])
intersect(s, set [3,4,5])
Out[54]:
\[ \left\{1, 2, 3, 4, 5, 6\right\} \]
Out[54]:
\[ \left\{4, 5\right\} \]

Since a set is unordered, there is no concept of a $n$-th element.

In [54]:
s.3

There are no library operations named s 
Use HyperDoc Browse or issue
                                 )what op s
to learn if there is any operation containing " s " in its name.
Cannot find a definition or applicable library operation named s with 
argument type(s) 
                               PositiveInteger
 
Perhaps you should use "@" to indicate the required return type, or "$" to 
specify which version of the function you need.

Stack

A stack implements a LIFO queue (last-in, first-out). It is like a list, but not all list operations are available. For example, one cannot remove an element which is not the top-most element.

In [55]:
s := stack [2,4,-2,3,6]
Out[55]:
\[ \left[2, 4, -2, 3, 6\right] \]
In [56]:
top s
Out[56]:
\[ 2 \]
In [57]:
push!(-7,s)
Out[57]:
\[ -7 \]
In [58]:
s
Out[58]:
\[ \left[-7, 2, 4, -2, 3, 6\right] \]
In [59]:
#s
Out[59]:
\[ 6 \]
In [60]:
pop! s
Out[60]:
\[ -7 \]
In [61]:
s
Out[61]:
\[ \left[2, 4, -2, 3, 6\right] \]

There are many more data structures. Among them are trees and queues.

In [62]:
)what domain Tree

--------------------------------- Domains ---------------------------------
Domains with names matching patterns:
     tree 
 BBTREE   BalancedBinaryTree           BSTREE   BinarySearchTree
 BTCAT-   BinaryTreeCategory&          BTREE    BinaryTree
 PENDTREE PendantTree                  SPLTREE  SplittingTree
 TREE     Tree
In [63]:
)what domain Queue

--------------------------------- Domains ---------------------------------
Domains with names matching patterns:
     queue 
 DEQUEUE  Dequeue                      QUEUE    Queue
In [64]:
)what domain Stream

--------------------------------- Domains ---------------------------------
Domains with names matching patterns:
     stream 
 BITST    BitStreamFrame               LZSTAGG- LazyStreamAggregate&
 STAGG-   StreamAggregate&             STREAM   Stream