Edit detail for ListProgramming revision 1 of 5

changed:
-
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 'first',
link is obtained using 'rest'.  We test if list is empty using 'empty?' and create empty list
using 'empty' or '[]'.  We can write lists in source by surronding them with square brackets.
Simple manipulation on list may look like:
\begin{axiom}
l := [1, 2, 3]
first(l)
l2 := rest(l)
first(l2)
l3 := rest(l2)
empty?(l3)
empty?(rest(l3))
\end{axiom}


  One can use 'elt' to access value in arbitrary node effectively using
list as an array.  But usually this is inefficient, because such access to N-th node has to
traverse all preceding nodes, giving O(N) operation.  Note: some languages do not have true lists,
they use arrays but call them lists.  Array access is constant cost operation, use them if
you need quick access to an arbitrary elements and do not need flexibility given by lists.

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 'cons'.  Several applications of 'cons' can create
any (proper) list.  For example:
\begin{axiom}
l := empty()$List(Integer)
l := cons(3, l)
l := cons(2, l)
l := cons(1, l)
\end{axiom}

Of course, in sequential code square brace notation '[1, 2, 3]' is much more convenient.  But
'cons' can be used in loops:
\begin{axiom}
l := empty()$List(Integer)
for i in 1..10 repeat l := cons(i, l)
l
\end{axiom}

Note that in both examples elements appear in opposite order to applying 'cons': the last
application of 'cons' creates first node of new list.  We could correct this problem
by using 'concat', but that is potentially inefficient since 'concat' has to copy the
whole list leading to quadratic algorithm ('concat!' avoids copy but still using it
is quadratic due to need to traverse preceding nodes).  Instead, the standard idiom
is to reverse the list after constriction.  In normal case after construction the
freshly build list in reverse order is no longer needed, so we can use 'reverse!'
which reuses nodes to make reversal faster:

\begin{axiom}
l := reverse!(l)
\end{axiom}

Note: after calling 'reverse!' old value stored in 'l' is no longer useful, we have
to use value returned by 'reverse!'.

We frequently need to create new list by applying the same transformation to all
elements of list.  FriCAS has special notation in this case:
\begin{axiom}
l2 := [i^2 for i in l]
\end{axiom}

Note: instead of 'i^2' we can use more complicated expression and we can replace 'for' part by other
FriCAS loop controls.  For more details see FriCAS book, chapter 5.4 "Loops" and 5.5 "Creating lists
and streams with iterators"").  Here we just note that this lead to very efficient code
(slightly more efficient that construction in reverse order followed by reversal).

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 first, link is obtained using rest. We test if list is empty using empty? and create empty list using empty or '[]'. We can write lists in source by surronding them with square brackets. Simple manipulation on list may look like:

fricas

l := [1, 2, 3]

(1)

Type: List(PositiveInteger?)

fricas

first(l)

(2)

Type: PositiveInteger?

fricas

l2 := rest(l)

(3)

Type: List(PositiveInteger?)

fricas

first(l2)

(4)

Type: PositiveInteger?

fricas

l3 := rest(l2)

(5)

Type: List(PositiveInteger?)

fricas

empty?(l3)

(6)

Type: Boolean

fricas

empty?(rest(l3))

(7)

Type: Boolean

One can use elt to access value in arbitrary node effectively using list as an array. But usually this is inefficient, because such access to N-th node has to traverse all preceding nodes, giving O(N) operation. Note: some languages do not have true lists, they use arrays but call them lists. Array access is constant cost operation, use them if you need quick access to an arbitrary elements and do not need flexibility given by lists.

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 cons. Several applications of cons can create any (proper) list. For example:

fricas

l := empty()$List(Integer)

(8)

Type: List(Integer)

fricas

l := cons(3, l)

(9)

Type: List(Integer)

fricas

l := cons(2, l)

(10)

Type: List(Integer)

fricas

l := cons(1, l)

(11)

Type: List(Integer)

Of course, in sequential code square brace notation '[1, 2, 3]?' is much more convenient. But cons can be used in loops:

fricas

l := empty()$List(Integer)

(12)

Type: List(Integer)

fricas

for i in 1..10 repeat l := cons(i, l)

Type: Void

fricas

l

(13)

Type: List(Integer)

Note that in both examples elements appear in opposite order to applying 'cons': the last application of cons creates first node of new list. We could correct this problem by using concat, but that is potentially inefficient since concat has to copy the whole list leading to quadratic algorithm (concat! avoids copy but still using it is quadratic due to need to traverse preceding nodes). Instead, the standard idiom is to reverse the list after constriction. In normal case after construction the freshly build list in reverse order is no longer needed, so we can use reverse! which reuses nodes to make reversal faster:

fricas

l := reverse!(l)

(14)

Type: List(Integer)

Note: after calling reverse! old value stored in l is no longer useful, we have to use value returned by reverse!.

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]

(15)

Type: List(Integer)

Note: instead of i^2 we can use more complicated expression and we can replace for part by other FriCAS? loop controls. For more details see FriCAS? book, chapter 5.4 "Loops" and 5.5 "Creating lists and streams with iterators""). Here we just note that this lead to very efficient code (slightly more efficient that construction in reverse order followed by reversal).