Привет,

Возникла проблема с массивами в haskell

Имею следующий код (ужатый и выхолощенный до минимума, всё ещё содерщего проблему, так что смысла в нём прошу не искать )

module Main
where

import Data.Array
import Data.Foldable

main :: IO ()
main = print (res arr)

res :: Array Int Int
--res a = Prelude.foldl (+) 0 (elems a)
res = Data.Foldable.foldl (+) 0

arr :: Array Int Int
arr = listArray (0, 100000) (repeat 42)

В таком виде код приводит к

Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize' to increase it.

Видимо, рекурсия, не сводимая к хвостовой. Но если поменять определение res на закоментированное, то код отрабатывает успешно.
Вопрос: откуда рекурсия в Data.Foldable.foldl?

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

SV>res = Data.Foldable.foldl (+) 0
SV>Вопрос: откуда рекурсия в Data.Foldable.foldl?

попробуй foldl' (с кавычкой). вообще говорят что foldl исполоьзовать бессмысленно, всегда лучше foldr или foldl'. наверняка дело в том, что foldl создаёт большой невычисленный thunk и стек переполняется на его вычислении

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

SV>res :: Array Int Int

Виноват,
res :: Array Int Int -> Int

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

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

SV>>res = Data.Foldable.foldl (+) 0
SV>>Вопрос: откуда рекурсия в Data.Foldable.foldl?

BZ>попробуй foldl' (с кавычкой). вообще говорят что foldl исполоьзовать бессмысленно, всегда лучше foldr или foldl'. наверняка дело в том, что foldl создаёт большой невычисленный thunk и стек переполняется на его вычислении

Тогда почему Prelude.foldl не падает?

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

SV>Тогда почему Prelude.foldl не падает?

да, что-то я мимо сказал, как раз по моему обхяснению он и должен. посмотри реализацию данного Foldable.foldl, в конце концов дело в ней

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

SV>Видимо, рекурсия, не сводимая к хвостовой. Но если поменять определение res на закоментированное, то код отрабатывает успешно.
SV>Вопрос: откуда рекурсия в Data.Foldable.foldl?

Мой опыт: НЕ падает на Data.Foldable.foldl; падает, если длину массива увеличить в 10 раз, но тогда падает и Prelude.foldl.

Здравствуйте, SolVolkov,

Кстати о птичках: судя по исходнику Data.Foldable, функция Data.Foldable.fold для массивов определена примерно так же, как и у тебя — только у тебя 0 и (+), а у них mempty и mappend.

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

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

SV>>Видимо, рекурсия, не сводимая к хвостовой. Но если поменять определение res на закоментированное, то код отрабатывает успешно.
SV>>Вопрос: откуда рекурсия в Data.Foldable.foldl?

MM>Мой опыт: НЕ падает на Data.Foldable.foldl; падает, если длину массива увеличить в 10 раз, но тогда падает и Prelude.foldl.

Хм... Может ты без оптимизации компилил? С "-O" Prelude.foldl падать не должет. (ghc 6.10.4; OpenSUSE 11.0, x86_64)
А длинна, при которой падает, естественно, зависит.

Здравствуйте, Аноним, Вы писали:

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

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

SV>>>Видимо, рекурсия, не сводимая к хвостовой. Но если поменять определение res на закоментированное, то код отрабатывает успешно.
SV>>>Вопрос: откуда рекурсия в Data.Foldable.foldl?

MM>>Мой опыт: НЕ падает на Data.Foldable.foldl; падает, если длину массива увеличить в 10 раз, но тогда падает и Prelude.foldl.

А>Хм... Может ты без оптимизации компилил? С "-O" Prelude.foldl падать не должет. (ghc 6.10.4; OpenSUSE 11.0, x86_64)
А>А длинна, при которой падает, естественно, зависит.

Это был я...

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

SV>Здравствуйте, Аноним, Вы писали:

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

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

SV>>>>Видимо, рекурсия, не сводимая к хвостовой. Но если поменять определение res на закоментированное, то код отрабатывает успешно.
SV>>>>Вопрос: откуда рекурсия в Data.Foldable.foldl?

MM>>>Мой опыт: НЕ падает на Data.Foldable.foldl; падает, если длину массива увеличить в 10 раз, но тогда падает и Prelude.foldl.

А>>Хм... Может ты без оптимизации компилил? С "-O" Prelude.foldl падать не должет. (ghc 6.10.4; OpenSUSE 11.0, x86_64)
А>>А длинна, при которой падает, естественно, зависит.

SV>Это был я...

Я вообще не компилил, я в ghci проверял.

Проверил оптимизацию. С -O, действительно, наблюдается описанное тобой поведение. С -O2 — ничего не падает. Возможно, стоит в haskell-café спросить?

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

SV>Тогда почему Prelude.foldl не падает?

Я думаю, потому что strictness analyzer работает. Если его выключить — то все отлично падает. А Data.Foldable.foldl он просто не съедает.