In list.diesel:
Lists are sequences based on a linked-list representation. General
lists support first (a.k.a. car, head) and rest
(a.k.a. cdr, tail) operations, plus all the standard sequence
operations, like length, is_empty
, do, pick_any
, includes,
find, copy, reverse_do
, flatten, ||, etc.
set_first
and set_rest
operations are defined (they produce
run-time errors when invoked on nil). However, simple lists
are not extensible_sequences
because they do not support add in
place. Instead, cons (a.k.a. add_functional
) adds to the front of a
simple list, returning a new list.
m_list
type defines a full-fledged
mutable, extensible list data structure, implemented as a wrapper
around a simple list. m_list
inherits add and remove from
extensible_collection
. For historical reasons, add is defined
to add to the front of the list. m_list
also inherits
{add,remove}_{first,last}
from extensible_sequence
.
(This data structure definition doesn't follow the usual pattern:
add adds to the front of the collection, not to the end; there is no
i_list data type defined and the m_list data type is concrete rather
than abstract.) In the future, it would be really nice to define a
view of doubly-linked lists that treats them as a sequence of link
nodes. Then lots of list splicing operations could be supported that
aren't really supported through the existing generic m_list
interface. E.g. removing an element from a list during an iteration
through it requires two traversals if written in terms of the m_list
interface. Doubly-linked and circular lists might also be useful
data structures.
replace_any
replaces some occurrence of a value in a list
with some other value
replace_all
replaces all occurrences of a value in a list
with some other value, returning the number of replacements made
replace_if
replaces all occurrences of a value in a list that
passes a predicate with some other value computed by a different
function, returning the number of replacements made