# UnaryRecursiveAggregate S¶

aggcat.spad line 1293 [edit on github]

S: Type

A unary-recursive aggregate is an aggregate where nodes may have either 0 or 1 children. This aggregate models, though not precisely, a linked list possibly with a single cycle. A node with one children models a non-empty list, with the value of the list designating the head, or first, of the list, and the child designating the tail, or rest, of the list. Since these aggregates are recursive aggregates, they may be cyclic.

- #: % -> NonNegativeInteger if % has finiteAggregate
from Aggregate

- =: (%, %) -> Boolean if S has SetCategory or % has finiteAggregate and S has BasicType
from BasicType

- ~=: (%, %) -> Boolean if S has SetCategory or % has finiteAggregate and S has BasicType
from BasicType

- any?: (S -> Boolean, %) -> Boolean if % has finiteAggregate
from HomogeneousAggregate S

- child?: (%, %) -> Boolean if S has BasicType
from RecursiveAggregate S

- children: % -> List %
from RecursiveAggregate S

- coerce: % -> OutputForm if S has CoercibleTo OutputForm
from CoercibleTo OutputForm

- concat!: (%, %) -> % if % has shallowlyMutable
`concat!(u, v)`

destructively concatenates`v`

to the end of`u`

.

- concat!: (%, S) -> % if % has shallowlyMutable
`concat!(u, x)`

destructively adds element`x`

to the end of`u`

. Note:`concat!(a, x) = concat!(a, [x])`

.

- concat!: List % -> % if % has shallowlyMutable
`concat!(lu)`

, where`lu`

is a list of aggregates`[a, b, ..., c]`

, returns a single aggregate consisting of the elements of`a`

followed by those of`b`

followed … by the elements of`c`

. This function may destructively modify the aggregates in`lu`

.

- concat: (%, %) -> %
`concat(u, v)`

returns an aggregate`w`

consisting of the elements of`u`

followed by the elements of`v`

. Note:`v = rest(w, \#u)`

.

- concat: (S, %) -> %
`concat(x, u)`

returns aggregate consisting of`x`

followed by the elements of`u`

. Note: if`v = concat(x, u)`

then`x = first v`

and`u = rest v`

.

- count: (S -> Boolean, %) -> NonNegativeInteger if % has finiteAggregate
from HomogeneousAggregate S

- count: (S, %) -> NonNegativeInteger if % has finiteAggregate and S has BasicType
from HomogeneousAggregate S

- cycleEntry: % -> %
`cycleEntry(u)`

returns the head of a top-level cycle contained in aggregate`u`

, or`empty()`

if none exists.

- cycleLength: % -> NonNegativeInteger
`cycleLength(u)`

returns the length of a top-level cycle contained in aggregate`u`

, or 0 if`u`

has no such cycle.

- cycleSplit!: % -> % if % has shallowlyMutable
`cycleSplit!(u)`

splits the aggregate by dropping off the cycle. The value returned is the cycle entry, or empty() if none exists. For example, if`w = concat(u, v)`

is the cyclic list where`v`

is the head of the cycle,`cycleSplit!(w)`

will drop`v`

off`w`

thus destructively changing`w`

to`u`

, and returning`v`

.

- cycleTail: % -> %
`cycleTail(u)`

returns the last node in the cycle, or empty() if none exists.

- cyclic?: % -> Boolean
from RecursiveAggregate S

- distance: (%, %) -> Integer
from RecursiveAggregate S

- elt: (%, first) -> S
`elt(u, "first")`

(also written:`u.first`

) is equivalent to first(`u`

).

- elt: (%, last) -> S
`elt(u, "last")`

(also written:`u.last`

) is equivalent to last(`u`

).

- elt: (%, rest) -> %
`elt(\%, "rest")`

(also written:`u.rest`

) is equivalent to`rest u`

.- elt: (%, value) -> S
from RecursiveAggregate S

- eval: (%, Equation S) -> % if S has SetCategory and S has Evalable S
from Evalable S

- eval: (%, List Equation S) -> % if S has SetCategory and S has Evalable S
from Evalable S

- eval: (%, List S, List S) -> % if S has SetCategory and S has Evalable S
from InnerEvalable(S, S)

- eval: (%, S, S) -> % if S has SetCategory and S has Evalable S
from InnerEvalable(S, S)

- every?: (S -> Boolean, %) -> Boolean if % has finiteAggregate
from HomogeneousAggregate S

- first: % -> S
`first(u)`

returns the first element of`u`

(equivalently, the value at the current node).

- first: (%, NonNegativeInteger) -> %
`first(u, n)`

returns a copy of the first`n`

elements of`u`

.

- hash: % -> SingleInteger if S has SetCategory
from SetCategory

- hashUpdate!: (HashState, %) -> HashState if S has SetCategory
from SetCategory

- last: % -> S
`last(u)`

returns the last element of`u`

. Note: for lists,`last(u) = u.(maxIndex u)`

.

- last: (%, NonNegativeInteger) -> %
`last(u, n)`

returns a copy of the last`n`

nodes of`u`

. Note:`last(u, n)`

is a list of`n`

elements.

- latex: % -> String if S has SetCategory
from SetCategory

- leaf?: % -> Boolean
from RecursiveAggregate S

- leaves: % -> List S
from RecursiveAggregate S

- less?: (%, NonNegativeInteger) -> Boolean
from Aggregate

- map!: (S -> S, %) -> % if % has shallowlyMutable
from HomogeneousAggregate S

- map: (S -> S, %) -> %
from HomogeneousAggregate S

- max: % -> S if S has OrderedSet and % has finiteAggregate
from HomogeneousAggregate S

- max: ((S, S) -> Boolean, %) -> S if % has finiteAggregate
from HomogeneousAggregate S

- member?: (S, %) -> Boolean if % has finiteAggregate and S has BasicType
from HomogeneousAggregate S

- members: % -> List S if % has finiteAggregate
from HomogeneousAggregate S

- min: % -> S if S has OrderedSet and % has finiteAggregate
from HomogeneousAggregate S

- more?: (%, NonNegativeInteger) -> Boolean
from Aggregate

- node?: (%, %) -> Boolean if S has BasicType
from RecursiveAggregate S

- nodes: % -> List %
from RecursiveAggregate S

- parts: % -> List S if % has finiteAggregate
from HomogeneousAggregate S

- qsetfirst!: (%, S) -> S if % has shallowlyMutable
`qsetfirst!(u, x)`

destructively changes the first element of`u`

to`x`

without checking for errors.

- qsetrest!: (%, %) -> % if % has shallowlyMutable
`qsetrest!(u, v)`

destructively changes the rest of`u`

to`v`

without checking for errors.

- rest: % -> %
`rest(u)`

returns an aggregate consisting of all but the first element of`u`

(equivalently, the next node of`u`

).

- rest: (%, NonNegativeInteger) -> %
`rest(u, n)`

returns the`n`

th node of`u`

. Note:`rest(u, 0) = u`

.

- second: % -> S
`second(u)`

returns the second element of`u`

. Note:`second(u) = first(rest(u))`

.

- setchildren!: (%, List %) -> % if % has shallowlyMutable
from RecursiveAggregate S

- setelt!: (%, first, S) -> S if % has shallowlyMutable
`setelt!(u, "first", x)`

(also written:`u.first := x`

) is equivalent to`setfirst!(u, x)`

.

- setelt!: (%, last, S) -> S if % has shallowlyMutable
`setelt!(u, "last", x)`

(also written:`u.last := x`

) is equivalent to`setlast!(u, x)`

.

- setelt!: (%, rest, %) -> % if % has shallowlyMutable
`setelt!(u, "rest", v)`

(also written:`u.rest := v`

) is equivalent to`setrest!(u, v)`

.- setelt!: (%, value, S) -> S if % has shallowlyMutable
from RecursiveAggregate S

- setfirst!: (%, S) -> S if % has shallowlyMutable
`setfirst!(u, x)`

destructively changes the first element of`u`

to`x`

. Error if`u`

is empty.

- setlast!: (%, S) -> S if % has shallowlyMutable
`setlast!(u, x)`

destructively changes the last element of`u`

to`x`

. Error if`u`

is empty.

- setrest!: (%, %) -> % if % has shallowlyMutable
`setrest!(u, v)`

destructively changes the rest of`u`

to`v`

. Error if`u`

is empty.

- setvalue!: (%, S) -> S if % has shallowlyMutable
from RecursiveAggregate S

- size?: (%, NonNegativeInteger) -> Boolean
from Aggregate

- split!: (%, NonNegativeInteger) -> % if % has shallowlyMutable
`split!(u, n)`

splits`u`

into two aggregates:`v = rest(u, n)`

and`w = first(u, n)`

, returning`v`

and setting`u`

to`w`

. If`n`

is 0, split! currently only works for Stream and gives error for List. Note: afterwards`rest(u, n)`

returns`empty()`

.

- tail: % -> %
`tail(u)`

returns the last node of`u`

. Error if`u`

is empty.

- third: % -> S
`third(u)`

returns the third element of`u`

. Note:`third(u) = first(rest(rest(u)))`

.

- value: % -> S
from RecursiveAggregate S

BasicType if S has SetCategory or % has finiteAggregate and S has BasicType

CoercibleTo OutputForm if S has CoercibleTo OutputForm

Evalable S if S has SetCategory and S has Evalable S

InnerEvalable(S, S) if S has SetCategory and S has Evalable S

SetCategory if S has SetCategory