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

Ответ 1

В книге Purely Functional Data Structures подробно рассматриваются ваши вопросы и включает в себя большое сочетание теории и реализаций в основном в ML - приложение также содержит реализации Haskell, поэтому вы должны следовать за ним с добавлением дополнительной страницы. Это довольно хорошо (хотя и трудное по частям), если вы действительно заинтересованы в тщательном ответе на свои вопросы. Сказав, что я думаю, что эфемерный дал превосходный короткий ответ.

edit: Стивен Хувиг предоставил ссылку на тезис о том, что книга началась как. Хотя я не прочитал это, единственное, чего не хватает (судя по оглавлению), это реализация Haskell.

Ответ 2

Говоря как кто-то, кто много лет занимается OO, а недавно строит крупный проект, требующий большой скорости (в режиме реального времени автоматическая система торговли опционами) в Haskell:

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

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

• Если да, это проблема?

Это не было для меня, кроме необходимости потратить некоторое время, чтобы изучить новый способ работы. В частности, производительность, конечно же, не была проблемой: система, над которой я работаю, работает значительно быстрее, чем предыдущая реализация Java, например.

• Что делать, если вам действительно нужна хэш-таблица для какого-либо приложения? Вы просто проглотите дополнительные расходы, понесенные для модификаций?

Как правило, проблема заключается не в том, что "вам действительно нужна хэш-таблица", а в том, что вам нужен доступ к определенным данным в течение определенных заданных временных ограничений (что вполне может быть "как можно быстрее на некоторых определенных аппаратных средствах" )., Для этого вы смотрите вокруг и делаете то, что вам нужно делать. Если это включает введение изменчивости, я не вижу большой проблемы с этим, и вы можете сделать это в Haskell, хотя это может быть не так удобно, как на других языках. Но имейте в виду, если у вас есть проблема такого характера, это, конечно, будет не так просто, как "использовать общую хеш-таблицу, и все готово". Чрезвычайно высокая производительность для конкретной функциональности на конкретной аппаратной платформе неизменно занимает много работы и обычно более чем несколько трюков. Предпочитая реализацию одного языка над другим только потому, что он имеет определенную вещь, которая работает лучше, чем на других языках, является, на мой взгляд, довольно бесхитростным подходом к разработке программного обеспечения, который вряд ли будет давать хорошие результаты.

Ответ 3

• Да. Обычно кортежи, списки и частично оцениваемые функции являются очень распространенными структурами данных в языках функционального программирования. Мутируемые структуры данных, такие как массивы и (реальные) хэш-таблицы, используются гораздо меньше, потому что они не вписываются в Haskell. SML (который также функциональный, но не ленивый) может использовать массивы более естественно, чем Haskell, но списки еще более распространены, поскольку они хорошо отображают рекурсивные алгоритмы.
• Я не уверен, как ответить на это. Проблема для кого?
• Существуют реализации ассоциативных массивов (эквивалент хэш-таблицы), которые могут продолжать разделять большую часть их базовой структуры даже после разных обновлений. Я считаю, что GHC Data.Map делает; Кроме того, Edison имеет довольно много ленивых/функционально-дружественных структур данных.

Ответ 4

Тезис Криса Окасаки, Чисто функциональные структуры данных, доступен для свободного онлайн. Он охватывает множество различных стратегий для неизменного постоянного представления данных.

Насколько действительно нужна хэш-таблица, считайте, что поиск O (lg n) в 20 раз медленнее, чем поиск O (1), когда вы ищете миллион элементов.

Ответ 5

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

Как упоминалось выше, книга Криса Окасаки о чисто функциональных структурах данных очень хороша.

Ответ 6

Функциональные программы имеют тенденцию уделять больше внимания рекурсии. Это, в свою очередь, предполагает использование рекурсивных алгоритмов и рекурсивных структур данных. Оба списка и деревья являются рекурсивными структурами ( "следующая" ссылка в списке - это другой список, а дочерние элементы дерева node являются обоими деревьями).

Возможно, вам захочется пересмотреть, если вы смотрите на дополнительные расходы по алгоритму. Почему хэш-таблица (которая является O (1) для нерекурсивного алгоритма) несет дополнительные расходы? Какое преимущество вы получаете, используя его, в отличие от дерева или списка?

Ответ 7

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

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

• Если да, это проблема?

Проблема заключается в том, что императивные парадигмы не смогут сохранить эффективность, поскольку распараллеливание становится более необходимым - единственный выход для этих языков - избавиться от побочных эффектов, но тогда они станут сломанными функциональными языками, но тогда, почему я должен беспокоиться о них, когда есть неплохие рабочие функциональные языки. Кроме того, семантику функциональных языков легче контролировать, поэтому функциональные программы можно доказать правильно, тогда как их С++-копии не могут (пока, во всяком случае). Следовательно, многие формальные инструменты проверки основаны на функциональных языках - например, ACL2 основан на общем lisp, а Cryptol основан на Haskell. Поскольку формальная проверка - волна будущих функциональных языков, лучше интегрироваться с этими инструментами. Короче говоря, попрощайтесь с C, С++ и такими - хорошие данные! Кто-то должен был взять с собой 30 очков 6 лет назад.

• Что делать, если вам действительно нужна хэш-таблица для какого-либо приложения? Вы просто усвоить дополнительные расходы понесенные для модификаций?

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

Ответ 8

Да, основное отличие - неизменность данных, которые могут включать код (см. функции более высокого порядка). См. Страницу Wikipedia Purely Functional для списка общих типов данных и обычаев. Независимо от того, зависит ли она от проблемы, как вы ее смотрите. Существует много преимуществ программирования на функциональном языке, если он соответствует типу задачи, над которой вы работаете. Хэш-таблица - это тип ассоциативного массива, но это не тот, который вы хотите использовать на функциональном языке из-за переименования, которое вам нужно будет делать при вставке и низкой производительности без массивов. Вместо этого попробуйте реализацию Haskell Data.Map для ассоциативного массива.

Ответ 9

Насколько хэш-таблицы в функциональных языках идут: Поскольку ACL2 упоминался выше, я хочу отметить, что есть библиотека "хэш-минус" для ACL2, которая предоставляет логическую историю, которая в основном представляет собой семантику ассоциаций-списков, но имеет производительность хеш-таблицы (например, вы можете найти значение в таблице, используя hons-get). Если вам интересно, ознакомьтесь с темой "hons" в руководствах пользователей ACL2.