Одно из обещаний свободного от побочных эффектов, ссылочно прозрачного функционального программирования заключается в том, что такой код может быть всесторонне оптимизирован. Чтобы процитировать Википедию:
Неизменяемость данных во многих случаях может привести к эффективности выполнения, позволяя компилятору делать небезопасные предположения в императивном языке, таким образом увеличивая возможности для встроенного расширения.
Я хотел бы увидеть примеры, в которых компилятор функционального языка превосходит императивный компилятор, создавая более оптимизированный код.
Изменить: я попытался дать конкретный сценарий, но, видимо, это не было хорошей идеей. Поэтому я постараюсь объяснить это по-другому.
Программисты переводят идеи (алгоритмы) на языки, понятные машинам. В то же время одним из наиболее важных аспектов перевода является то, что люди также могут понять полученный код. К сожалению, во многих случаях приходится идти на компромисс: сжатый, читаемый код страдает низкой производительностью, и его необходимо оптимизировать вручную. Это подвержено ошибкам, требует много времени и делает код менее читаемым (вплоть до совершенно нечитаемым).
Основы функциональных языков, такие как неизменность и ссылочная прозрачность, позволяют компиляторам выполнять обширную оптимизацию, которая может заменить ручную оптимизацию кода и освобождение программистов от этого компромисса. Ищу примеры идей (алгоритмов) и их реализации, такие как:
- (функциональная) реализация близка к исходной идее и проста для понимания,
- он значительно оптимизирован компилятором языка, и
- трудно (или невозможно) написать такой же эффективный код на императивном языке без ручной оптимизации, которая снижает его краткость и удобочитаемость.
Прошу прощения, если это немного расплывчато, но я надеюсь, что идея ясна. Я не хочу давать лишних ограничений в ответах. Я открыт для предложений, если кто-то знает, как это лучше выразить.
Мой интерес не только теоретический. Я бы хотел использовать такие примеры (среди прочего), чтобы заинтересовать студентов функциональным программированием.
Поначалу меня не удовлетворили несколько примеров, предложенных в комментариях. Поразмыслив, я беру свои возражения назад, это хорошие примеры. Не стесняйтесь расширять их до полных ответов, чтобы люди могли комментировать и голосовать за них.
(Одним из классов таких примеров, скорее всего, будет распараллеленный код, который может использовать преимущества нескольких ядер ЦП. Часто на функциональных языках это можно сделать легко, не жертвуя простотой кода (например, в Haskell, добавив _ 1_ или pseq в соответствующих местах). Меня интересуют такие примеры тоже, но и в других, непараллельных.)
min = head . sort- person josejuan schedule 16.01.2013log nраз в Haskell. Я показываю, как Haskell оптимизирует простое решение. Вы никогда не сможете сравнивать один с одним компиляторами C ++ и Haskell (например) именно потому, что они используют разные стратегии. Вы можете сравнивать результат оптимизации, а не оптимизации. - person josejuan schedule 16.01.2013take 10 . sort). Возможно, можно было бы пойти еще дальше, чтобы реализовать ленивую быструю сортировку и использовать ее в качестве эффективного алгоритма выбора . Возможно, вы могли бы расширить свой комментарий до ответа, чтобы люди могли проголосовать за него. - person Petr schedule 17.01.2013