List is a sequence of nodes storing data and links to other node. Each node has place for single piece of
data and a single link. First node of the list contains link to second node, second node contains
link to the third node, etc. There is special value representing empty list. Last node of a list
contains this value in as its link. In FriCAS value stored in first node is given by fricas l := [1,
Type: List(PositiveInteger?)fricas first(l)
Type: PositiveInteger?fricas l2 := rest(l)
Type: List(PositiveInteger?)fricas first(l2)
Type: PositiveInteger?fricas l3 := rest(l2)
Type: List(PositiveInteger?)fricas empty?(l3)
Type: Booleanfricas empty?(rest(l3))
Type: Boolean One can use One of most common operations of lists is creating list from sequence of values. One can create
list with given value and given tail by using fricas l := empty()$List(Integer)
Type: List(Integer)fricas l := cons(3,
Type: List(Integer)fricas l := cons(2,
Type: List(Integer)fricas l := cons(1,
Type: List(Integer)Of course, in sequential code square brace notation '[1, 2, 3]?' is much more convenient. But
fricas l := empty()$List(Integer)
Type: List(Integer)fricas for i in 1..10 repeat l := cons(i, Type: Voidfricas l
Type: List(Integer)Note that in both examples elements appear in opposite order to applying 'cons': the last
application of fricas l := reverse!(l)
Type: List(Integer)Note: after calling We frequently need to create new list by applying the same transformation to all elements of list. FriCAS has special notation in this case: fricas l2 := [i^2 for i in l]
Type: List(Integer)Note: instead of Parts of list can be shared: fricas l1 := [1,
Type: List(PositiveInteger?)fricas l2 := cons(10,
Type: List(PositiveInteger?)fricas l3 := cons(20,
Type: List(PositiveInteger?)l2 has on "own" node and other nodes are shared with l1 and l3. Similarly l3 has one "own" node and the other are shared. One can see that nodes are shared by modifying them: fricas setfirst!(l1,
Type: PositiveInteger?fricas l1
Type: List(PositiveInteger?)fricas l2
Type: List(PositiveInteger?)fricas l3
Type: List(PositiveInteger?)Above we used modification on to show sharing. However in general modifying shared structures may give tricky results. So normal practice is to avoid modifying shared lists. In other words we first build list which may use modification (notably reversing list in place), then we use it without further changes. When Spad functions modify lists there is fundamental limitation: at low level lists are represented by pointers and called function has copy of a pointer to the list. So function can modify list elements, but can not change pointer in the caller. In other words, function can shorten a list, but can not change nonempty list to empty list: fricas fun1(l) == empty?(l) => l l := [] l Type: Voidfricas l := [1,
Type: List(PositiveInteger?)fricas fun1(l) fricas Compiling function fun1 with type List(PositiveInteger) -> List( PositiveInteger)
Type: List(PositiveInteger?)fricas l
Type: List(PositiveInteger?)To avoid this limitation usual convention is that caller should use return value of a function: fricas l := reverse!(l)
Type: List(PositiveInteger?)fricas l
Type: List(PositiveInteger?)fricas l := fun1(l)
Type: List(PositiveInteger?)fricas l
Type: List(PositiveInteger?)Note that after modification value of original list may be useless, while return value is OK. For example fricas bb := [3,
Type: List(PositiveInteger?)fricas bs := sort! bb
Type: List(PositiveInteger?)fricas bb
Type: List(PositiveInteger?)fricas bs
Type: List(PositiveInteger?)
If one really wants to change argument there is a trick of prepending dummy element: fricas fun2(l) == t := l t := [] setrest!(l, Type: Voidfricas l := [1,
Type: List(PositiveInteger?)fricas dl := cons(0,
Type: List(Integer)fricas fun2(dl) fricas Compiling function fun2 with type List(Integer) -> List(Integer)
Type: List(Integer)fricas rest(dl)
Type: List(Integer)Note: we need variable |