Кстати, есть в чисто функциональных языках понятие вектора? Честного вектора, который хранит данные в памяти последовательно?

Обычно связанные списки используют, чтобы добавлять эл-ы в коллекцию не инвалидируя итераторы/указатели. Ну и в сишке ещё вместо динамических массивов их любят использовать.

Это простейшая коллекция, на ней легко показывать пример того, как примерно такие вещи работают.

Смотря насколько ты хочешь его персистетным. И насколько жестко ты понимаешь слово "последовательно"

Если не персистетный, то обычный иммутебльный массив, который копируется целиком

Если персистетный - то смотри персистетный вектор. Это очень широкое дерево, где в узлах хранятся небольшие массивы.

При изменении элемента в этом массиве, только он небольшой и копируется, остальные ветки не меняются при этом

Ну получается что на Расте это не особо нужно потому что слишком сложно реализовывать руками, а в языках с GC это приводит к неэффективной работе с памятью. В итоге удобно и эффективно это только в Хаскеле и может еще какие-то чистые ФП языки.

На расте это скорее не нужно, потому что пока никто не сделал нормальную поддержку кастомных аллокаторов для конкретных типов.

Такие коллекции вполне эффективны, если они работают с аллокатором как в гц языках

В любом случае респект за подробное разъяснение, день прошел не зря

Ну на расте я фиговую реализацию привел, потому что её сложно сделать, из-за отсутствия гц.
Вариант чуть получше вот такой,  но он всё равно не идеальный.

struct ConsStruct<A> { head: A, tail: List<A> }

enum List<A> {
    Nil, Cons(Arc<ConsStruct<A>>)
}

impl<A> Clone for List<A> {
    fn clone(&self) -> Self {
        match self {
            List::Nil => List::Nil,
            Cons(arc) => Cons(arc.clone()),
        }
    }
}

impl <A> List<A> {
    fn append(&self, head: A) -> Self {
        let tail = self.clone();
        Cons(Arc::new(ConsStruct { head, tail }))
    }
}

Тут лучше заметно, что клонировнаие списка - дико дешево и не требует клонирования от его элементов

Но из-за этого всё хранится в куче, что для гц языка - более менее нормально, а для раста это плохо, если пользоваться системным аллокатором

Т.к. он на такие трюки не рассчитан

Т.е. такой иммутабельный список реально имеет достаточно сомнительную пользу как структура данных.

А вот подобным образом построенные иммутабельные деревья поиска и вектора - они на самом деле неплохи

Их можно без вопросов передавать между потоками и т.д. и т.п.

Производительность у них более-менее и при этом дешевое клонирование сохраняется

А вот такой список в хаскеле используется чуть для другого:

Он там вместо итератора за счёт ленивости языка. Т.к. когда ты делаешь Cons там, то из-за ленивости там реально будет что-то вроде:

Cons(Lazy(head), Lazy(tail)), где, что head, что tail будут высчитаны, только при явном их использовании.

Отсюда у них есть набор хороших свойств, который позволяет переписывать операции со списками так, что в реальности создаваться они тупо не будут.

Т.е. большинство библиотченых операций с ними в хаскеле выражены через unfold и fold таких списков, и при этом можно пользоваться тем, что fold от unfold можно вычислить без создания списка, чем и пользуется стандартная библиотека через специально описанные rewrite rules для компилятора.

И вот этот трюк как раз только в хаскеле и доступен, потому что без ленивости и чистоты - вот это сворачивание операций fold и unfold не всегда корректно

Не только в хаскелле

Поэтому ленивые, иммутабельные списки - вне хаскеля очень условно актуальны.

А вот все остальные персистетные структуры данных вполне можно использовать, они везде норм.