скажите это эликсилиристам

В эрланге, кажется, нет настолько же удобного и простого механизма для создания честных мутабельных структур данных (да он, вроде, и не нужен никому особо)

ну я тикет запилил, посмотрим https://bugs.erlang.org/browse/ERL-1416

Там суть вообще не в ленивости, а в том, что хаскель предоставляет достаточно удобную и несложную в использовании обёртку над нативными указателями

Да суть в том, что двусвязный список не нужен. Я всё ещё не понимаю зачем

@loguntsov говорит: "двусвязный список", а уточняет "хочу по ссылке доступ", и ещё добавляет: "для LRU кэша"

Это разве не бред?

что значит "не нужен" ?

вообще не нужен?

я вот думаю, кто из нас двоих на вентилятор накидывает

То и значит, двусвязный список отличается от односвязного тем, что по нему оптимально проходиться не только с головы, но и с хвоста некоторой функцией (назову её reduce(head, acc) -> acc) и можно добавлять элемент в конец за O(1)

Чтобы добавлять элемент в конец за O(1), можно использовать queue или персистентный дэк (у Окасаки можно подсмотреть)

Чтобы не проходить список с хвоста, можно сделать кучу вещей, например

* Считать значение аккумулятора при добавлении элемента

* Вместо нескольких фолда для одного и того же дэка, использовать не более двух: один с головы, другой с конца. Тогда они оба будут работать без разворота.

Ну и наконец использовать ets, доступ за O(log N) не такой уж и долгий, учитывая что разброс скорости доступа в зависимости от уровня кэша будет больше чем оверхэд от прыжков по дереву

Доступ к элементу по ссылке в определение двусвязного списка не входит

итераторы не входят в определение структур данных, это отдельная абстрация. и какова сложность insert_befor в односвязном списке?

Что делает insert_before ?

List1 = lists:insert_befor(Iterator, List, a)

List = [1, 2, 3], Iterator = 2, List1 = [1, a, 2, 3]

Ну тут O(N)

упс

Так, а в двусвязном списке всё равно O(N)

чо это?

извиняюсь, что влезаю. а элементы какого типа?

ну строго говоря если учесть реализацию с неизменямостью - профита не будет. но ты же утверждаешь "вообще"