Comments 21
А зачем портировать в функциональный мир именно бинарную кучу? Есть несколько весьма хороших чисто функциональных подходов к организации кучи, например goo.gl/VMgdG2
Отличная статья, спасибо!
Мне остался непонятен один момент: чем чисто функциональные структуры данных отличаются от обычных персистентных структур данных?
Мне остался непонятен один момент: чем чисто функциональные структуры данных отличаются от обычных персистентных структур данных?
Спасибо за фидбек!
По делу. Во-первых, не совсем понятно что имеется ввиду под «обычные персистентные структуры». Не секрет, что ЧФСД можно реализовать и в императивной среде (например на Java), но там они не очень популярны, потому как выглядят чужеродными. Другое дело функциональные языки, где мутации, как правило, физически не-возможны — тут и выбора то большого нет. Во-вторых, эта терминология очень скользкая дорожка. Часто говоря «персистентная структура (persistent)» подразумевают ЧФСД (purely functional) и на оборот. Более того, есть еще одно смежное определение «неизменяемая структура (immutable)», которое часто используется вместо двух предыдущих. Пример. Есть совершенно идентичная реализация чисто-функционального вектора (bit-mapped vector trie) в Scala и Сlosure. В Scala он называется "immutable.Vector", в Closure — "PersistentVector".
По делу. Во-первых, не совсем понятно что имеется ввиду под «обычные персистентные структуры». Не секрет, что ЧФСД можно реализовать и в императивной среде (например на Java), но там они не очень популярны, потому как выглядят чужеродными. Другое дело функциональные языки, где мутации, как правило, физически не-возможны — тут и выбора то большого нет. Во-вторых, эта терминология очень скользкая дорожка. Часто говоря «персистентная структура (persistent)» подразумевают ЧФСД (purely functional) и на оборот. Более того, есть еще одно смежное определение «неизменяемая структура (immutable)», которое часто используется вместо двух предыдущих. Пример. Есть совершенно идентичная реализация чисто-функционального вектора (bit-mapped vector trie) в Scala и Сlosure. В Scala он называется "immutable.Vector", в Closure — "PersistentVector".
Мартин Одерски в своей книге исключительно зовет такие структуры неизменяемыми. Специально указывыет, что они часть функциональной парадигмы, но именно функциональными никогда не называет (как раз из-за того, что в императивных языках они тоже есть). Персистентность отмечена лишь как свойство.
>> не совсем понятно что имеется ввиду под «обычные персистентные структуры».
Ну, например, есть такой класс задач, в котором нужно хранить всю историю изменений объекта. Временами встречал олимпиадные задачки такого рода, да и в реальной жизни аналогичных проблем хватает: скажем, для history viewer или undo/redo tracker. Понятно, что хранить каждую версию объекта отдельно — не очень здорово, поэтому переходим к персистентности. Я писал подобные решения на Java и C#, они вовсе не выглядели чужеродно, всё смотрелось вполне мило.
И в общем случае в персистентной структуре речи об функциональности (как мне кажется) не идёт, можно даже не мыслить в функциональных терминах. Мы просто создаём новые элементы структуры, а старые не затираем. И требования неизменности в общем случае нет: скажем, пишу я history editor, который предусматривает перезапись истории. Меняю какой-нибудь элемент для одного состояния, а получается так, что он меняется для всех состояний — profit. И в таком подходе получаем изменяемость структуры by design. Поэтому, я считаю, нельзя считать персистентные структуры и ЧФСД синонимами.
Понимаю, что с терминологией тут всё сложно, но хотелось бы разобраться, чтобы употреблять правильные термины по месту.
Ну, например, есть такой класс задач, в котором нужно хранить всю историю изменений объекта. Временами встречал олимпиадные задачки такого рода, да и в реальной жизни аналогичных проблем хватает: скажем, для history viewer или undo/redo tracker. Понятно, что хранить каждую версию объекта отдельно — не очень здорово, поэтому переходим к персистентности. Я писал подобные решения на Java и C#, они вовсе не выглядели чужеродно, всё смотрелось вполне мило.
И в общем случае в персистентной структуре речи об функциональности (как мне кажется) не идёт, можно даже не мыслить в функциональных терминах. Мы просто создаём новые элементы структуры, а старые не затираем. И требования неизменности в общем случае нет: скажем, пишу я history editor, который предусматривает перезапись истории. Меняю какой-нибудь элемент для одного состояния, а получается так, что он меняется для всех состояний — profit. И в таком подходе получаем изменяемость структуры by design. Поэтому, я считаю, нельзя считать персистентные структуры и ЧФСД синонимами.
Понимаю, что с терминологией тут всё сложно, но хотелось бы разобраться, чтобы употреблять правильные термины по месту.
Пример с редактором истории странный. Персистентность предполагает, что вместо изменения объекта вы получаете модифицированную копию в довесок к сохранившемуся оригиналу. При редактировании истории вы хотите поменять какой-то элемент объекта (вероятно расшаренный участок памяти, если он не изменялся постоянно), и в этот момент структура должна потерять свою устойчивость.
Ну, всё зависит от структуры. Я не говорил, что такой манёвр всегда и легко реализуется для произвольной структуры, но на уровне подхода к решению абстрактной задачи такую идею рассматривать вполне можно. Просто хотелось привести какой-нибудь максимально простой пример изменяемой персистентной структуры.
Я как раз про то, что в момент изменения всей истории это уже эфемерная структура, так как предыдущих состояний больше нет.
Ну, тут опять возникает вопрос терминологии. Структура как бы эфемерная, но для её построения мы используем персистентный подход. Оригинально структура персистентная (стандартные операции добавления/удаления/модификации элементов идут как персистентные), просто мы навешиваем сверху дополнительную операцию.
Я попробую ответить. Для меня лично, это тоже больное место — эта терминология. В умных книжках, все эти моменты ненавязчиво опускаются (т.к. видимо являются чем-то сверхэлементарным для авторов, не требующим пояснений). Что для нас — перфекционистов — является большим испытанием. Я для себя решил разграничить эти вещи следующим образом:
Персистентность — свойство объекта/структуры позволяющее поддерживать множество его версий (это требование ФП мира). Тогда, персистентная структура — это коллекция, которая позволяет выполнять тот-же набор операций и для своей предыдущей версии. Такие структуры встречаются и в императивных средах, и могут быть построены на изменяемом внутреннем состоянии (с сайд-эффектами).
Неизменяемость — свойство объекта/структуры запрещяющее его любые изменения. Понятно, что неизменяемая структура после модификации представляет собой копию предыдущей версии + конкретные изменения (например новый элемент). При этом, неизменяемые объекты всегда персистентны (т.е. версию которую мы когда-то создали мы не можем изменить/удалить). Такие структуры тоже есть в императивном мире, например java.lang.String (моя любимая коллекция). Неизменяемость — это ограничение функционального мира (т.е. отсутствие деструктивных апдейтов). Может ли неизменяемая структура быть построена на изменяемом внутреннем состоянии? Я думаю да. Есть такое понятие как локализация мутации. Отличный пример такой мутации Паша Павлов рассказывает в этом видео на примере очереди банкиров. Т.е. формально коллекция неизменяемая (по набору элементов), но во внтуренней структуре есть некоторые места, которые подвержены мутациям, т.е. нельзя сказать, что такие структуры всегда без сайд-эффектов.
ЧФСД — это класс структур без сайд-эффектов. Баста.
Персистентность — свойство объекта/структуры позволяющее поддерживать множество его версий (это требование ФП мира). Тогда, персистентная структура — это коллекция, которая позволяет выполнять тот-же набор операций и для своей предыдущей версии. Такие структуры встречаются и в императивных средах, и могут быть построены на изменяемом внутреннем состоянии (с сайд-эффектами).
Неизменяемость — свойство объекта/структуры запрещяющее его любые изменения. Понятно, что неизменяемая структура после модификации представляет собой копию предыдущей версии + конкретные изменения (например новый элемент). При этом, неизменяемые объекты всегда персистентны (т.е. версию которую мы когда-то создали мы не можем изменить/удалить). Такие структуры тоже есть в императивном мире, например java.lang.String (моя любимая коллекция). Неизменяемость — это ограничение функционального мира (т.е. отсутствие деструктивных апдейтов). Может ли неизменяемая структура быть построена на изменяемом внутреннем состоянии? Я думаю да. Есть такое понятие как локализация мутации. Отличный пример такой мутации Паша Павлов рассказывает в этом видео на примере очереди банкиров. Т.е. формально коллекция неизменяемая (по набору элементов), но во внтуренней структуре есть некоторые места, которые подвержены мутациям, т.е. нельзя сказать, что такие структуры всегда без сайд-эффектов.
ЧФСД — это класс структур без сайд-эффектов. Баста.
Внесу свои пять копеек.
Персистентность бывает разной. Различают три вида.
1. Частичная. Можем читать любую версию, но менять только последнюю. Граф версий представляет собой односвязный список.
2. Полная. Можем читать и менять любую версию. Граф версий — это дерево.
3. Конфлюэнтная. Это полная персистентность с возможностью мерджа версий. Граф версий — даг (ориентированный ациклический граф).
ЧФСД гарантирует все три уровня персистентности. С другой стороны, почти любую императивную структуру данных можно превратить в частичную или полную с амортизационно константным ухудшением по памяти и времени. Правда, она не будет ЧФСД.
Персистентность бывает разной. Различают три вида.
1. Частичная. Можем читать любую версию, но менять только последнюю. Граф версий представляет собой односвязный список.
2. Полная. Можем читать и менять любую версию. Граф версий — это дерево.
3. Конфлюэнтная. Это полная персистентность с возможностью мерджа версий. Граф версий — даг (ориентированный ациклический граф).
ЧФСД гарантирует все три уровня персистентности. С другой стороны, почти любую императивную структуру данных можно превратить в частичную или полную с амортизационно константным ухудшением по памяти и времени. Правда, она не будет ЧФСД.
В первую очередь — отсутствием сайд-эффектов от операций над ними.
Про асимптотическую сложность интересен комментарий от Gaperton:
…
2) Это важно по той причине, что существуют алгоритмы, которые, будучи записаны в функциональном стиле, поимеют добавочный log(N) в своей асимптотике (и никакие фокусы вроде монад и уникалных типов не помогут). И по другому никак. Depth-first graph traversal — пример такого алгоритма (O(N) императивный, О(N)log(N) ффункциональный). А испорченная асимптотика во многих случаях гораздо хуже плохой кодогенерации.
…
Программист на OCaml здесь выкрутится, выделив в алгоритме небольшую императивную часть и избавившись от log(N). А вот программистам на Clean и Haskell придется хуже — в тяжелом случае придется выносить часть алгоритма в С++. Что, впрочем, не фокус — прямо скажем. Вставки на ассемблере в программу на С лет десять назад никого не пугали, надо заметить.
И это еще не все. В функциональном коде применяются доволно специфические структуры данных, имеющие, с одной стороны, большуу константу при О для основных операций, но с другой стороны, аллокаторы этих языков заточенны под элементы таких структур данных. Так что впрямую сравнивать производительность программ нельзя — в случае ФЯ выбирается другая структура данных, а значит, будет отличаться и алгоритм. Естественно — в медленную сторону. Т.е либо будет больше константа в алгоритме, либо до кучи все еще и умножится на log(N).
Хочу добавить, что Геогий Бронников (переводчик SICP) готовит перевод книги Окасаки на русский, причём каждый может ему в этом помочь, т.к. книга выложена на GitHub.
эм, а кто следит за версионностью структуры? как удаляются старые версии? По празнаку отсуствия ссылок на объект?
Все эти стеки, очереди, кучи, деревья, графы (будь они не ладны) и прочие “остроумные” названия непонятных и сложных структур данных ни как не хотели закрепляться в моей головеНу вот к названиям ленивые студенты ещё не прикапывались.
Sign up to leave a comment.
Чисто функциональные структуры данных