Больше информации о списке cons
Список cons - это структура данных, которая произошла от языка программирования Lisp и его диалектов, состоит из вложенных пар и представляет собой версию связанного списка в Lisp. Его название происходит от функции cons (сокращение от construct function - конструктора) в Lisp, которая создает новую пару из двух своих аргументов. Вызовом cons для пары, состоящей из значения и другой пары, мы можем создать списки cons, состоящие из рекурсивных пар.
Например, вот псевдокодовое представление списка cons, содержащего список 1, 2, 3, с каждой парой в скобках:
(1, (2, (3, Nil)))
Каждый элемент в списке cons содержит два элемента: значение текущего элемента и следующий элемент. Последний элемент в списке содержит только значение, называемое Nil, без следующего элемента. Список cons создается путем рекурсивного вызова функции cons. Каноническое имя для обозначения базового случая рекурсии - это Nil. Обратите внимание, что это не то же самое, что "null" или "nil" из главы 6, которое представляет собой недопустимое или отсутствующее значение.
Список cons не является часто используемой структурой данных в Rust. Большинство времени, когда у вас есть список элементов в Rust, Vec<T> - это лучше выбор для использования. Другие, более сложные рекурсивные типы данных имеют значение в различных ситуациях, но, начиная с списка cons в этой главе, мы можем изучить, как коробки позволяют нам определить рекурсивный тип данных без большого отвлечения.
Листинг 15-2 содержит определение перечисления для списка cons. Обратите внимание, что этот код еще не скомпилируется, потому что тип List не имеет известного размера, что мы покажем.
Имя файла: src/main.rs
enum List {
Cons(i32, List),
Nil,
}
Листинг 15-2: Первая попытка определить перечисление для представления структуры данных списка cons из значений i32
Примечание: Мы реализуем список cons, который хранит только значения i32, для целей этого примера. Мы могли бы реализовать его с использованием обобщений, как мы обсуждали в главе 10, чтобы определить тип списка cons, который может хранить значения любого типа.
Использование типа List для хранения списка 1, 2, 3 будет выглядеть как код в Листинге 15-3.
Имя файла: src/main.rs
--snip--
use crate::List::{Cons, Nil};
fn main() {
let list = Cons(1, Cons(2, Cons(3, Nil)));
}
Листинг 15-3: Использование перечисления List для хранения списка 1, 2, 3
Первое значение Cons содержит 1 и еще одно значение List. Это значение List - это еще одно значение Cons, которое содержит 2 и еще одно значение List. Это значение List - это еще одно значение Cons, которое содержит 3 и значение List, которое в конце концов является Nil, нерекурсивной вариантом, который сигнализирует о конце списка.
Если мы попытаемся скомпилировать код в Листинге 15-3, мы получим ошибку, показанную в Листинге 15-4.
error[E0072]: recursive type `List` has infinite size
--> src/main.rs:1:1
|
1 | enum List {
| ^^^^^^^^^ recursive type has infinite size
2 | Cons(i32, List),
| ---- recursive without indirection
|
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to make `List`
representable
|
2 | Cons(i32, Box<List>),
| ++++ +
Листинг 15-4: Ошибка, которую мы получаем, пытаясь определить рекурсивное перечисление
Ошибка показывает, что этот тип "имеет бесконечный размер". Причина в том, что мы определили List с вариантом, который является рекурсивным: он содержит непосредственно еще одно значение самого себя. В результате Rust не может понять, сколько места ему нужно для хранения значения List. Разберём, почему мы получаем эту ошибку. Сначала мы рассмотрим, как Rust определяет, сколько места ему нужно для хранения значения нерекурсивного типа.
