[Haskell] Подсчитать длину списка. - Декларативное программирование

Здравствуйте, valexey, Вы писали:

V>Читаю вот статью "мягкое введение в Haskell", решил попробовать один из примеров, а именно -- подсчет длины списка.

V>

V>length                  :: [a] -> Integer
V>length []               =  0
V>length (x:xs)           =  1 + length xs

V>main = print (length [1..10000000])
V>

V>Компилирую это дело ghc -03, запускаю, через некоторое время вывалиевается из за переполнения стэка:

Правильно делает. Для thunk'а 1+1+1+...+1 (10000000 раз) никакой памяти не хватит.

V>Это как-то лечится (кроме увеличения стэка)?

Рекурсию — в хвостовую, а затем форсировать. Например, так

length xs = len xs 0 where  
              len []     acc = acc
              len (x:xs) acc = len xs $! (1 + acc)

Но лучше использовать стандартные функции

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

Здравствуйте, deniok, Вы писали:

D>Правильно делает. Для thunk'а 1+1+1+...+1 (10000000 раз) никакой памяти не хватит.

Непонятно, почему не сделана простейшая оптимизация.

D>Рекурсию — в хвостовую, а затем форсировать. Например, так

Можно и не форсировать.

... << RSDN@Home 1.2.0 alpha 4 rev. 1218>>

Здравствуйте, Буравчик, Вы писали:

Б>Здравствуйте, deniok, Вы писали:

D>>Правильно делает. Для thunk'а 1+1+1+...+1 (10000000 раз) никакой памяти не хватит.

Б>Непонятно, почему не сделана простейшая оптимизация.

В чем должна заключаться оптимизация — можно точно сформулировать?

D>>Рекурсию — в хвостовую, а затем форсировать. Например, так

Б>Можно и не форсировать.

Можно, но если хочется избавиться от stack overflow, то придется

Prelude Data.List> let length xs = len' xs 0 where  {len' [] acc = acc;  len' (x
:xs) acc = len' xs $! (1 + acc)}
Prelude Data.List> length [1..1000000]
1000000
Prelude Data.List> let lengthNotForce xs = len' xs 0 where  {len' [] acc = acc;
 len' (x:xs) acc = len' xs (1 + acc)}
Prelude Data.List> lengthNotForce [1..1000000]
*** Exception: stack overflow

Здравствуйте, deniok, Вы писали:

Б>>Непонятно, почему не сделана простейшая оптимизация.

D>В чем должна заключаться оптимизация — можно точно сформулировать?

Нельзя

Поспешил я. Показалось, что здесь можно было бы догадаться ввести аккумулятор.
Но, получается, что в общем случае это сделать проблематично. Я подумаю над этим

Б>>Можно и не форсировать.

D>Можно, но если хочется избавиться от stack overflow, то придется

Ну, с ключами -O3 и -O2 stack overflow не вылезает. Я проверил

... << RSDN@Home 1.2.0 alpha 4 rev. 1218>>

Здравствуйте, Буравчик, Вы писали:

Б>Ну, с ключами -O3 и -O2 stack overflow не вылезает. Я проверил

Ну, мы конечно верим в GHC team и в их strictness analyzer, но всё же -On на мой вкус недостаточно документированы. Чего бы не подсказать компилятору, где можно/нужно форсировать.

Здравствуйте, deniok, Вы писали:

D>Рекурсию — в хвостовую, а затем форсировать. Например, так ...

А всё-таки почему GHC до сих пор не умеет сам преобразовывать такие примитивные случаи рекурсии? Да же какой-нить GCC, не говоря уж про LLVM, это умеют...

Здравствуйте, geniepro, Вы писали:

D>>Рекурсию — в хвостовую, а затем форсировать. Например, так ...

G>А всё-таки почему GHC до сих пор не умеет сам преобразовывать такие примитивные случаи рекурсии? Да же какой-нить GCC, не говоря уж про LLVM, это умеют...

в gcc есть strictness analyzer?

вообще-то причина ровно одна — ghc комипилирует более высокоуровневый язык. и утверждать, что gcc умеет это оптимизировать — всё равно что говорить, что это умеет делать gas

Здравствуйте, geniepro, Вы писали:
G>А всё-таки почему GHC до сих пор не умеет сам преобразовывать такие примитивные случаи рекурсии? Да же какой-нить GCC, не говоря уж про LLVM, это умеют...
Gcc умеет превращать рекурсивный процесс в итеративный (т.е. убирать рост control context)?
Или ты про необходимость форсить в хаскеле даже в случае хвостовой рекурсии.

Здравствуйте, geniepro, Вы писали:

G>Здравствуйте, deniok, Вы писали:

D>>Рекурсию — в хвостовую, а затем форсировать. Например, так ...

G>А всё-таки почему GHC до сих пор не умеет сам преобразовывать такие примитивные случаи рекурсии? Да же какой-нить GCC, не говоря уж про LLVM, это умеют...

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

genieproMorphism _ ini _    []     = ini
genieproMorphism f ini step (_:xs) = f step (genieproMorphism f ini step xs)
-- при этом, кстати
length' = genieproMorphism (+) 0 1

Легко понять, что все это разворачивается в

step `f` (step `f` (step `f` (... (step `f` (step `f` ini))...)))

О! Вспоминая, что

foldr f ini [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` ini)...)

заключаем, что наш морфизм — частный случай катаморфизма; слегка подумав, выражаем его через foldr.

genieproMorphism f step = foldr (f . const step)
-- или так
genieproMorphism f step = foldr (\_ acc -> f step acc)

Ну foldr к foldl' свести, мягко говоря, не очень просто, здесь даже анализатора строгости не хватит, ещё для f нужен будет анализатор ассоциативности.

Может не стоило обобщать всё до полного катаморфизма? Вычисления в исходном примере могут начаться, только когда мы, пробежав весь список, дойдем до ini (увязанного в данном примере с концом списка). А то, что (step `f` ini) можно выполнить над началом списка, а дальше применять (step `f`) к результату над каждым следующим элементом и получить то же самое — это некоторый тонкий факт, связанный с тем, что мы в действительности игнорируем сами элементы списка. Пожалуй подобную оптимизацию действительно можно было бы сделать, поскольку здесь мы имеем дело с истинным полиморфизмом: в типе

genieproMorphism :: (a -> b -> b) -> a -> b -> [t] -> b

тип t стоит под квантором общности. Итак: допустима замена

\f step -> foldr (\_ acc -> f step acc)
-- на
\f step -> foldl (\acc _ -> f step acc)

которая, конечно, имеет смысл, если в дальнейшем анализатор строгости решит заменить foldl на foldl'.

Здравствуйте, deniok, Вы писали:

D>Итак: допустима замена
D>

D>\f step -> foldr (\_ acc -> f step acc)
D>-- на
D>\f step -> foldl (\acc _ -> f step acc)
D>

D>которая, конечно, имеет смысл, если в дальнейшем анализатор строгости решит заменить foldl на foldl'.

Ну, конечно, можно упростить: допустима замена

\g -> foldr (\_ acc -> g acc)
-- на
\g -> foldl (\acc _ -> g acc)

Например

*Tst> (\g -> foldr (\_ acc -> g acc)) ((+)2) 3 [1..999]
2001
*Tst> (\g -> foldl (\acc _ -> g acc)) ((+)2) 3 [1..999]
2001
*Tst> (\g -> foldr (\_ acc -> g acc)) ((-)2) 3 [1..999]
-1
*Tst> (\g -> foldl (\acc _ -> g acc)) ((-)2) 3 [1..999]
-1

Здравствуйте, deniok, Вы писали:

[cut]
D>Ну foldr к foldl' свести, мягко говоря, не очень просто, здесь даже анализатора строгости не хватит, ещё для f нужен будет анализатор ассоциативности.

А вывести, что у нас тут Sum a, который моноид, в общем случае не получится? Хотя, блин, это и будет уже анализатор ассоциативности (если явно нигде ничего не указывать

)

Здравствуйте, deniok, Вы писали:

D>Можно, но если хочется избавиться от stack overflow, то придется

Здесь же явная хвостовая рекурсия. Почему GHC ее не превратил в цикл?

... << RSDN@Home 1.2.0 alpha 4 rev. 1218>>

Здравствуйте, Буравчик, Вы писали:

Б>Здравствуйте, deniok, Вы писали:

D>>Можно, но если хочется избавиться от stack overflow, то придется

Б>Здесь же явная хвостовая рекурсия. Почему GHC ее не превратил в цикл?

По-моему GHCi по умолчанию не оптимизирует, а чтобы превратить хвостовую рекурсию в цикл в ленивом языке надо еще провести strictness analysis. Иначе семантика может поменяться; да и эффективность упасть.

Здравствуйте, Mr.Cat, Вы писали:

MC>Gcc умеет превращать рекурсивный процесс в итеративный (т.е. убирать рост control context)?

Ну вот, на другом форуме на эту тему сообщили:

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

Здравствуйте, geniepro, Вы писали:
G>Ну вот, на другом форуме на эту тему сообщили:
G>GCC 4.4
Занятно. Интересно, насколько сложные случаи он может оптимизировать.

Б>Здесь же явная хвостовая рекурсия. Почему GHC ее не превратил в цикл?

А он превратил.

Тут выше был пример с gcc.

Так вот, сишный код получился, примерно, такой:

IntThunk ZeroThunk, OneThunk;
IntThunk length(ListThunk list) {
  return isNil(FORCE(list)) ? ZeroThunk : MkPlusThunk (OneThunk, length (tail(list)));
}

Это может быть превращено в цикл. За исключением, что вместо значения ты получишь вычисление этого значения, которое и упадёт на FORCE, что нужно для вывода.

	От:	valexey
	Дата:	22.06.09 17:56
	Оценка:

	От:	deniok
	Дата:	22.06.09 18:26
	Оценка:

	От:	Буравчик
	Дата:	22.06.09 18:45
	Оценка:

	От:	deniok
	Дата:	22.06.09 18:52
	Оценка:

	От:	Буравчик
	Дата:	22.06.09 19:18
	Оценка:

От:	geniepro	http://geniepro.livejournal.com/
Дата:	24.06.09 12:11
Оценка:

От:	Курилка	http://kirya.narod.ru/
Дата:	24.06.09 19:56
Оценка:

От:	thesz	http://thesz.livejournal.com
Дата:	25.06.09 13:35
Оценка: