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