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

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

Тезис Chris Okasaki, Чисто Функциональные Структуры данных , доступен бесплатно онлайн. Это покрывает много различных стратегий неизменного персистентного представления данных.

До реальной необходимости в хэш-таблице, полагайте, что O (LG n) поиск является только в двадцать раз более медленным, чем O (1) поиск при поиске миллиона элементов.

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

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

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

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

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

• Если так, действительно ли это - проблема?

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

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

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

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

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

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

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

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

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

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

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

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