Lists

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.

extend module Stdlib;

module List;
abstract class list[T] isa sequence[T],
                                  - type parameter is covariant:
                                  list[`S >= T];
abstract class list_exactly[T] isa sequence_exactly[T], list[T];
  fun rest(:list[`T]):list[T];
predicate empty_list[T] isa list[T], empty_collection[T];
predicate non_empty_list[T] isa list[T], non_empty_collection[T];

Simple lists are mutable Lisp-style singly-linked lists with two representations, nil and cons. Method cons creates a new cons cell; object nil[T] can be used directly. Simple lists are mutable, in the sense that 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.

abstract class simple_list[T] isa list_exactly[T],
                                         functionally_extensible_collection[T];
  fun set_rest(:simple_list[`T], :simple_list[T]):void;
  fun append(l1:simple_list[`T], l2:simple_list[T]):simple_list[T];
object nil[T] isa simple_list[T];
class cons[T] isa simple_list[T];
  fun cons(hd:T, tl:simple_list[`T]):cons[T];

To correct this problem, the 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.

class m_list[T] isa list_exactly[T], extensible_sequence[T];
extend class m_list[`T <= comparable[T]] isa removable_collection[T];
  fun remove_and_return_one(l:m_list[`T], test:&(T):bool,
                                   if_absent:&():`Else):T|Else;
  fun splice_onto_end(l1:m_list[`T], l2:m_list[T]):m_list[T];

replace_any replaces some occurrence of a value in a list with some other value

  fun replace_any(l:m_list[`T <= comparable[T]],
                         old_value:T, new_value:T):void;
  fun replace_any(l:m_list[`T <= comparable[T]],
                         old_value:T, new_value:T,
                         if_absent:&():void):void;

replace_all replaces all occurrences of a value in a list with some other value, returning the number of replacements made

  fun replace_all(l:m_list[`T], old_value:T, new_value:T):int
          where signature =(:T,:T):bool;

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

  fun replace_if(l:m_list[`T],
                        pred:&(T):bool, new_value_cl:&(T):T):int;
  fun new_m_list[T]():m_list[T];

end module List;