This notebook is licenced under CC BY-SA 4.0.

Sources at Github.

In [1]:

```
)set message type off
)set output algebra off
setFormat!(FormatMathJax)$JFriCASSupport
)set message type on
```

In [2]:

```
)version
```

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]:

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

In [3]:

```
r.name
```

Out[3]:

In [4]:

```
r.age := 75
```

Out[4]:

In [5]:

```
r
```

Out[5]:

`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]:

In [7]:

```
u := "some text"
```

Out[7]:

In [8]:

```
(u case int, u case str)
```

Out[8]:

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]:

In [10]:

```
s := ("Das", "ist", "ein", "Haus")
```

Out[10]:

Tuples can be used in parallel assignments.

In [11]:

```
(x,y,z) := (-1,0,1);
```

Out[11]:

In [12]:

```
(z,y,x)
```

Out[12]:

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

The type `List(T)`

denotes linked lists whose elements all
belong to type `T`

.

In [13]:

```
li := [2,4,5,-6]
```

Out[13]:

In [14]:

```
ls := ["I", "am", "a", "list", "of", "strings"]
```

Out[14]:

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]:

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
```

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

In [18]:

```
concat("foo", li)
```

In [16]:

```
concat(3, li)
```

Out[16]:

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

In [17]:

```
li.3
```

Out[17]:

The length of a list can be computed by the `#`

operation.

In [18]:

```
#li
```

Out[18]:

Lists can be constructed by list comprehension.

In [19]:

```
[3*x for x in 1..10]
```

Out[19]:

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]:

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]:

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]:

In [23]:

```
removeDuplicates a
```

Out[23]:

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]:

In [25]:

```
upper."a" := "A"
```

Out[25]:

In [26]:

```
for i in 1..3 repeat upper("bcd".i) := "BCD".i
```

Out[26]:

In [27]:

```
upper
```

Out[27]:

In [28]:

```
upper."c"
```

Out[28]:

`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]:

Out[33]:

Out[33]:

Out[33]:

Segmented lists provide a way to enter data efficiently.

In [34]:

```
sl := [2..5,3,-1,-2..5, 10..20]
```

Out[34]:

In [35]:

```
expand sl
```

Out[35]:

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]:

In [37]:

```
[x^2 for x in sg | even? x]
```

Out[37]:

Segments need not have an upper bound.

In [38]:

```
sp := 0..
```

Out[38]:

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]:

In [40]:

```
odd := [2*n+1 for n in 0..]
```

Out[40]:

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]:

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

In [42]:

```
entries first9even
```

Out[42]:

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]:

In [44]:

```
[extract! h for n in 1..3]
```

Out[44]:

In [45]:

```
h
```

Out[45]:

In [46]:

```
insert!("b2",h)
```

Out[46]:

In [47]:

```
members h
```

Out[47]:

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
```

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]:

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]:

In [50]:

```
multiset li
```

Out[50]:

A set is an unordered list with duplicates removed.

In [51]:

```
s := set li
```

Out[51]:

One can ask for the size of the set.

In [52]:

```
#s
```

Out[52]:

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]:

Out[54]:

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

In [54]:

```
s.3
```

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]:

In [56]:

```
top s
```

Out[56]:

In [57]:

```
push!(-7,s)
```

Out[57]:

In [58]:

```
s
```

Out[58]:

In [59]:

```
#s
```

Out[59]:

In [60]:

```
pop! s
```

Out[60]:

In [61]:

```
s
```

Out[61]:

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

In [62]:

```
)what domain Tree
```

In [63]:

```
)what domain Queue
```

In [64]:

```
)what domain Stream
```