Haskell: эффективное выполнение последовательности действий

Можно поиметь хвостовую рекурсию, но тогда список окажется задом-наперед

Ну, в моей задаче порядок не важен, хотя интересно и более общее решение, сохраняющее порядок.
Попробовал преобразовать rollNDice по аналогии с достижением хвостовой рекурсии в чистых функциях:

rollNDice n | n < 0     = error "Negative sequence length"
            | n == 0    = return []
            | otherwise = rollAcc n []
                where
                  rollAcc 0 a = return a
                  rollAcc n a = do v <- rollDice
                                   rollAcc (n-1) (v:a)

но в этом случае переполнение стека случается уже на n = 10000.

Странно, у меня последний вариант с ghc лучше работает, то память жрет...
Надо подумать.

sequence-то ясно, что не рулит тут, т.к.
         
sequence = foldr mcons (return [])
              where mcons p q = p >>= \x -> q >>= \y -> return (x:y)

Я на Hugs тестировал. Попробовал GHC - там все значительно лучше: rollNDice валится только с аргументом 1000000, работая с аргументами меньше 100000 весьма шустро, а manyTimes работает даже с 10000000, съедая при этом, правда, 2 гига памяти.

Расход памяти в случае manyTimes совсем не радует. Куда там столько девается? Вроде между вызовами должен храниться один список из растущего до n числа элементов. Т.е. при n = 10 миллионов и типе элемента списка Int это несколько десятков мегабайт (ну, пусть сотня-другая, если в ячейке списка еще указатель хранить и еще что-нибудь).

У тебя немного странная постановка задачи. Что ты хочешь сделать с результатом? Вывести его в файл, делать с ним какие-то арифметические действия?

Самый простой способ.

diceList :: Int -> [IO Int]
diceList n = take n (repeat rollDice)

Ну и sequence $ diceList n. Правда sequence не хвостово-рекурсивная и ее ИМХО ее и не сделаешь.

diceList <- mapM (const rollDice) [1..n]

Почему странная? Мне нужно n результатов работы функции с побочными эффектами. Дальнейшая работа с ними - как с обычными данными.

Собственно, через sequence / take / repeat я и сделал первый вариант. В Hugs получилось медленно и с сильно ограниченным n. В GHC уже лучше, особенно второй вариант. Но и он на больших n совершенно неприлично жрет память.

Так какова конченая цель? "Просто так" в хаскеле ничего не бывает.

Получить n случайных чисел из одного генератора. Такая цель устроит?

Блин. Что значит получить? repeat rollDice. Вот ты их и получил. И не n, а скока хошь.

Не отмазывайся, не военкомат. Тебя спросили как _выполнить_последовательность_действий_. В самом вульгарно-императивном смысле. Мы уже поняли, что Хаскель не умеет делать это эффективно, смирись и ты.

>_выполнить_последовательность_действий_

Ну построй цепочку комбинаторов типа

seq = actionA >> actionB >> actionC >> return ()

Вот тебе последовательность действий. В самом вульгарно-императивном смысле.

Хм. Я может как-то невнятно выражаюсь? Я хочу в программе на Хаскеле получить n случайных чисел. Не действий, а чисел. Обычный список [Int]. В самом начале темы я привел два варианта программ, которыми это пытаюсь сделать. Оба варианта для больших n либо вовсе не пригодны (если использовать Hugs), либо весьма неэффективны (второй вариант на GHC). Мне интересно, нельзя ли эту задачу решить более эффективно. А если нет - то почему (в Хаскеле пока не очень хорошо разбираюсь, интересно мнение более компетентных людей).

--- АМ

Вот, к примеру, такое выражение:

length $ map (/2) [1..1000000]

работает в Hugs секунд 30 и памяти не жрет. Таким образом, с большими списками можно нормально работать, если использовать хвостовую рекурсию. Хочется понять, как жить, если источник значений в списке - действие.

Еще раз, на всякий случай: нужен список результатов выполнения n действий, а не список действий.

>Обычный список [Int].

Обычный список [Int] ты получишь только с использованием unsafePerformIO. А так ты получишь [IO Int] и никак иначе.

Как решается хвостово-рекурсивная [IO Int] -> IO [Int], я честно сказать, не в курсе.

>Еще раз, на всякий случай: нужен список результатов выполнения n действий, а не список действий.

А где в твоем примере список? Его нет.

Как и вот в таком примере.

printDice n = mapM_ lll (diceList n) where lll x = do r <- x putStrLn (show r)

И никакого расхода памяти.

printDice n = 
    mapM_ lll (diceList n) 
    where 
        lll x = do 
             r <- x 
             putStrLn (show r) 

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

Вот пример: import IO import System.Random

rollDice :: IO Int rollDice = getStdRandom $ randomR (1, 6)

manyTimes n f | n < 0 = error "Negative sequence length" | n == 0 = return [] | otherwise = manyTimesAcc n f [] where manyTimesAcc 0 _ a = return a manyTimesAcc n f a = do v <- f manyTimesAcc (n-1) f (v:a)

int2float :: Int -> Float int2float = fromInteger . toInteger

rollnum = 1000

main = do rolls <- manyTimes rollnum rollDice print $ (int2float (sum rolls)) / (fromInteger rollnum)

При увеличении rollnum поимеем переполнение стека. manyTimes имеет тип (Monad a, Num b, Ord b) => b -> a c -> a [c]

import IO
import System.Random

rollDice :: IO Int
rollDice = getStdRandom $ randomR (1, 6)

manyTimes n f | n < 0     = error "Negative sequence length"
              | n == 0    = return []
              | otherwise = manyTimesAcc n f []
                where
                  manyTimesAcc 0 _ a = return a
                  manyTimesAcc n f a = do v <- f
                                          manyTimesAcc (n-1) f (v:a)

int2float :: Int -> Float
int2float = fromInteger . toInteger

rollnum = 1000

main = do rolls <- manyTimes rollnum rollDice
          print $ (int2float (foldl (+) 0 rolls)) / (fromInteger rollnum)

АХЗ, вообще, походу дела это какая-то фигня с модулем random. Я с ним ни разу не работал, так что может быть неправильно его использую.

Замени на любой другой IO action и попробуй свою функцию.

Попробовал getCPUTime - та же фигня. Засомневался, не список ли из 10 миллионов Int'ов столько занимает.
Запустил такую программку:

import IO

fibInt :: [Int]
fibInt = 1:1:zipWith (+) fibInt (tail fibInt)

fooPrint h n = do hPrint h n
                  return n

main = do let l = take 10000000 fibInt
          h <- openFile "/dev/null" WriteMode
          sequence_ $ map (fooPrint h) l
          hClose h
          hSetBuffering stdin NoBuffering
          putStrLn "data prepared"
          k <- getLine
          print $ length l

На этапе считывания с stdin строки было потреблено 50% памяти, т.е. около гигабайта. Многовато, конечно, но лучше, чем 2 гигабайта.

P.S. все это с GHC, Hugs помирает примерно на 23050 элементах (имеется в виду запуск do l <- manyTimes 23050 rollDice или аналогичной функции) под Линуксом с ошибкой "Garbage collection fails to reclaim sufficient space", а под Виндой - "C Stack Overflow".

ghc[i] +RTS -K$((16*1024*1024)) -RTS

Гхц ругается, что 8миб стека ему мало. Поставь больше, делов.