OberonCore https://forum.oberoncore.ru/ |
|
Haskell подсчитать длину списка. https://forum.oberoncore.ru/viewtopic.php?f=72&t=1707 |
Страница 1 из 5 |
Автор: | Alexey Veselovsky [ Понедельник, 22 Июнь, 2009 11:40 ] |
Заголовок сообщения: | Haskell подсчитать длину списка. |
Немножко вот почитал статью про хаскель на ночь глядя. Заодно попробовал немножно с ним поэкспериментировать. Взял пример: подсчет числа элементов в списке: Код: length [] = 0 length (x,xs) = 1 + length(xs) main = print (length [1..1000000]) Программа радостно вылетает из за переполнения стэка. Немножко почитал про подобные проблемы, вроде как что-то где-то переполняется из за ленивости. Попробовал ленивость запретить. Код: length [] = 0 length (x,xs) = (+) 1 $! length(xs) main = print (length [1..1000000]) Результат ровно тот же самый. PS. Просьба сильно не пинать, с хаскелем знаком 3 часа как |
Автор: | Info21 [ Понедельник, 22 Июнь, 2009 13:16 ] |
Заголовок сообщения: | Re: Haskell подсчитать длину списка. |
Alexey Veselovsky писал(а): ... Заодно попробовал немножно с ним поэкспериментировать. Обязательно нужно. Для усиления любви к Оберону.
|
Автор: | PGR [ Понедельник, 22 Июнь, 2009 20:48 ] |
Заголовок сообщения: | Re: Haskell подсчитать длину списка. |
Alexey Veselovsky писал(а): Программа радостно вылетает из за переполнения стэка. Немножко почитал про подобные проблемы, вроде как что-то где-то переполняется из за ленивости. Поможет хвостовая рекурсия, а ленивость спасает только от создания огромного списка. Код: len n [] = n
len n (x:xs) = len (n+1) xs length x = len 0 x |
Автор: | Alexey Veselovsky [ Понедельник, 22 Июнь, 2009 21:18 ] |
Заголовок сообщения: | Re: Haskell подсчитать длину списка. |
Ага. Спасибо. Я то, откровенно говоря, думал что умный компилятор столь тривиальный пример сам преобразует в хвостовую рекурсию. Хотя бы на -O3 степени оптимизации. |
Автор: | Илья Ермаков [ Вторник, 23 Июнь, 2009 07:34 ] |
Заголовок сообщения: | Re: Haskell подсчитать длину списка. |
Фигушки, хвостовую надо писать явно, а для этого имитировать переменную-счётчик специальным параметром, который ФПисты называют аккумулятором. Т.е. обычный цикл с переменной, выраженный через ... |
Автор: | Geniepro [ Вторник, 23 Июнь, 2009 08:49 ] |
Заголовок сообщения: | Re: Haskell подсчитать длину списка. |
Alexey Veselovsky писал(а): Программа радостно вылетает из за переполнения стэка. Немножко почитал про подобные проблемы, вроде как что-то где-то переполняется из за ленивости. Попробовал ленивость запретить. ... Результат ровно тот же самый. Тут проблема не в ленивости, а в нехвостовой рекурсии. Кстати, в примере от PGR как раз уже из-за ленивости может тоже произойти проблема -- откладывание вычислений (n+1). Но это уже компилятор оптимизирует. Виртуальная машина LLVM может оптимизировать такие случаи, например, простой (экспоненциальный) вариант функции фибоначчи она переводит в итеративный вариант. К сожалению, для Хаскелла связка с LLVM пока есть только для всяких там линуксов, под виндой у меня не получилось... Вообще, в данном случае, раз Вы пробегаетесь по всему списку с какой-то накапливаемой переменной, то это лучше оформить как свёртку списка (fold, reduce), например так: Код: length' xs = foldl (\n _ -> n+1) 0 xs
|
Автор: | Geniepro [ Вторник, 23 Июнь, 2009 08:54 ] |
Заголовок сообщения: | Re: Haskell подсчитать длину списка. |
Info21 писал(а): Для усиления любви к Оберону. Эх, ещё бы было за что его любить.Вот говорят -- выбирай не дом, а соседей. Так же и тут -- выбирай не язык, а сообщество вокруг него... |
Автор: | Info21 [ Вторник, 23 Июнь, 2009 09:26 ] |
Заголовок сообщения: | Re: Haskell подсчитать длину списка. |
Geniepro писал(а): Info21 писал(а): Для усиления любви к Оберону. Эх, ещё бы было за что его любить.Geniepro писал(а): Вот говорят -- выбирай не дом, а соседей. Так же и тут -- выбирай не язык, а сообщество вокруг него... Еще говорят: держись подальше от дураков.
|
Автор: | PGR [ Вторник, 23 Июнь, 2009 10:04 ] |
Заголовок сообщения: | Re: Haskell подсчитать длину списка. |
Alexey Veselovsky писал(а): Ага. Спасибо. Я то, откровенно говоря, думал что умный компилятор столь тривиальный пример сам преобразует в хвостовую рекурсию. Хотя бы на -O3 степени оптимизации. Даже нефункциональный GCC преобразовывает в цикл первый вариант функции с нехвостовой рекурсией. GHC есть куда расти |
Автор: | Alexey Veselovsky [ Вторник, 23 Июнь, 2009 10:14 ] |
Заголовок сообщения: | Re: Haskell подсчитать длину списка. |
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 Ну, понятно что этот пример суть велосипед. Однако вон сколько интересного (для меня) выяснилось на нем. В каком-то коде делающем что-то полезное естественно лучше пользоваться стандартнобиблиотечными функциями. |
Автор: | Geniepro [ Вторник, 23 Июнь, 2009 10:58 ] |
Заголовок сообщения: | Re: Haskell подсчитать длину списка. |
PGR писал(а): Даже нефункциональный GCC преобразовывает в цикл первый вариант функции с нехвостовой рекурсией. GHC есть куда расти Что любопытно, GHC ведь содержит в себе GCC (хотя его вроде пытаются заменить на С--), но вот в этой программе эта GCC-шная оптимизация (если она и правда есть) не сработала...Попробовал такой вариант: Код: #include <stdio.h> Скомпилировал через GCC -- программа вываливается с сообщением "C stack overflow in generated code"
int f(int n) { return (n == 0) ? 0 : (1 + f(n-1)); } void cmain(void) { printf("%d\n", f(1000000)); } |
Автор: | Alexey Veselovsky [ Вторник, 23 Июнь, 2009 10:59 ] |
Заголовок сообщения: | Re: Haskell подсчитать длину списка. |
Geniepro писал(а): Скомпилировал через GCC -- программа вываливается с сообщением "C stack overflow in generated code" Оптимизация -O3 ? |
Автор: | Geniepro [ Вторник, 23 Июнь, 2009 11:04 ] |
Заголовок сообщения: | Re: Haskell подсчитать длину списка. |
Alexey Veselovsky писал(а): Код: length xs = len xs 0 where len [] acc = acc len (x:xs) acc = len xs $! (1 + acc) Что такое есть "$!" я, честно говоря, ещё не понимаю Это тот же самый код, что у PGR, только указано явное форсирование вычисление инкремента переменной, накапливающей размер списка (для этого и указана операция $! -- она и форсирует это вычисление)... |
Автор: | Geniepro [ Вторник, 23 Июнь, 2009 11:05 ] |
Заголовок сообщения: | Re: Haskell подсчитать длину списка. |
Alexey Veselovsky писал(а): Geniepro писал(а): Скомпилировал через GCC -- программа вываливается с сообщением "C stack overflow in generated code" Оптимизация -O3 ? -O2, -O3 -- разницы нет... |
Автор: | Alexey Veselovsky [ Вторник, 23 Июнь, 2009 11:08 ] |
Заголовок сообщения: | Re: Haskell подсчитать длину списка. |
Geniepro писал(а): Alexey Veselovsky писал(а): Geniepro писал(а): Скомпилировал через GCC -- программа вываливается с сообщением "C stack overflow in generated code" Оптимизация -O3 ? -O2, -O3 -- разницы нет... Версия компилятора какая? |
Автор: | Geniepro [ Вторник, 23 Июнь, 2009 11:11 ] |
Заголовок сообщения: | Re: Haskell подсчитать длину списка. |
Alexey Veselovsky писал(а): Версия компилятора какая? GHC 6.10.2, в нём gcc version 3.4.5 (mingw-vista special r3)
|
Автор: | Alexey Veselovsky [ Вторник, 23 Июнь, 2009 11:14 ] |
Заголовок сообщения: | Re: Haskell подсчитать длину списка. |
Geniepro писал(а): Alexey Veselovsky писал(а): Версия компилятора какая? GHC 6.10.2, в нём gcc version 3.4.5 (mingw-vista special r3)Ну, это ж древность страшная (я про gcc) До дому доберусь, посмотрю что там на 4.3 будет. |
Автор: | Valery Solovey [ Вторник, 23 Июнь, 2009 11:38 ] |
Заголовок сообщения: | Re: Haskell подсчитать длину списка. |
А у оператора "$!" какое-нибудь конкретное название есть? Чтобы было удобно в разговорной речи: "Здесь используйте оператор сложения, здесь - оператор присваивания, а здесь ...". Да и для более чёткого его понимания краткое название (в одно-два слова) не повредит. |
Автор: | Geniepro [ Вторник, 23 Июнь, 2009 11:54 ] |
Заголовок сообщения: | Re: Haskell подсчитать длину списка. |
Valery Solovey писал(а): А у оператора "$!" какое-нибудь конкретное название есть? Вот даже не задавался таким вопросом. Эта операция реализована так:Код: -- | Strict (call-by-value) application, defined in terms of 'seq'. то есть строгое применение, как-то так...($!) :: (a -> b) -> a -> b f $! x = x `seq` f x http://www.haskell.org/hoogle/?hoogle=%24%21 |
Автор: | PGR [ Вторник, 23 Июнь, 2009 11:57 ] |
Заголовок сообщения: | Re: Haskell подсчитать длину списка. |
Alexey Veselovsky писал(а): До дому доберусь, посмотрю что там на 4.3 будет. GCC 4.4Код: typedef struct item item; struct item { int n; item *next; }; int len(item *i) { return (i==0) ? 0 : 1+len(i->next); } Код: _len:
mov edx, DWORD PTR [esp+4] test edx, edx je L8 mov ecx, 1 L4: mov edx, DWORD PTR [edx+4] mov eax, ecx add ecx, 1 test edx, edx jne L4 ret L8: xor eax, eax ret |
Страница 1 из 5 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |