# UnaryRecursiveAggregate SΒΆ

- 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. A node with no child then designates the empty list. Since these aggregates are recursive aggregates, they may be cyclic.

- #: % -> NonNegativeInteger if % has finiteAggregate
- from Aggregate
- =: (%, %) -> Boolean if S has SetCategory or S has BasicType and % has finiteAggregate
- from BasicType
- ~=: (%, %) -> Boolean if S has SetCategory or S has BasicType and % has finiteAggregate
- 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: (%, %) -> %
`concat(u, v)`

returns an aggregate`w`

consisting of the elements of`u`

followed by the elements of`v`

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

.

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

.- copy: % -> %
- from Aggregate
- count: (S -> Boolean, %) -> NonNegativeInteger if % has finiteAggregate
- from HomogeneousAggregate S
- count: (S, %) -> NonNegativeInteger if S has BasicType and % has finiteAggregate
- 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
- empty: () -> %
- from Aggregate
- empty?: % -> Boolean
- from Aggregate
- eq?: (%, %) -> Boolean
- from Aggregate
- eval: (%, Equation S) -> % if S has Evalable S and S has SetCategory
- from Evalable S
- eval: (%, List Equation S) -> % if S has Evalable S and S has SetCategory
- from Evalable S
- eval: (%, List S, List S) -> % if S has Evalable S and S has SetCategory
- from InnerEvalable(S, S)
- eval: (%, S, S) -> % if S has Evalable S and S has SetCategory
- 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`

(`n >= 0`

) 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) = u.(\# u - 1)`

.

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

returns a copy of the last`n`

(`n >= 0`

) 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
- member?: (S, %) -> Boolean if S has BasicType and % has finiteAggregate
- from HomogeneousAggregate S
- members: % -> List S if % 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 (`n`

`>=`

0) node of`u`

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

.- sample: %
- from Aggregate

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

. Note: if`u`

is`shallowlyMutable`

,`setrest(tail(u), v) = concat(u, v)`

.

- 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 S has BasicType and % has finiteAggregate

CoercibleTo OutputForm if S has CoercibleTo OutputForm

Evalable S if S has Evalable S and S has SetCategory

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

SetCategory if S has SetCategory