Haskell оптимизация

> Как хаскель работает на внутреннем уровне: создаёт список из тясячи чисел, потом их передает map, с выхода map список квадратов идёт на фильтр, потом отфильтрованный список на sum?

нет

А как?

И для сравнения: как решить эту задачу быстрее всего (на хаскеле).

Быстрее всего работает вот это:

for (unsigned i = 1, sqr = 1; i <= 1000; i++) {
  printf("sqr(%u) = %u\n", i, sqr);
  sqr += (i << 1) + 1;
}

man высокоуровневая оптимизация, короче

</thread>

Почитай про нормальный порядок редукции.

...как решить эту задачу быстрее всего (НА ХАСКЕЛЕ).

Кстати, не понял к чему код — он даже не ту задачу решает.

Спасибо. Погуглю. Хоть один конструктивный ответ ;)

Был бы очень признателен, если хотя бы вкрадце ответили на вопросы 1 и 2.

Спасибо. А чем этот код лучше 3х приведенных?

Haskell начнёт с вычисления sum и обнаружит что для него жизненно необходим список. Для такой задачи нужен ленивый генератор списков, то есть который определён как вот_голова:а_хвост_посчитаю_следующей_итерацией. Что-то мне подсказывает что и filter и map ведут себя именно так. А дальше происходит следующее sum обращается к элементу списка, его вычисляют, sum суммирует ну и так далее. То есть алгоритм стремится к приведённому тобой циклу.

Если бы Haskell придерживался описанной тобой логики, то как бы работал take 5 [1..]?

1. http://haskell.cs.yale.edu/ghc/docs/6.12.2/html/users_guide/profiling.html
2. нет, все типы в Haskell по умолчанию ленивые, стратегия редукции - outermost graph reduction
3. http://www.haskell.org/ghc/docs/6.12.2/html/users_guide/rewrite-rules.html

1. http://haskell.cs.yale.edu/ghc/docs/6.12.2/html/users_guide/profiling.html

Ну это не интересно. Интересно «внутренняя» реализация: одно дело, если все три варианта внутри реализуются хаскелем по разному, а другое — это синтаксический сахар.

The Implementation of Functional Programming Languages

11.1 - lazy evalution, это про первые два примера,

7 - list comprehations, это про третий,

III - G-machine, это вообще про подход к трансляции. Именно в haskell это STG (simple tagless G-machine).

Интересно «внутренняя» реализация

ну возьми да посмотри, в чём проблема?

>Кстати, не понял к чему код — он даже не ту задачу решает.

Он решает задачу быстрого вычисления последовательных квадратов чисел. Если ты настолько талантлив, что сюда нужно еще приписать суммирование, то у меня всего два вопроса:

1. что ты забыл в программировании

2. зачем тебе хаскель, если даже примитивная императивщина сложности вызывает?

Спасибо. А чем этот код лучше 3х приведенных?

Он хуже. Немного лучше его - вариант с list comprehasion. Лучше всего - два первых варианта (они идентичны, т.к. карирование функций транслируется не через замыкания а особым образом :)).

реквест: кто напишет stack overflow free версию?

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

Ладно, забудьте. Почему-то от ЛОРа впечатления всё хуже. Ни один вопрос задать нельзя. Обольют гавном с ног до головы, пошлют на кучу никуда не ведущих ссылок, куча флуда, половина ответов мол «ты че дурак — иди да почитай маны» и грубость повсеместная.

Радует, что не всё так запущено. Есть несколько участников (KblCb, quasimoto и ещё несколько), которые всегда отвечают строго по теме, вежливо и понятно. А если нечего сказать — молчать. Респект вам!

Спасибо! Исчерпывающий ответ!

Огорчает то, что с каждым годом люди все хуже и хуже говорят по-русски. Посчитать сумму квадратов := $\sum_{i=1}^1000 i^2$.

Также считаю правильным обливать говном с ног до головы тех, кто не умеет задавать вопросы. Например, дурацкий вопрос про память решается расширением диапазона и запуском бинарника. После запуска видим, что даже «типа списку» из миллиарда элементов не требуется гигабайт оперативной памяти для работы. Хоть хаскель и полное говно, но писаки его не настолько идиоты, чтобы заниматься хранением ненужных списков.

test = odd

bar acc i n | i == n     = acc
            | test (i^2) = bar (i^2 + acc) (i + 1) n
            | otherwise  = bar acc         (i + 1) n

foo n = bar 0 0 n

Почему TCO не работает?

В ghc все (ну или почти все; точнее, все, удовлетворяющие определенным критериям; в мануале они называются goods consumer и good producer) списочно-обрабатывающие функции подвергаются list fusion'у - промежуточных списков не создается. Делается это посредством rewrite rules.

Также считаю правильным...

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

Ясно. Спасибо.

/offtop

Посчитать сумму квадратов := $\sum_{i=1}^1000 i^2$.

Ну умеете вы считать сумму квадратов на Си и якобы умеете это записывать в TeX (у вас сумма до от одного до одного записана). Но я тут причём? Радуйтесь себе в сторонке. Суть темы была в подсчете суммы только тех квадратов, которые удовлетворяют предикату test, причём на языке Haskell. Вы опять двадцать пять: учите меня считать сумму ы всех квадратов на Сях. А самое главное — ни одно ваше сообщение не содержательно с точки зрения темы.

Ладно, я из темы выхожу. Да и с форума, наверное, тоже. На базаре и то культурней обстановка.

Мне можете ничего не отвечать — я уже не прочитаю. Между собой, ради бога, общайтесь... ;)

>Суть темы была в подсчете суммы только тех квадратов, которые удовлетворяют предикату test, причём на языке Haskell.

Суть темы была в оптимизации. Использовать ЯВУ и жертвовать выразительностью ради скорости весьма странно.

> sum [ n^2 | n <- [1..1000], test n ]

одному мне кажется, что этот вариант явно расходится с предыдущими?

одному мне кажется, что этот вариант явно расходится с предыдущими?

тут проверка до возведения в квадрат, да, но кого это волнует?