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>

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"

Автор:  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/