Чисто функциональная мягкая куча - PullRequest
16 голосов
/ 04 августа 2010

Существуют ли реализации чисто функциональной мягкой кучи структуры данных на любом языке?

Ответы [ 3 ]

20 голосов
/ 04 августа 2010

Быстрый поиск в цифровой библиотеке ACM показывает, что структура мягкой кучи Чазелле, несмотря на то, что она очень интересна, получила сравнительно мало исследований, и поэтому постоянные / функциональные мягкие кучи являются открытой темой исследования.

Так что я бы сказал, нет, не существует известных подходов для постоянных мягких куч. Описание одного будет опубликованным результатом (оно может сводиться к добавлению копирования, где вы будете изменять исходную структуру, и определению возможностей совместного использования).

1 голос
/ 08 июня 2015

Статья Хаима Каплана, Роберта Э. Тарьяна, Ури Цвика описывает, но не полностью анализирует чисто функциональный вариантЕго можно найти по адресу:

http://phdtree.org/pdf/44150182-soft-heaps-simplified/

0 голосов
/ 08 июля 2014

В этом проекте есть Java-код, который может быть не слишком страшным для перевода на Scala ... и затем сделать его более функциональным.В книге Data Structures есть код на Haskell, который может быть легче перенести в Soft Heaps, особенно с учетом примера кода Java.

https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...