Geniepro писал(а):
Alexey Veselovsky писал(а):
Программа радостно вылетает из за переполнения стэка. Немножко почитал про подобные проблемы, вроде как что-то где-то переполняется из за ленивости. Попробовал ленивость запретить. ... Результат ровно тот же самый.
Тут проблема не в ленивости, а в нехвостовой рекурсии.
Кстати, в примере от PGR как раз уже из-за ленивости может тоже произойти проблема -- откладывание вычислений (n+1). Но это уже компилятор оптимизирует.
Я немного поэкспериментировал + задал вопрос на rsdn. Выяснилось что вариант от PGR ведет себя весьма сильно по разному в разных реализациях или даже в одной реализации, но с разными настройками haskell'я:
1) Если собрать ghc (с настройками по умолчанию), то функция начинает со страшное силой кушать память (кучу, а не стэк). Соответственно если список достаточно длинный, то програмка влегкую откушивает весь стэк.
2) Если собрать ghc с -O3, то всё хорошо. Считает как надо.
3) В интерпретаторе переполнение стэка происходит в любом случае.
Чтобы такого небыло на rsdn предложили вот такой вариант:
Код:
length xs = len xs 0 where
len [] acc = acc
len (x:xs) acc = len xs $! (1 + acc)
Что такое есть "$!" я, честно говоря, ещё не понимаю
Цитата:
Виртуальная машина LLVM может оптимизировать такие случаи, например, простой (экспоненциальный) вариант функции фибоначчи она переводит в итеративный вариант. К сожалению, для Хаскелла связка с LLVM пока есть только для всяких там линуксов, под виндой у меня не получилось...
Ну, винда лично мне не интересна
Цитата:
Вообще, в данном случае, раз Вы пробегаетесь по всему списку с какой-то накапливаемой переменной, то это лучше оформить как свёртку списка (fold, reduce), например так:
Код:
length' xs = foldl (\n _ -> n+1) 0 xs
Ну, понятно что этот пример суть велосипед. Однако вон сколько интересного (для меня) выяснилось на нем. В каком-то коде делающем что-то полезное естественно лучше пользоваться стандартнобиблиотечными функциями.