Язык Haskell: О пользе и вреде лени: различия между версиями

Представленная искусная реализация функции быстрой сортировки на Си, придуманная [[w:Хоар, Чарльз Энтони Ричард|Хоаром]], безусловно, выигрывает по эффективности у реализации на Haskell (как по времени работы, так и по необходимой для вычислений памяти). Но код на Haskell существенно проще! Следует отметить, что обе реализации имеют сложность <math>O(n \log n)</math>, то есть время работы на списке (массиве) длины <math>n</math> растёт пропорционально <math>n \log n</math>, и в этом «асимптотическом смысле» обе реализации одинаково хороши.

Кроме того, активно развиваются алгоритмы трансляции функциональных языков, и по эффективности ассемблерного кода они постепенно начинают догонять императивные языки. А самое важное (но сложное для понимания) достоинство Haskell заключается в том,что в <!--em-->трансляторы языка Haskell со временем можно будет добавить алгоритмы, которые по данным определениям функций<!--em--> смогут сами находить наиболее эффективные алгоритмы их вычисления, например, с использованием динамического программирования или жадных стратегий. Сегодня теория алгоритмов уже настолько развита, что можно выделить ряд шаблонов алгоритмических задач, и «научить» трансляторы функциональных языков программирования «видеть их» в определениях функций и применять известные эффективные алгоритмы вычисления.