Эффективность чисто функционального программирования

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

• вышеупомянутый Союз-найти
• хэш-таблицы
• массивы
• некоторые алгоритмы графа
• ...

однако мы предполагаем, что в" императивных " языках доступ к памяти равен O (1), тогда как теоретически это не может быть так асимптотически(т. е. для неограниченных размеров задачи) и доступ к памяти в пределах огромного набора данных всегда O (log n), который может быть эмулирован на функциональном языке.

кроме того, мы должны помнить, что на самом деле все современные функциональные языки предоставляют изменяемые данные, и Haskell даже предоставляет их без ущерба для чистоты (ST monad).

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

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

EDIT:

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

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

если строгая функция имеет сложность O(f(n)) в строгом языке, то она также имеет сложность O(f(n)) в ленивом языке. Зачем волноваться? :)

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

доказательство эскиз: Учитывая фиксированную верхнюю границу использования памяти, следует иметь возможность написать виртуальную машину, которая выполняет набор императивных команд с такой же асимптотической сложностью, как если бы вы действительно выполняли на этой машине. Это связано с тем, что вы можете управлять изменяемой памятью как постоянной структурой данных, давая o(log(n)) чтение и запись, но с фиксированной верхней границей памяти использование, вы можете иметь фиксированный объем памяти, в результате чего они распадаются на O(1). Таким образом, функциональная реализация может быть императивной версией, работающей в функциональной реализации виртуальной машины, и поэтому они оба должны иметь одинаковую асимптотическую сложность.

Я бы предложил читать дальше производительность Haskell, а затем взглянув на игра ориентиры производительность для функциональных языков по сравнению с процедурными / OO.

"функциональный" - это куча различных функций, каждая из которых независимо полезна, и ее более полезно рассматривать по отдельности.

неизменяемости

теперь, когда я знаком с ним, каждый раз, когда я могу уйти с возвращением неизменного результата, я всегда стараюсь сделать это, даже в объектно-ориентированной программе. Проще рассуждать о программе, если у вас есть данные типа значения.

функции как первый класс Типы

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

возможность создавать функции (например, превращение действия в просто действие также весьма полезно в некоторых сценариях.

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

монады

Это тонкая, но очень мощная конструкция. Это так же мощно, как ключевое слово yield, используемое для создания классов IEnumerable в C#. По сути, это создание государственной машины для вас под прикрытием, но ваша логика выглядит линейной.

Ленивая Оценка И Рекурсия

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

S-Выражений

Я думаю, я не уверен, где это поставить, но возможность рассматривать некомпилированный код как объект (и проверять/изменять его), такие как Lisp S-выражения или выражения LINQ, в некотором смысле является самым мощным инструментом функционального программирования. Большинство новых .Сеть "свободный" интерфейсы, и DSL, использовать сочетание лямбда-синтаксиса и выражений LINQ для создания некоторых очень сжатых API. Не говоря уже о Linq2Sql/Linq2Nhibernate, где ваш код C# "волшебно" выполняется как SQL, а не как код C#.