А ты думал, если пишешь на хаскеле, то код автоматически становится самым оптимальным и безошибочным?

Ну, безошибочности от того, кто пишет «самым оптимальным» ожидать не приходится, конечно.

А вообще, Набоков, помнится, долго удивлялся, что по-английски тоже можно сказать глупость.

спасибо

согласен, спасибо за поправку

С тегом «быдлокод» это прямо в точку, откройте для себя свёртки и хвостовую рекурсию.

max' = foldl max 0

зато у автора ход хотя бы выдаёт правильный результат хоть и за экспоненциальное время

λ> let max' = foldl max 0
λ> max' [-1,-2,-3]
0

кстати, вопрос, имеет ли смысл использовать foldl1, а не foldr ведь функия поиска максимума монолитная?

имеет ли смысл использовать foldl1, а не foldr ведь функия поиска максимума монолитная?

Монолитная это как? Если написать maximum = foldr1 max, то стек довольно быстро будет кушаться гигабайтами, в base maximum написан как maximum = foldl1 max при этом для Int / Integer есть RULES которые используют строгую версии maximum = foldl1' max (max тут тоже строгий).

Нет, но имеет смысл foldl1' (благодаря коммутативности): http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl'

Магея

-- | max.hs

import System.Environment

mx :: Ord a => [a] -> a
mx (x:[]) = x
mx (x:xs) = if x > mx xs then x else mx xs

main :: IO ()
main = do
  n :: Int <- fmap (read . head) getArgs
  print $ mx [1 .. n]

/* max.c */

#include <stdio.h>
#include <stdlib.h>

int mx(int **xs)
{
    if (*(xs + 1) == NULL)
        return **xs;
    else
        if (**xs > mx(xs + 1))
            return **xs;
        else
            return mx(xs + 1);
}

int main(int argc, char **argv)
{
    int i, n = atoi(argv[1]);
    int **xs = malloc((1 + n) * sizeof(int*));

    for (i = 0; i < n; i++) {
        xs[i] = malloc(sizeof(int));
        *xs[i] = i + 1;
    }

    xs[++i] = NULL;

    printf("%i\n", mx(xs));
}

$ gcc -O3 max.c -o max-gcc
$ clang -O3 max.c -o max-clang
$ ghc -XScopedTypeVariables -O3 max.hs -o max-ghc
$ jhc max.hs -o max-jhc
$ time ./max-clang 25
25

real	0m0.359s
user	0m0.356s
sys	0m0.000s
$ time ./max-clang 30
30

real	0m10.801s
user	0m10.789s
sys	0m0.000s
$ time ./max-jhc 25
25

real	0m0.326s
user	0m0.324s
sys	0m0.000s
$ time ./max-jhc 30
30

real	0m10.603s
user	0m10.373s
sys	0m0.000s
$ time ./max-gcc 25
25

real	0m0.122s
user	0m0.120s
sys	0m0.000s
$ time ./max-gcc 30
30

real	0m3.745s
user	0m3.732s
sys	0m0.000s
$ time ./max-gcc 35
35

real	1m59.943s
user	1m59.383s
sys	0m0.008s
$ time ./max-ghc 25
25

real	0m0.003s
user	0m0.000s
sys	0m0.000s
$ time ./max-ghc 30
30

real	0m0.003s
user	0m0.000s
sys	0m0.000s
$ time ./max-ghc 35
35

real	0m0.003s
user	0m0.000s
sys	0m0.000s
$ time ./max-ghc 1000
1000

real	0m0.003s
user	0m0.000s
sys	0m0.000s
$ ./max-ghc 1000000
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

clang (2.8) < jhc (0.7.7) < gcc (4.5.2) << ghc (7.4.1).

valgrind ./max-gcc 25

More than 10000000 total errors detected. I'm not reporting any more. Final error counts will be inaccurate. Go fix your program!

ЧЯДНТ явно.

    int **xs = malloc((1 + n) * sizeof(int*));

    for (i = 0; i < n; i++) {
        xs[i] = malloc(sizeof(int));
        *xs[i] = i + 1;
    }

Божимой, это развидеть хочу я.

ghc -XScopedTypeVariables -O3 max.hs -o max-ghc

Интересно. С -O3 действительно оптимизируется до O(n) алгоритма. Зря я вчера гнал на ghc.

С -O3 действительно оптимизируется до O(n) алгоритма. Зря я вчера гнал на ghc.

Дело не в -O3, а в n :: Int, т.е. для fixnum-ов он что-то оптимизирует, для больших чисел (Integer) - нет.

Дело не в -O3, а в n :: Int

Если быть точным, дело и в том, и в другом.

More than 10000000 total errors detected. I'm not reporting any more. Final error counts will be inaccurate. Go fix your program!

Ok,

-    xs[++i] = NULL;
+    xs[i] = NULL;

ERROR SUMMARY: 0 errors from 0 contexts

Божимой, это развидеть хочу я.

Всё хорошо, просьба не паниковать :)

Не ну я понимаю, что это делалось ради if (*(xs + 1) == NULL) , но всё равно производит жуткое впечатление. :}

Если быть точным, дело и в том, и в другом.

С -O1 и -O2 точно также, только с -O0 тормозит. Ну и GHCi будет тормозить, так как интерпретатор.

но всё равно производит жуткое впечатление. :}

Прямым аналогом были бы нормальные linked lists, но мне захотелось сделать массив указателей на int-ы.

С -O1 и -O2 точно также

Значит я совсем выпал из реальности: мне казалось, что я вчера с -O2 собирал. Спать больше надо.

У такой реализации большое преимущество за счёт пространственной локальности, кеширования и т.д.

мне казалось, что я вчера с -O2 собирал

Может версия другая, у меня 7.4.1.

зато у автора ход хотя бы выдаёт правильный результат хоть и за экспоненциальное время

Твоя правда, я наивно хотел таким образом элегантно уйти от проблемы пустого списка :3
Ну ОК, будет через foldl1.

Монолитная (molithic) (По Окасаки) имелось ввиду, что единожды запущенная функция вычисляется до конца, таким образом все thunk, которые создаются излишни. В противовес инкрементальной (incremental) которая возвращает часть значения или thunk, например это будут все map, filter, ++ и т.п.