неужели нет какого-то пакета container-transient чтобы такие штуки делать

в смысле делать через мутабельные структуры что-то?

Ну да) Я на сисярпе писал кайний раз лет 3-5 назад

да

ST + vector + vector-algorithms

Вообще иногда такое хочется

А ещё я хочу аллокацию в компактах!!!

Хочешь ответить на http запрос - аллоцировался компакт, далее все аллокации в треде в нём, там 32К хватит на большинство вычислений, потом ответил всё и забыл

а если не хватит?

То или в обычном хипе или следующий чанк

контейнер-транзиент на хаскеле не то что не написать, но надо городить хак на хак, потому что нету мутабельных полей же. кметт начинал такой делать, но доделал и выложил на хекедж только пакет для хачения мутабельных полей.
ну т.е. кому-то надо это все писать, сортировку для массива вон за 20 лет написали. для списка-то нормальный мердж сорт написли не задолго до того, лет 15 назад, а там 8 строк или около того

Т.е. проблема в мутабельных полях тока

А какие там пропоузалы? Там ST можно будет вставить?

да, но этот пропозал заглох

список через массив-то отсортировать щас уже можно, речь про мутирование узлов в дереве

Ну мне кажется, если насортировать массив в хорошем порядке и по нему строить готовую структуру то будет ок, или нет?

Кажется, что можно построить оптимальный Map за O(n) по сортированному массиву известной длины, без мутаций во время построения

ну транзиенты не только для этого нужны же

а так-то да, из сортированного списка мап строится быстрее берем вектор/примитив сортируем, через список подаем на вход построителю дерева, построитель дерева сфьюзивается с читателем массива

всего три пакета использовали и дерево готово