Последовательности, массивы и векторы

Тип последовательности объединяет два других типа Lisp: списки и массивы. Другими словами, любой список является последовательностью, а любой массив является последовательностью. Общим свойством всех последовательностей является то, что каждая из них представляет собой упорядоченный набор элементов.

Массив — это объект фиксированной длины со слотом для каждого из его элементов. Все элементы доступны за постоянное время. Четыре типа массивов — строки, векторы, таблицы символов и векторы булевых значений.

Список — это последовательность элементов, но он не является единственным примитивным объектом; он состоит из ячеек cons, по одной ячейке на каждый элемент. Для поиска n-го элемента требуется просмотреть n ячеек cons, поэтому элементы, удаленные от начала списка, требуют больше времени для доступа. Но к списку можно добавлять или удалять элементы.

На следующем рисунке показаны взаимосвязи между этими типами:

          _____________________________________________
         |                                             |
         |          Sequence                           |
         |  ______   ________________________________  |
         | |      | |                                | |
         | | List | |             Array              | |
         | |      | |    ________       ________     | |
         | |______| |   |        |     |        |    | |
         |          |   | Vector |     | String |    | |
         |          |   |________|     |________|    | |
         |          |  ____________   _____________  | |
         |          | |            | |             | | |
         |          | | Char-table | | Bool-vector | | |
         |          | |____________| |_____________| | |
         |          |________________________________| |
         |_____________________________________________|