OberonCore • - Haskell подсчитать длину списка.

Сообщения без ответов | Активные темы

Список форумов » Разное » Другие вопросы по программированию » Функциональное программирование

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

Haskell подсчитать длину списка.

Страница 1 из 5

[ Сообщений: 91 ]

На страницу 1, 2, 3, 4, 5 След.

Версия для печати

Пред. тема | След. тема

Автор

Сообщение

Alexey Veselovsky

Заголовок сообщения: 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 часа как ;-)

Вернуться к началу

Info21

Заголовок сообщения: Re: Haskell подсчитать длину списка.

Добавлено: Понедельник, 22 Июнь, 2009 13:16

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва

Alexey Veselovsky писал(а):

... Заодно попробовал немножно с ним поэкспериментировать.

Обязательно нужно. Для усиления любви к Оберону.

Вернуться к началу

PGR

Заголовок сообщения: 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

Вернуться к началу

Alexey Veselovsky

Заголовок сообщения: Re: Haskell подсчитать длину списка.

Добавлено: Понедельник, 22 Июнь, 2009 21:18

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

Ага. Спасибо. Я то, откровенно говоря, думал что умный компилятор столь тривиальный пример сам преобразует в хвостовую рекурсию. Хотя бы на -O3 степени оптимизации.

Вернуться к началу

Илья Ермаков

Заголовок сообщения: Re: Haskell подсчитать длину списка.

Добавлено: Вторник, 23 Июнь, 2009 07:34

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл

Фигушки, хвостовую надо писать явно, а для этого имитировать переменную-счётчик специальным параметром, который ФПисты называют аккумулятором. Т.е. обычный цикл с переменной, выраженный через ...

Вернуться к началу

Geniepro

Заголовок сообщения: 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

Вернуться к началу

Geniepro

Заголовок сообщения: Re: Haskell подсчитать длину списка.

Добавлено: Вторник, 23 Июнь, 2009 08:54

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

Info21 писал(а):

Для усиления любви к Оберону.

Эх, ещё бы было за что его любить.
Вот говорят -- выбирай не дом, а соседей. Так же и тут -- выбирай не язык, а сообщество вокруг него...

Вернуться к началу

Info21

Заголовок сообщения: Re: Haskell подсчитать длину списка.

Добавлено: Вторник, 23 Июнь, 2009 09:26

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва

Geniepro писал(а):

Info21 писал(а):

Для усиления любви к Оберону.

Эх, ещё бы было за что его любить.

Его не за что не любить. В отличие от разных других порождений коллективного комбинаторного умотипа.

Geniepro писал(а):

Вот говорят -- выбирай не дом, а соседей. Так же и тут -- выбирай не язык, а сообщество вокруг него...

Еще говорят: держись подальше от дураков.

Вернуться к началу

PGR

Заголовок сообщения: Re: Haskell подсчитать длину списка.

Добавлено: Вторник, 23 Июнь, 2009 10:04

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

Alexey Veselovsky писал(а):

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

Вернуться к началу

Alexey Veselovsky

Заголовок сообщения: Re: Haskell подсчитать длину списка.

Добавлено: Вторник, 23 Июнь, 2009 10:14

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

Geniepro писал(а):

Alexey Veselovsky писал(а):

Я немного поэкспериментировал + задал вопрос на 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 пока есть только для всяких там линуксов, под виндой у меня не получилось...

Ну, винда лично мне не интересна ;-)

Цитата:

Код:

length' xs = foldl (\n _ -> n+1) 0 xs

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

Вернуться к началу

Geniepro

Заголовок сообщения: Re: Haskell подсчитать длину списка.

Добавлено: Вторник, 23 Июнь, 2009 10:58

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

PGR писал(а):

Что любопытно, 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

Заголовок сообщения: Re: Haskell подсчитать длину списка.

Добавлено: Вторник, 23 Июнь, 2009 10:59

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

Geniepro писал(а):

Скомпилировал через GCC -- программа вываливается с сообщением "C stack overflow in generated code"

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

Вернуться к началу

Geniepro

Заголовок сообщения: 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, только указано явное форсирование вычисление инкремента переменной, накапливающей размер списка (для этого и указана операция $! -- она и форсирует это вычисление)...

Вернуться к началу

Geniepro

Заголовок сообщения: Re: Haskell подсчитать длину списка.

Добавлено: Вторник, 23 Июнь, 2009 11:05

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

Alexey Veselovsky писал(а):

Geniepro писал(а):

Скомпилировал через GCC -- программа вываливается с сообщением "C stack overflow in generated code"

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

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

Вернуться к началу

Alexey Veselovsky

Заголовок сообщения: 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 -- разницы нет...

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

Вернуться к началу

Geniepro

Заголовок сообщения: 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)

Вернуться к началу

Alexey Veselovsky

Заголовок сообщения: 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 будет.

Вернуться к началу

Valery Solovey

Заголовок сообщения: Re: Haskell подсчитать длину списка.

Добавлено: Вторник, 23 Июнь, 2009 11:38

Зарегистрирован: Понедельник, 30 Июль, 2007 10:53
Сообщения: 1538
Откуда: Беларусь, Минск

А у оператора "$!" какое-нибудь конкретное название есть? Чтобы было удобно в разговорной речи: "Здесь используйте оператор сложения, здесь - оператор присваивания, а здесь ...". Да и для более чёткого его понимания краткое название (в одно-два слова) не повредит.

Вернуться к началу

Geniepro

Заголовок сообщения: 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

Вернуться к началу

PGR

Заголовок сообщения: 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

Вернуться к началу

Страница 1 из 5

[ Сообщений: 91 ]

На страницу 1, 2, 3, 4, 5 След.

Список форумов » Разное » Другие вопросы по программированию » Функциональное программирование

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

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

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

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