OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Суббота, 07 Декабрь, 2019 19:04

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 91 ]  На страницу 1, 2, 3, 4, 5  След.
Автор Сообщение
 Заголовок сообщения: Haskell подсчитать длину списка.
СообщениеДобавлено: Понедельник, 22 Июнь, 2009 11:40 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Немножко вот почитал статью про хаскель на ночь глядя. Заодно попробовал немножно с ним поэкспериментировать.

Взял пример: подсчет числа элементов в списке:

Код:
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 часа как ;-)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Понедельник, 22 Июнь, 2009 13:16 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8209
Откуда: Троицк, Москва
Alexey Veselovsky писал(а):
... Заодно попробовал немножно с ним поэкспериментировать.
Обязательно нужно. Для усиления любви к Оберону.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Понедельник, 22 Июнь, 2009 20:48 

Зарегистрирован: Понедельник, 29 Январь, 2007 19:00
Сообщения: 370
Откуда: Украина, Запорожье
Alexey Veselovsky писал(а):
Программа радостно вылетает из за переполнения стэка. Немножко почитал про подобные проблемы, вроде как что-то где-то переполняется из за ленивости.

Поможет хвостовая рекурсия, а ленивость спасает только от создания огромного списка.
Код:
len n [] = n
len n (x:xs) = len (n+1) xs

length x = len 0 x


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Понедельник, 22 Июнь, 2009 21:18 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Ага. Спасибо. Я то, откровенно говоря, думал что умный компилятор столь тривиальный пример сам преобразует в хвостовую рекурсию. Хотя бы на -O3 степени оптимизации.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Вторник, 23 Июнь, 2009 07:34 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9161
Откуда: Россия, Орёл
Фигушки, хвостовую надо писать явно, а для этого имитировать переменную-счётчик специальным параметром, который ФПисты называют аккумулятором. Т.е. обычный цикл с переменной, выраженный через ... :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Вторник, 23 Июнь, 2009 08:49 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Alexey Veselovsky писал(а):
Программа радостно вылетает из за переполнения стэка. Немножко почитал про подобные проблемы, вроде как что-то где-то переполняется из за ленивости. Попробовал ленивость запретить. ... Результат ровно тот же самый.

Тут проблема не в ленивости, а в нехвостовой рекурсии.
Кстати, в примере от PGR как раз уже из-за ленивости может тоже произойти проблема -- откладывание вычислений (n+1). Но это уже компилятор оптимизирует.

Виртуальная машина LLVM может оптимизировать такие случаи, например, простой (экспоненциальный) вариант функции фибоначчи она переводит в итеративный вариант. К сожалению, для Хаскелла связка с LLVM пока есть только для всяких там линуксов, под виндой у меня не получилось... :(

Вообще, в данном случае, раз Вы пробегаетесь по всему списку с какой-то накапливаемой переменной, то это лучше оформить как свёртку списка (fold, reduce), например так:
Код:
length' xs = foldl (\n _ -> n+1) 0 xs


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Вторник, 23 Июнь, 2009 08:54 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Info21 писал(а):
Для усиления любви к Оберону.
Эх, ещё бы было за что его любить.
Вот говорят -- выбирай не дом, а соседей. Так же и тут -- выбирай не язык, а сообщество вокруг него...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Вторник, 23 Июнь, 2009 09:26 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8209
Откуда: Троицк, Москва
Geniepro писал(а):
Info21 писал(а):
Для усиления любви к Оберону.
Эх, ещё бы было за что его любить.
Его не за что не любить. В отличие от разных других порождений коллективного комбинаторного умотипа.

Geniepro писал(а):
Вот говорят -- выбирай не дом, а соседей. Так же и тут -- выбирай не язык, а сообщество вокруг него...
Еще говорят: держись подальше от дураков.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Вторник, 23 Июнь, 2009 10:04 

Зарегистрирован: Понедельник, 29 Январь, 2007 19:00
Сообщения: 370
Откуда: Украина, Запорожье
Alexey Veselovsky писал(а):
Ага. Спасибо. Я то, откровенно говоря, думал что умный компилятор столь тривиальный пример сам преобразует в хвостовую рекурсию. Хотя бы на -O3 степени оптимизации.

Даже нефункциональный GCC преобразовывает в цикл первый вариант функции с нехвостовой рекурсией. GHC есть куда расти :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Вторник, 23 Июнь, 2009 10:14 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
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

Ну, понятно что этот пример суть велосипед. Однако вон сколько интересного (для меня) выяснилось на нем. В каком-то коде делающем что-то полезное естественно лучше пользоваться стандартнобиблиотечными функциями.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Вторник, 23 Июнь, 2009 10:58 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
PGR писал(а):
Даже нефункциональный GCC преобразовывает в цикл первый вариант функции с нехвостовой рекурсией. GHC есть куда расти :)
Что любопытно, GHC ведь содержит в себе GCC (хотя его вроде пытаются заменить на С--), но вот в этой программе эта GCC-шная оптимизация (если она и правда есть) не сработала...

Попробовал такой вариант:
Код:
#include <stdio.h>

int f(int n)
{
    return (n == 0) ? 0 : (1 + f(n-1));
}

void cmain(void)
{
    printf("%d\n", f(1000000));
}
Скомпилировал через GCC -- программа вываливается с сообщением "C stack overflow in generated code"


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Вторник, 23 Июнь, 2009 10:59 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Geniepro писал(а):
Скомпилировал через GCC -- программа вываливается с сообщением "C stack overflow in generated code"


Оптимизация -O3 ?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Вторник, 23 Июнь, 2009 11:04 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Alexey Veselovsky писал(а):
Код:
length xs = len xs 0 where 
              len []     acc = acc
              len (x:xs) acc = len xs $! (1 + acc)

Что такое есть "$!" я, честно говоря, ещё не понимаю ;-)

Это тот же самый код, что у PGR, только указано явное форсирование вычисление инкремента переменной, накапливающей размер списка (для этого и указана операция $! -- она и форсирует это вычисление)...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Вторник, 23 Июнь, 2009 11:05 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Alexey Veselovsky писал(а):
Geniepro писал(а):
Скомпилировал через GCC -- программа вываливается с сообщением "C stack overflow in generated code"


Оптимизация -O3 ?

-O2, -O3 -- разницы нет...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Вторник, 23 Июнь, 2009 11:08 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Geniepro писал(а):
Alexey Veselovsky писал(а):
Geniepro писал(а):
Скомпилировал через GCC -- программа вываливается с сообщением "C stack overflow in generated code"


Оптимизация -O3 ?

-O2, -O3 -- разницы нет...


Версия компилятора какая?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Вторник, 23 Июнь, 2009 11:11 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
Alexey Veselovsky писал(а):
Версия компилятора какая?
GHC 6.10.2, в нём gcc version 3.4.5 (mingw-vista special r3)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Вторник, 23 Июнь, 2009 11:14 

Зарегистрирован: Вторник, 25 Апрель, 2006 16:21
Сообщения: 2180
Откуда: Нижний Новгород
Geniepro писал(а):
Alexey Veselovsky писал(а):
Версия компилятора какая?
GHC 6.10.2, в нём gcc version 3.4.5 (mingw-vista special r3)


Ну, это ж древность страшная ;-) (я про gcc)
До дому доберусь, посмотрю что там на 4.3 будет.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Вторник, 23 Июнь, 2009 11:38 

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск
А у оператора "$!" какое-нибудь конкретное название есть? Чтобы было удобно в разговорной речи: "Здесь используйте оператор сложения, здесь - оператор присваивания, а здесь ...". Да и для более чёткого его понимания краткое название (в одно-два слова) не повредит.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Вторник, 23 Июнь, 2009 11:54 

Зарегистрирован: Четверг, 12 Июль, 2007 23:18
Сообщения: 1982
Откуда: Узбекистан, Чирчик
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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Haskell подсчитать длину списка.
СообщениеДобавлено: Вторник, 23 Июнь, 2009 11:57 

Зарегистрирован: Понедельник, 29 Январь, 2007 19:00
Сообщения: 370
Откуда: Украина, Запорожье
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


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 91 ]  На страницу 1, 2, 3, 4, 5  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2019, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB