А вот за что я не люблю пропагандистов ФП

Так это за некорректные сравнения.

Статья Making Haskell faster than C!

В статье приводится пример оптимизации кода на Haskell таким образом что его выполнение происходит быстрее чем выполнение кода написанного на С. Это было бы приятно и интересно...если бы исходный код на С и на Haskell был бы хоть примерно эквивалентен.

Задача простая - подсчет количества слов в файле. Слова - это части текста отделенные пробелами/табуляцией/переносом строк.

Вот исходный код на С:

int main() {

    int i = 0;

    int c, last_space = 1, this_space;

    while ((c = getchar()) != EOF) {

        this_space = isspace(c);

        if (last_space && !this_space)

            i++;

        last_space = this_space;

    }

    printf("%i\n", i);

    return 0;

}

Вот исходный код на Haskell:

main = print . length . words =<< getContents

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

Программа на С сделана явно с одной целью - написать ее самым медленным способом. Как добиться того чтобы программа выполнялась максимально медленно? Найти самую медленную опрацию и испльзовать ее максимально часто. В данном случае самая медленная операция это чтение из файла/потока. Как использовать ее максимально часто? Читать посимвольно...

Это ясно и понятно большенству программистов на С\С++. Т.е. программисты на С\С++ видят что автор сделал совершенно некорректное сравнение. Сознательно сделав код на С максимально медленным. Автор жулик.... и неважно сделал он это сознательно или нет.

В результате вместо того чтобы заинтересовать программистов на С\С++ возможностями Haskell в частности и ФП в целом мы получаем отторжение.

"Haskell is pure functional langues" - зачем это нужно.

Кажется я наконец разобрался с вопросом почему программисты на haskell настойчиво подчеркивают тот факт что haskell так называемый pure ("чистый") язык. И причем здесь side effects.

Зачем вообще нужны эти "чистые" функции?

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

Пример -
int f(int x) { return 3+x;} - чистая функция
int g(int x) { return random()+x;} - не чистая функция

Как видно в С/С++ чистые функции тоже возможны. Более того, если мы пробежимся по любому коду на С/С++ то мы увидем что большенство функций по крайней мере выглядят как "чистые". Да и большенство алгоритмов записанных на С/С++ неявно предполагает что на одни и те же входные данные мы будем получать один и тот же результат. Иначе программировать было бы сложновато...

Разница между С/С++ и Haskell состоит в том что в Haskell нет (пока забудем о монадах) возможности записать не "чистую" фукнцию.

На первый взгляд это только минус языку(на самом деле так оно и есть, просто плюсы перекрывают этот минус). Поскольку С/С++ получается, по крайней мере внешне, мощнее.

Ну а на второй...В С\С++ нет возможности явно указать является ли функция "чистой" или нет. И все функции по умолчанию считаются не "чистыми".

Допустим есть язык в котором такая возможность есть (Haskell). Что это дает собственно языку? Да толком то ничего... Так зачем же...

Тут возникает вопрос - а что это дает компилятору? А вот компилятору это дает многое. В частности это дает возможность компилятору оптимизировать написанный алгоритм. С использованием "ленивости", отложенных вычислений и прочих плюшек. В идеале получив на вход базовый алгоритм состоящий из вызовов "чистых" функций компилятор(путем оптимизации) может составить некий "идеально быстрый" алгоритм. Т.е. компилятор языка воспринимает подаваемую ему на вход программу как некую функцию над которой он может производить оптимизирующие действия. Банальный пример - получив на вход функцию
(функция получающая два указателя на функции и число и возвращающая число, пишу в псевдокоде)
int f( g(x),k(x),x)
{
return g(x)*g(x)+2*g(x)*k(x)+k(x)*k(x);
}

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

int f( g(x),k(x),x)
{
int temp = g(x)+k(x);
return temp*temp;
}

Возможна ли такая оптимизация компилятором в С/С++? Нет, компилятор С/С++ не может быть уверен что вызовы g(x) всегда возвращают одни и те же значения.

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

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

Подпоследовательность...суперпоследовательнось..перебор...вообщем

Взято с RSDN, что в свою очередь взято из статьи в журнале MonadReader выпуск#1

Суперпоследовательность s последовательности p — такая последовательность, множество подпоследовательностей которой содержит, среди прочего, все перестановки последовательности p.
Пример:

p = 1 2 3
s = 1 2 3 1 2 3 1
    # # #
    #   #   #
      #   #   #
      #       # #
        # # #
        #   #   #

Чтобы далее не заморачиваться с наборами неуникальных элементов, будем полагать, что p(n) = [1..n], т.е. алфавит из n букв.

Напишите:
1) Предикат, проверяющий, является ли данная строка s суперпоследовательностью для алфавита p(n). Наивная реализация занимает O(n! * length(s)), это неприемлемо долго.
2) Генератор кратчайшей суперпоследовательности для p(n)
3) Формулы для оценки нижней и верхней границ её длины. Понятно, что грубые оценки — это n и n^2-n+1. Можно ли их сузить?
4) Формулы для оценки количества кратчайших суперпоследовательностей.

Для любителей самообразования:
— напишите это на Хаскелле и на J
— — наиболее читаемо
— — наиболее компактно
— — наиболее быстродействующе

Почему я отношусь с недоверием к функциональным языкам.

Вот реализация функции quicjsort в Haskell

qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

Коротко, красиво, и главное сразу видно что она сработает.
Вот реализация (одна из) функции quicksort на языке С:

void qsort(int a[], int lo, int hi) {
{
  int h, l, p, t;

  if (lo < hi) {
    l = lo;
    h = hi;
    p = a[hi];

    do {
      while ((l < h) && (a[l] <= p)) 
          l = l+1;
      while ((h > l) && (a[h] >= p))
          h = h-1;
      if (l < h) {
          t = a[l];
          a[l] = a[h];
          a[h] = t;
      }
    } while (l < h);

    t = a[l];
    a[l] = a[hi];
    a[hi] = t;

    qsort( a, lo, l-1 );
    qsort( a, l+1, hi );
  }
}

Длинно, непонятно, и только для массива целых чисел, для других типов придется писать свою или обобщать эту. Кстати, вот императивная реализация того же на Haskell. Еще более некрасиво...

Очевидно что на Haskell получилось лучше, правда? Не совсем...
По коду на С видно (ок, мне видно) что дополнительной памяти в процессе сортировки не выделяется хотя стек растет. Впрочем этого(роста стека) можно было бы и избежать (частично).

Можно ли сказать это про реализацию на Haskell?

Далее...как ни странно но реализаций алгоритма quicksort может быть больше одной... Например реализуя руками этот алгоритм я привык брать в качестве "опорного" элемента элемент из серидины массива. Ну да это мелочь...А вот что более существенно:

Неправильный qsort() в Solaris

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

Вот по ссылке для других OS (смотреть только на общую "тенденцию", эксперемент был не на скорость).

Операционная система	хорошая	плохая	разница
FreeBSD 4.3	1.6	1.2	0.8
Linux RedHat 6.2	3.5	3.0	0.9
Windows NT 4.0 SP5	2	12	6.0
Solaris 7, x86	3.0	65.0	22.0
Solaris 8, x86	2.6	62.0	24.0

В обоих случаях на Solaris "плохая" программа выполняется существенно медленнее.
Оказывается, из-за этого под Solaris'ом очень медленно работают запросы PostgreSQL с сортировкой.

Кстати на NT та же проблема. Как сейчас не знаю, не проверял.

Выводы - иногда на алгоритмы накладываются дополнительные требования (основное - чтобы алгоритм работал). Как правило это требования по скорости, по памяти, по использованию каких-либо других ресурсов, по сложности. Используя С для реализации алгоритма quicksort я на эти вопросы ответить могу. Используя Haskell - нет.