[FP] Не дающий покоя, навязчивый, сводящий с ума вопрос

> Скажите, это как-нибудь оптимизируется хоть в каком-нибудь ФЯ?

Насчет ФЯ не знаю, но в Python 2.x это не оптимизируется, и будет тебе 3 списка (хотя рекурсии что-то я не вижу). В Python 3.0, AFAIK, map и filter возвращают итераторы, и получается как в императивном случае.

За настоящие ФЯ пусть ответят настоящие спецы :)

> Этож какое неоправданное использование ресурсов!

Память нынче дешева :D

Python - не функциональный язык. И потом, зачем тут списки?

Делаешь функцию - генератор аккумуляторов(практически sicp-пример):

(defun filter-accumulate (acc p end-p nil-val term next) (labels ((accumulator (init end) (if (funcall end-p init end) nil-val (funcall acc (let ((val (funcall term init))) (if (funcall p val) val nil-val)) (accumulator (funcall next init) end))))) #'accumulator))

И вот твой, собственно, случай: (funcall (filter-accumulate #'+ #'plusp #'> 0 #'sin #'1+) 0 99)

(можно еще и в хвостовую рекурсию развернуть или сразу в loop, тогда и по производительности совсем замечательно все будет)

Ох, е.
Вот код:
(defun filter-accumulate (acc p nil-val term next)
(labels ((accumulator
(init end)
(if (> init end) nil-val
(funcall acc
(let ((val (funcall term init)))
(if (funcall p val) val nil-val))
(accumulator (funcall next init) end)))))
#'accumulator))

(funcall (filter-accumulate #'+ #'plusp #'> 0 #'sin #'1+) 0 99)

(defun filter-accumulate (acc p end-p nil-val term next)
 (labels ((accumulator 
	    (init end) 
	    (if (funcall end-p init end) nil-val
	      (funcall acc
		       (let ((val (funcall term init)))
			 (if (funcall p val) val nil-val))
		       (accumulator (funcall next init) end)))))
   #'accumulator))


(funcall (filter-accumulate #'+ #'plusp #'> 0 #'sin #'1+) 0 99) 

Функциональный язык С# всё в один цикл раскатает (см. yield).

>Функциональный язык С#

<картинка с петросяном>

Ух спасибо, добрый анон. Теперь буду спать спокойно, зная, что существуют генераторы аккамуляторов (пока не узнаю что это такое)

>что это такое
Обычные функции высшего порядка, например

Что бы не создавать списков, можно так:

from itertools import imap, ifilter
reduce(float.__add__, ifilter(lambda x: x > 0, imap(sin, range(100))))

Но мне кажется, что так тоже будет несколько медленнее, чем простой цикл.

какой только херни не понапридумывают, лишь бы нормальные фвп не использовать
В питоне что, запретили фпв создавать?

В ghc (Glasgow Haskell Compiler) все будет заменено одним списком (по крайней мере, должно; если не заменяется, можно дописать свои правила преобразования). см. http://www.haskell.org/ghc/docs/latest/html/users_guide/rewrite-rules.html

В разных компиляторах Common Lisp тоже вполне возможно (не смотрел точно). В Common Lisp — за счет compiler-macro.

Да и в других языках вполне возможно.

> какой только херни не понапридумывают, лишь бы нормальные фвп не использовать

Ага, понапридумывали всякие циклы. :)

> В питоне что, запретили фпв создавать?

Нет, не запрещали.

sum ((x for x in ( sin(t) for t in xrange (100) ) if x > 0 ))

Этот питоновский вариант не будет создавать никаких массивов. В ленивых языках тоже не будет создано никаких массивов, всё будет делаться на лету, т.е. тоже сплошной цикл.

Haskell:

sum $ filter (>=0) $ map sin [0..99]

Цикл будет один - ибо произойдет list fusion.

>>sum $ filter (>=0) $ map sin [0..99] >>Цикл будет один - ибо произойдет list fusion.

а в схеме будет list fusion?

>>sum ((x for x in ( sin(t) for t in xrange (100) ) if x > 0 ))

Императивненько как-то..

Похоже я упускаю что-то очевидное: почему нельзя заменить range на xrange? И вот уже одним списком меньше. Ну и про itertools уже сказали.

>>почему нельзя заменить range на xrange? И вот уже одним списком меньше. Ну и про itertools уже сказали.

Да, видимо это и есть наиболее рациональный подход (по крайней мере для больших списков).

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

А в ФЯ как технически происходит оптимизация?

>>xrange последовательно обмазывается функциями imap и ifilter (или просто map и filter в пузике(py3k))

selfix

>А в ФЯ как технически происходит оптимизация?

http://en.wikipedia.org/wiki/Compiler_optimizations#Functional_language_optim...

> reduce(float.__add__, filter(lambda x: x > 0, map(sin, range(100))))

> Этож какое неоправданное использование ресурсов!

ну itertools же:

from itertools import ifilter, imap

reduce(float.__add__, ifilter(lambda x: x > 0, imap(sin, xrange(100))))


также, в питон3 все это говнище будет генераторами по умолчанию

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

1) короче
2) проще для понимания
3) точно известно время работы

? Ну кроме красноглазия ессно...

Ну, reduce как раз по этой причине собирались убрать из питона (по крайней мере из builtins).

А что касается map, filter и lambda, они обычно сильно упрощают понимание и код короче делают.

> если переписать обычным тупым циклом, то получится:

> 1) короче

Перепиши. Посмотрим, получится ли короче.

> 2) проще для понимания

Это да. Хотя - вопрос привычки :)

> 3) точно известно время работы

Оно в обоих случаях известно.

> 1) короче

существенно короче только если писать на c++

на питоне длина кода примерно та же

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

2) проще для понимания

вопрос привычки.

по мне так сумма в виде sum(list_of_elements) понятнее чем сумма в виде цикла.

3) точно известно время работы

оно точно известно при любой форме записи

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

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

Так лучше?

sum [y|x<-[0..99], let y=sin x, y>0]

это что, компрехеншн?

Факториал вы тоже считаете генерируя список перемножая его элементы?

>это что, компрехеншн?

да

>Факториал вы тоже считаете генерируя список перемножая его элементы?

да

какие проблемы? Начто иначе нужен lazy evaluation? Чтобы и писать легко и работало в результате быстро.

>1) короче

в большинстве случаев будет намного длиннее. особенно в примерах сложней факториала

>2) проще для понимания

это троллинг

>3) точно известно время работы

что мешает посчитать асимптотическую сложность для обоих случаев? в чём принципиальная разница?

>> в большинстве случаев будет намного длиннее. особенно в примерах сложней факториала

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

>> это троллинг

Это ИМХО =). Хотя согласен - это скорее дело привычки.

>> что мешает посчитать асимптотическую сложность для обоих случаев? в чём принципиальная разница?

Разница в том, что в случае если я напишу на C тупой цикл, который тупо суммирует N синусов, то я буду точно уверен, что время выполнения - O(N). Назвисимо от используемого компилятора. А в случае магии со списками и "труЪ функциональщиной" придётся надеяться на компилятор - то ли ему хватит ума дооптимизировать до O(N), то ли он родит нечто вроде O(N^2)...

P.S. Я не троллю, мне действительно интересно зачем всё это нужно.

>Возможно. Но не всегда. Вот в тех случаях когда нефункциональный подход будет короче - зачем всёравно писать функционально?

это уже дзен и LISP-way

>Разница в том, что в случае если я напишу на C тупой цикл, который тупо суммирует N синусов, то я буду точно уверен, что время выполнения - O(N). Назвисимо от используемого компилятора. А в случае магии со списками и "труЪ функциональщиной" придётся надеяться на компилятор - то ли ему хватит ума дооптимизировать до O(N), то ли он родит нечто вроде O(N^2)...

а компиляторы C ничего не оптимизируют, да? или в труЪ-функциональщине нет профайлеров и вывода промежуточного кода?

>Я не троллю, мне действительно интересно зачем всё это нужно

что именно? ФП? для решения задач, которые хорошо ложатся на ФП ;) в случае небольших выпадающих из общей картины участков есть FFI, для haskell бонусом - квазиквотация и штуковины вроде harpy

если же вся работа сводится к борьбе с ФП, то стоит задуматься - а нужен ли он здесь вообще

>> а компиляторы C ничего не оптимизируют, да? или в труЪ-функциональщине нет профайлеров и вывода промежуточного кода?

А теперь прочитай пост топикстартера:

>> В результате создается 3 списка и вычисления происходят в 3 циклах (рекурсиях?).

>> Императивным подходом получаем 1 список + 1 цикл

>> Скажите, это как-нибудь оптимизируется хоть в каком-нибудь ФЯ? 3 списка заменяются одним? 3 рекурсии заменяются одним циклом? Или все остается так, как выглядит =( ? Этож какое неоправданное использование ресурсов!

Т.е. императивным подходом мы гарантированно получаем O(N), без всяких если. А функциональным - 50/50, как решит компилятор. Допустим я для разработки и отладки использую хороший компилятор X и пишу только в функциональном стиле. У меня всё работает хорошо и быстро. Но мои исходники скачал Вася Пупкин и собрал их не таким хорошим компилятором Y, который кое-где не додумался соптимизировать до уровня компилятора X. В результате у васи моя программа работает в N раз медленней. Причём это *та*же* программа с теми же алгоритмами. Лично мне вот такая неопределённость и не нравится.

Компиляторы C и C++ в принципе не умеют оптимизировать алгоритмы (кроме простейших случаев), да от них это и не требуется. Никто в здравом уме не станет писать высокоуровневый код типа "сумма(синус(*) от 1.0 до 99.0 с шагом 1.0)" на C++. С одной стороны это далеко не всегда удобно, но с другой стороны всегда можно гарантировать как и за какое время будет работать алгоритм. На любом компиляторе, которым эта программа соберётся.

> Т.е. императивным подходом мы гарантированно получаем O(N), без всяких если. А функциональным - 50/50, как решит компилятор.

Такое впечатление, что ты вообще не читал ответов. Или ты просто троллишь.

> Компиляторы C и C++ в принципе не умеют оптимизировать алгоритмы

Тем не менее, результаты работы разных компиляторов могут различаться в разы, и что - выкинем Си/Си++?

>Но мои исходники скачал Вася Пупкин и собрал их не таким хорошим компилятором Y

для haskell есть ghc. чем будет собирать Вася? yhc? jhc? они несколько нестабильные, вообще говоря

>всегда можно гарантировать как и за какое время будет работать алгоритм. На любом компиляторе, которым эта программа соберётся

это не так. особенно для C++

а по сабжу - судя по всему, тебя больше волнует переносимость ФП-исходников между компиляторами, чем оптимизация. тогда о чём вообще речь? что же касается самой оптимизации, то все связанные со сложностью вопросы оцениваются ничуть не хуже чем для императивных языков

> Никто в здравом уме не станет писать высокоуровневый код типа "сумма(синус(*) от 1.0 до 99.0 с шагом 1.0)" на C++

Не? :D

s = sum_fn<double>(1.0, 99.0, sin, 1.0)

(тело sum_fn остается в качестве упражнения читателю :))

>> для haskell есть ghc. чем будет собирать Вася? yhc? jhc? они несколько нестабильные, вообще говоря

Для common lisp'а существует дофига компиляторов и интерпретаторов.

>> это не так. особенно для C++

Я пытаюсь сказать, что при написании программ на языках типа C++ никто не будет надеятся на то, что компилятор сможет хорошо оптимизировать сложный высокоуровневый код. Хотя некоторые компиляторы это и умеют.

>> а по сабжу - судя по всему, тебя больше волнует переносимость ФП-исходников между компиляторами, чем оптимизация. тогда о чём вообще речь?

Можно и так сказать.

>> что же касается самой оптимизации, то все связанные со сложностью вопросы оцениваются ничуть не хуже чем для императивных языков

В том и проблема, что из-за "подразумевающихся" оптимизаций для *языков* это никак не оценить. Только для конкретных компиляторов. У компиляторов C такой проблемы просто нет, так как они не умеют оптимизировать на таком уровне (я уже задолбался говорить одно и то же) =).

И хочу напомнить: я знаю, что в том же common lisp'е можно писать и императивно. Но почему многие не рекомендуют так делать? Мне вот это не понятно. Я пока не вижу ни каких плюсов в переписывании императивного кода в чисто функциональный, там где нет явного выигрыша вроде сильного упрощения кода и выигрыша в производительности. Только минусы.

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

не видишь? не переписывай!

>Для common lisp'а существует дофига компиляторов и интерпретаторов

а CL и не функциональный язык: там как хочешь, так и пишешь

>Я пытаюсь сказать, что при написании программ на языках типа C++ никто не будет надеятся на то, что компилятор сможет хорошо оптимизировать сложный высокоуровневый код. Хотя некоторые компиляторы это и умеют

ты знаешь, на это нигде и никто не надеется. работает медленно - берём профайлер и оптимизируем. хоть в C++, хоть в Haskell, хоть в Scheme

>У компиляторов C такой проблемы просто нет, так как они не умеют оптимизировать на таком уровне

однако разница между результатом работы всё же есть, так? и как достигается переносимость? вот здесь - то же самое, только на "другом уровне"

> В том и проблема, что из-за "подразумевающихся" оптимизаций для *языков* это никак не оценить. Только для конкретных компиляторов. У компиляторов C такой проблемы просто нет, так как они не умеют оптимизировать на таком уровне (я уже задолбался говорить одно и то же) =).


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

такие штуки как разворот рекурсии в цикл приводят к
_пропорциональному_ изменению времени выполнения
(плюс, возможно, уменьшение потребления памяти)

> А можно вопрос (возможно глупый)? Вот хоть убейте не понимаю: зачем подобные вещи писать в чисто функциональном стиле, хотя если переписать обычным тупым циклом, то получится:

> 1) короче > 2) проще для понимания > 3) точно известно время работы

Как насчет параллелизации? MapReduce было популяризованно гуглом как среда которая параллельно вычисляет на произвольном числе машин, возможно на тысячах. Размер задачи будет соответствующий, на практике там будет не i=1..99 а i=1..999999999.

Нет, я все же не понял, почему функциональным стилем называется работа со списками(пусть и ленивыми)?
Серьезно, единственный функциональный пример тут >>3356901 - фвп и линейная рекурсия.

При чем тут MR? Это лишь удобная модель, которую понятно как распараллелить и под нее можно подвести многие задачи. И свой оверхед у нее есть.

Ладно ладно, вы опять меня убедили =).

lists:foldl(fun(X, Y) -> X + sin(Y), 0, lists:seq(0, 99)).

что может быть проще?

упс, зобыл end

lists:foldl(fun(X, Y) -> X + sin(Y) end, 0, lists:seq(0, 99)).

эх, сначало не заметил уточнения насчет "положительных" значений,
а потом не успел написать правильный вариант... напишу щас тогда :)

lists:foldl(fun(X, Y) -> 
                        case math:sin(Y) of
                            Z when Z >=0 ->
                                X + Z;
                            _ ->
                                X
                        end
                end,
                0, lists:seq(0, 99)).

форматирование пздц

это так и задумано или глюк?

Тебя что конкретно смущает? форматирование или синтаксис? Если первое, то тут да, что-то немного съехало, если второе, то дело привычки.