0.6 Data Structures in FriCAS¶

This chapter is an overview of some of the data structures provided by FriCAS.

0.6.1 Lists¶

The FriCAS List type constructor is used to create homogeneous lists of finite size. The notation for lists and the names of the functions that operate over them are similar to those found in functional languages such as ML.

Lists can be created by placing a comma separated list of values inside square brackets or if a list with just one element is desired then the function list is available:

[4]

\[[4]\]

_{Type: List PositiveInteger}

list(4)

\[[4]\]

_{Type: List PositiveInteger}

[1,2,3,5,7,11]

\[[1,2,3,5,7,11]\]

_{Type: List PositiveInteger}

The function append takes two lists as arguments and returns the list consisting of the second argument appended to the first. A single element can be added to the front of a list using cons:

append([1,2,3,5],[7,11])

\[[1,2,3,5,7,11]\]

_{Type: List PositiveInteger}

cons(23,[65,42,19])

\[[23,65,42,19]\]

_{Type: List PositiveInteger}

Lists are accessed sequentially so if FriCAS is asked for the value of the twentieth element in the list it will move from the start of the list over nineteen elements before it reaches the desired element. Each element of a list is stored as a node consisting of the value of the element and a pointer to the rest of the list. As a result the two main operations on a list are called first and rest. Both of these functions take a second optional argument which specifies the length of the first part of the list:

first([1,5,6,2,3])

\[1\]

_{Type: PositiveInteger}

first([1,5,6,2,3],2)

\[[1,5]\]

_{Type: List PositiveInteger}

rest([1,5,6,2,3])

\[[5,6,2,3]\]

_{Type: List PositiveInteger}

rest([1,5,6,2,3],2)

\[[6,2,3]\]

_{Type: List PositiveInteger}

Other functions are empty? which tests to see if a list contains no elements, member? which tests to see if the first argument is a member of the second, reverse which reverses the order of the list, sort which sorts a list, and removeDuplicates which removes any duplicates. The length of a list can be obtained using the `` #`` operator.

empty?([7,2,-1,2])

\[false\]

_{Type: Boolean}

member?(-1,[7,2,-1,2])

\[true\]

_{Type: Boolean}

reverse([7,2,-1,2])

\[[2,-1,2,7]\]

_{Type: List Integer}

sort([7,2,-1,2])

\[[-1,2,2,7]\]

_{Type: List Integer}

removeDuplicates([1,5,3,5,1,1,2])

\[[1,5,3,2]\]

_{Type: List PositiveInteger}

#[7,2,-1,2]

\[4\]

_{Type: PositiveInteger}

Lists in FriCAS are mutable and so their contents (the elements and the links) can be modified in place. Functions that operator over lists in this way have names ending in the symbol !. For example, concat! takes two lists as arguments and appends the second argument to the first (except when the first argument is an empty list) and setrest! changes the link emanating from the first argument to point to the second argument:

u := [9,2,4,7]

\[[9,2,4,7]\]

_{Type: List PositiveInteger}

concat!(u,[1,5,42]); u

\[[9,2,4,7,1,5,42]\]

_{Type: List PositiveInteger}

endOfu := rest(u,4)

\[[1,5,42]\]

_{Type: List PositiveInteger}

partOfu := rest(u,2)

\[[4,7,1,5,42]\]

_{Type: List PositiveInteger}

setrest!(endOfu,partOfu); u

\[\left\lbrack 9,2,\overline{4,7,1} \right\rbrack\]

_{Type: List PositiveInteger}

From this it can be seen that the lists returned by first and rest are pointers to the original list and not a copy. Thus great care must be taken when dealing with lists in FriCAS.

Although the nth element of the list l can be obtained by applying the first function to n-1 applications of rest to l, FriCAS provides a more useful access method in the form of the . operator:

u.3

\[4\]

_{Type: PositiveInteger}

u.5

\[1\]

_{Type: PositiveInteger}

u.6

\[4\]

_{Type: PositiveInteger}

first rest rest u -- Same as u.3

\[4\]

_{Type: PositiveInteger}

u.first

\[9\]

_{Type: PositiveInteger}

u(3)

\[4\]

_{Type: PositiveInteger}

The operation u.i is referred to as indexing into u or elting into u. The latter term comes from the elt function which is used to extract elements (the first element of the list is at index 1).

elt(u,4)

\[7\]

_{Type: PositiveInteger}

If a list has no cycles then any attempt to access an element beyond the end of the list will generate an error. However, in the example above there was a cycle starting at the third element so the access to the sixth element wrapped around to give the third element. Since lists are mutable it is possible to modify elements directly:

u.3 := 42; u

\[\left\lbrack 9,2,\overline{42,7,1} \right\rbrack\]

_{Type: List PositiveInteger}

Other list operations are:

L := [9,3,4,7]; #L

\[4\]

_{Type: PositiveInteger}

last(L)

\[7\]

_{Type: PositiveInteger}

L.last

\[7\]

_{Type: PositiveInteger}

L.( #L - 1)

\[4\]

_{Type: PositiveInteger}

Note that using the `` #`` operator on a list with cycles causes FriCAS to enter an infinite loop.

Note that any operation on a list L that returns a list LL′ will, in general, be such that any changes to LL′ will have the side-effect of altering L. For example:

m := rest(L,2)

\[[4,7]\]

_{Type: List PositiveInteger}

m.1 := 20; L

\[[9,3,20,7]\]

_{Type: List PositiveInteger}

n := L

\[[9,3,20,7]\]

_{Type: List PositiveInteger}

n.2 := 99; L

\[[9,99,20,7]\]

_{Type: List PositiveInteger}

\[[9,99,20,7]\]

_{Type: List PositiveInteger}

Thus the only save way of copying lists is to copy each element from one to another and not use the assignment operator:

p := [i for i in n] -- Same as p := copy(n)

\[[9,99,20,7]\]

_{Type: List PositiveInteger}

p.2 := 5; p

\[[9,5,20,7]\]

_{Type: List PositiveInteger}

\[[9,99,20,7]\]

_{Type: List PositiveInteger}

In the previous example a new way of constructing lists was given. This is a powerful method which gives the reader more information about the contents of the list than before and which is extremely flexible. The example

[i for i in 1..10]

\[[1,2,3,4,5,6,7,8,9,10]\]

_{Type: List PositiveInteger}

should be read as

Using the expression i, generate each element of the list by iterating the symbol i over the range of integers [1,10]

To generate the list of the squares of the first ten elements we just use:

[i^2 for i in 1..10]

\[[1,4,9,16,25,36,49,64,81,100]\]

_{Type: List PositiveInteger}

For more complex lists we can apply a condition to the elements that are to be placed into the list to obtain a list of even numbers between 0 and 11:

[i for i in 1..10 | even?(i)]

\[[2,4,6,8,10]\]

_{Type: List PositiveInteger}

This example should be read as:

Using the expression i, generate each element of the list by iterating the symbol i over the range of integers [1,10] such that i is even

The following achieves the same result:

[i for i in 2..10 by 2]

\[[2,4,6,8,10]\]

_{Type: List PositiveInteger}

0.6.2 Segmented Lists¶

A segmented list is one in which some of the elements are ranges of values. The expand function converts lists of this type into ordinary lists:

[1..10]

\[[1..10]\]

_{Type: List Segment PositiveInteger}

[1..3,5,6,8..10]

\[[1..3,5..5,6..6,8..10]\]

_{Type: List Segment PositiveInteger}

expand(%)

\[[1,2,3,5,6,8,9,10]\]

_{Type: List Integer}

If the upper bound of a segment is omitted then a different type of segmented list is obtained and expanding it will produce a stream (which will be considered in the next section):

[1..]

\[[1..]\]

_{Type: List UniversalSegment PositiveInteger}

expand(%)

\[[1,2,3,4,5,6,7,8,9,10,…]\]

_{Type: Stream Integer}

0.6.3 Streams¶

Streams are infinite lists which have the ability to calculate the next element should it be required. For example, a stream of positive integers and a list of prime numbers can be generated by:

[i for i in 1..]

\[[1,2,3,4,5,6,7,8,9,10,…]\]

_{Type: Stream PositiveInteger}

[i for i in 1.. | prime?(i)]

\[[2,3,5,7,11,13,17,19,23,29,…]\]

_{Type: Stream PositiveInteger}

In each case the first few elements of the stream are calculated for display purposes but the rest of the stream remains unevaluated. The value of items in a stream are only calculated when they are needed which gives rise to their alternative name of lazy lists.

Another method of creating streams is to use the generate(f,a) function. This applies its first argument repeatedly onto its second to produce the stream [a,f(a),f(f(a)),f(f(f(a)))…]. Given that the function nextPrime returns the lowest prime number greater than its argument we can generate a stream of primes as follows:

generate(nextPrime,2)$Stream Integer

\[[2,3,5,7,11,13,17,19,23,29,…]\]

_{Type: Stream Integer}

As a longer example a stream of Fibonacci numbers will be computed. The Fibonacci numbers start at 1 and each following number is the addition of the two numbers that precede it so the Fibonacci sequence is: 1,1,2,3,5,8,….

Since the generation of any Fibonacci number only relies on knowing the previous two numbers we can look at the series through a window of two elements. To create the series the window is placed at the start over the values [1,1] and their sum obtained. The window is now shifted to the right by one position and the sum placed into the empty slot of the window; the process is then repeated. To implement this we require a function that takes a list of two elements (the current view of the window), adds them, and outputs the new window. The result is the function [a,b]→b,a+b]:

win : List Integer -> List Integer

_{Type: Void}

win(x) == [x.2, x.1 + x.2]

_{Type: Void}

win([1,1])

\[[1,2]\]

_{Type: List Integer}

win(%)

\[[2,3]\]

_{Type: List Integer}

Thus it can be seen that repeatedly applying win to the results of the previous invocation each element of the series is obtained. Clearly win is an ideal function to construct streams using the generate function:

fibs := [generate(win,[1,1])]

\[[[1,1],[1,2],[2,3],[3,5],[5,8],[8,13],[13,21],[21,34],[34,55],[55,89],…]\]

_{Type: Stream List Integer}

This isn’t quite what is wanted – we need to extract the first element of each list and place that in our series:

fibs := [i.1 for i in [generate(win,[1,1])] ]

\[[1,1,2,3,5,8,13,21,34,55,…]\]

_{Type: Stream Integer}

Obtaining the 200th Fibonacci number is trivial:

fibs.200

\[280571172992510140037611932413038677189525\]

_{Type: PositiveInteger}

One other function of interest is complete which expands a finite stream derived from an infinite one (and thus was still stored as an infinite stream) to form a finite stream.

0.6.4 Arrays, Vectors, Strings, and Bits¶

The simplest array data structure is the one-dimensional array which can be obtained by applying the oneDimensionalArray function to a list:

oneDimensionalArray([7,2,5,4,1,9])

\[[7,2,5,4,1,9]\]

_{Type: OneDimensionalArray PositiveInteger}

One-dimensional array are homogenous (all elements must have the same type) and mutable (elements can be changed) like lists but unlike lists they are constant in size and have uniform access times (it is just as quick to read the last element of a one-dimensional array as it is to read the first; this is not true for lists).

Since these arrays are mutable all the warnings that apply to lists apply to arrays. That is, it is possible to modify an element in a copy of an array and change the original:

x := oneDimensionalArray([7,2,5,4,1,9])

\[[7,2,5,4,1,9]\]

_{Type: OneDimensionalArray PositiveInteger}

y := x

\[[7,2,5,4,1,9]\]

_{Type: OneDimensionalArray PositiveInteger}

y.3 := 20 ; x

\[[7,2,20,4,1,9]\]

_{Type: OneDimensionalArray PositiveInteger}

Note that because these arrays are of fixed size the concat! function cannot be applied to them without generating an error. If arrays of this type are required use the FlexibleArray constructor.

One-dimensional arrays can be created using new which specifies the size of the array and the initial value for each of the elements. Other operations that can be applied to one-dimensional arrays are map! which applies a mapping onto each element, swap! which swaps two elements and copyInto!(a,b,c) which copies the array b onto a starting at position c.

a : ARRAY1 PositiveInteger := new(10,3)

\[[3,3,3,3,3,3,3,3,3,3]\]

_{Type: OneDimensionalArray PositiveInteger}

(note that ARRAY1 is an abbreviation for the type OneDimensionalArray.) Other types based on one-dimensional arrays are Vector, String, and Bits.

map!(i +-> i+1,a); a

\[[4,4,4,4,4,4,4,4,4,4]\]

_{Type: OneDimensionalArray PositiveInteger}

b := oneDimensionalArray([2,3,4,5,6])

\[[2,3,4,5,6]\]

_{Type: OneDimensionalArray PositiveInteger}

swap!(b,2,3); b

\[[2,4,3,5,6]\]

_{Type: OneDimensionalArray PositiveInteger}

copyInto!(a,b,3)

\[[4,4,2,4,3,5,6,4,4,4]\]

_{Type: OneDimensionalArray PositiveInteger}

\[[4,4,2,4,3,5,6,4,4,4]\]

_{Type: OneDimensionalArray PositiveInteger}

vector([1/2,1/3,1/14])

\[[12,13,114]\]

_{Type: Vector Fraction Integer}

"Hello, World"

\[\mathrm{"Hello,World"}\]

_{Type: String}

bits(8,true)

\["11111111"\]

_{Type: Bits}

A vector is similar to a one-dimensional array except that if its components belong to a ring then arithmetic operations are provided.

0.6.5 Flexible Arrays¶

Flexible arrays are designed to provide the efficiency of one-dimensional arrays while retaining the flexibility of lists. They are implemented by allocating a fixed block of storage for the array. If the array needs to be expanded then a larger block of storage is allocated and the contents of the old block are copied into the new one.

There are several operations that can be applied to this type, most of which modify the array in place. As a result these functions all have names ending in !. The physicalLength returns the actual length of the array as stored in memory while the physicalLength! allows this value to be changed by the user.

f : FARRAY INT := new(6,1)

\[[1,1,1,1,1,1]\]