Функциональщина, односвязные списки: обратный обход (3 стр)

ffinder
> например дано: ListNum
> надо получить: ListEven и ListOdd, данные должны быть в прямом порядке (не в перевернутом).
> зачем что-то изменять? просто читаем поэлементно начиная с конца, не генерируя перевернутый список.

Immutable односвязный список на физическом уровне устроен как куча больших деревьев. Листья этих деревьев являются началами разных версий этого списка. Следующий элемент произвольной версии списка – это родитель её вершины в дереве. Корень любого дерева, таким образом, является последним элементом всех версий списка, начала которых являются листьями этого дерева.

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

Мне не известно как можно было бы реализовать двусвязный immutable список, в котором все стандартные операции работали бы за O(1). (Хотя я не много об этом знаю.)

id-alex
о! уже конкретика поперла.
можешь дать линки где ты эти хитрости вычитал? и про который из языков речь ведешь?

ffinder

Я не берусь утверждать, что CRT каких-то функциональных языков устроены именно так.
Я просто знаю про структуру данных „immutable список“. Нагуглил несколько ссылок по теме:
CodeProject с картинками
Wikipedia:en про «Singly-linked linear lists vs. other lists»
Что такое «Persistent data structure»

id-alex, спасибо за статьи. Многое прояснилось.

Я опичален, у языков c persistant (оно же immutable) структурами данных похоже нет никаких шансов догнать императивные с mutable. Overhead огромный, а практическая польза от него сомнительна. ИМХО, подход тупиковый. Никого не хотел обидеть, peace.

ffinder
> Я опичален, у языков c persistant (оно же immutable) структурами данных похоже
> нет никаких шансов догнать императивные с mutable. Overhead огромный, а
> практическая польза от него сомнительна. ИМХО, подход тупиковый. Никого не
> хотел обидеть, peace.

Неизменяемые структуры данных можно использовать для СУБД, например http://couchdb.apache.org/docs/overview.html

Из исследовательской работы (Zipper-based File System, http://okmij.org/ftp/Computation/Continuations.html#zipper-fs):

> we offer: transactional semantics; undo of any file and directory operation; snapshots; statically guaranteed the strongest, repeatable read, isolation mode for clients; pervasive copy-on-write for files and directories; built-in traversal facility; and just the right behavior for cyclic directory references

Еще говорят о том, что проблемы с параллельным программированием прямо-таки исчезают. См. Haskell (обзорная страничка: http://www.haskell.org/haskellwiki/Applications_and_libraries/Con… d_parallelism) и Erlang.

innuendo
> разве нет в Haskell reverse для односвязных списков ?
Там основной языковой список односвязный.

DROnik
> Потому что они самые простые и быстрые
и их просто сделать потокобезопасными без блокировок. Полезность этих типов списков недооценивают и иногда просто не включают в стандартные либы, в .net пришлось писать свою реализацию. 10 строк, но всеравно не приятно)

ffinder
> Это вообще нормально? Как с этим люди живут в реальных условиях?
[green]
Они и не живут. Это ж разве жизнь?
Функциональщики - это своего рода нежить в мире программирования.
[/green]

Sbtrn. Devil
> Функциональщики - это своего рода нежить в мире программирования.
Покормлю.
А кто ж тогда эти, как их, жаболюбы, с их публичными неподвижными одинокими фабриками фасолин "Завод"?

А шо в этих односвязных списках такого?
Я вот использую двумерные 4х-связные в проекте, мне кажется, в них больше потенциала.

TarasB
Граф, Тарас? Граф типа матрица? Связи: вверх, вниз, влево, вправо?

Sbtrn. Devil
> Они и не живут. Это ж разве жизнь?
Они затесываются в команды имперасов ... импетарасов ... императистов и плодят нечитаемый функциональный код в языках для этого не предназначенных. Их потуги выглядят весьма милыми. Особенно написание своей функциональной библиотеки. Вот у нас один такой пишет свою библиотеку акторов. Видимо Эрланга начитался.

kvakvs
> А кто ж тогда эти, как их ... жаболюбы
Зомби. Лидируют на рынке, заполняют всё пространство, очень раздуваются от мутаций от гордости.

Sbtrn. Devil
> Функциональщики - это своего рода нежить в мире программирования.
Куда хуже — люди, которые о функциональщине слышали только краем уха в своих страшных снах. Так скажешь случайно "лямбда", "замыкание", "свёртка"... и тут видишь яркую вспышку света и огненный гриб — сразу понятно, у человека бомбануло.

NightmareZ
> Куда хуже — люди, которые о функциональщине слышали только краем уха в своих
> страшных снах.

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

=A=L=X=
> функциональных языках
На минимум 10, не забывай.