Эффективное представление функций

Question

Тип функции A -> B в некотором смысле не очень хорош.Хотя функции являются первоклассными значениями, часто невозможно свободно ими управлять из-за проблем эффективности.Вы не можете применить слишком много преобразований (A -> B) -> (C -> D), в какой-то момент вам нужно вычислить значение.

Очевидно, это связано с не строгой природой->.

Есть хорошо известные приемы работы с функциями типа Double -> Double.Их можно представить как векторы с заданным базисом, который может состоять из тригонометрических функций, полиномов и т. Д.

Есть ли какие-то общие приемы, позволяющие обойти неэффективность типа A -> B?* Или альтернативы ->?

Answer 1

Вы, похоже, обеспокоены тем, что данные h === f • g, f • g обычно менее эффективны, чем h. Учитывая состав функций, известных во время компиляции, компилятор выполняет два трюка, которые могут сделать f • g более эффективными, чем вы подозреваете, - вставку и слияние. Встраивание исключает дополнительное косвенное обращение к второму вызову функции и открывает множество новых возможностей для оптимизации. Слияние потоков (или слияние сборка / складывание) может (для базового примера) превратить такие композиции, как map f . map g, в map (f . g), тем самым уменьшая число обходов конструкции на постоянный коэффициент. Fusion работает не только со списками, но и с другими структурами и предоставляет одну из причин эффективной производительности библиотек Haskell, таких как Vector.

Сокращенный синтез: http://www.haskell.org/haskellwiki/Correctness_of_short_cut_fusion

Stream Fusion: Что такое Stream Fusion Haskell

Answer 2

Я не могу это подтвердить. Как продуктивный пользователь и разработчик AFRP, я выполняю преобразования для полностью полиморфных функций много, глубоко вложенных и для долго работающих приложений. Обратите внимание, что компиляторы Haskell не используют традиционную парадигму вызова функций на основе стека. Они используют алгоритмы сокращения графа. У нас нет таких проблем, как, скажем, C.

Answer 3

Одним из наиболее распространенных приемов является запоминание - сохранение значения функции после ее вычисления. Ссылки: Haskellwiki , SO, например , MemoCombinators . Как вы упомянули, другой трюк - когда у вас есть хороший тип функции (полином, вектор, ряд Тейлора и т. Д.) - тогда он может быть представлен в виде списка, выражения и т. Д.

Answer 4

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

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

Ленивые аргументы оцениваются путем замены параметра на выражение аргумента, где бы оно ни происходило.

По умолчанию «пусть решает компилятор». Для большого количества «обычного» кода (что бы это ни значило) не имеет значения, используете ли вы нетерпеливую или ленивую оценку.

Обычно в Феликсе ленивая оценка выполняется быстрее: обратите внимание, это НЕ означает закрытие. Это означает встраивание. Однако иногда компилятор выбирает стремительную оценку, это уменьшает раздувание кода, и слишком много встраивания приводит к обратным результатам. Я не утверждаю, что алгоритм хорош, но Феликс иногда может опередить С и Окамла (GHC не попал в финал).

В качестве простого примера. Типы классов. У Феликса есть классы типов, вроде Haskell. Нет или очень мало производительности ... конечно, нет словарей!

На мой взгляд, Haskell был бы намного лучше, если бы вы просто отказались от архаичной концепции раздельной компиляции: анализаторы целых программ могут сделать намного больше, а текст работает гораздо быстрее, чем объектный код (при полной свободе) кешировать результаты компиляции). Это безумие, когда ленивый язык использует модель компиляции, предназначенную для энергичной оценки!

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