Строг mapM в Haskell? Почему эта программа получает переполнение стека?
Следующая программа завершается правильно:
import System.Random
randomList = mapM (\_->getStdRandom (randomR (0, 50000::Int))) [0..5000]
main = do
randomInts <- randomList
print $ take 5 randomInts
Выполнение:
$ runhaskell test.hs
[26156,7258,29057,40002,26339]
Однако подавая его с бесконечным списком, программа никогда не завершается, и при возможной компиляции дает ошибку переполнения стека!
import System.Random
randomList = mapM (\_->getStdRandom (randomR (0, 50000::Int))) [0..]
main = do
randomInts <- randomList
print $ take 5 randomInts
Выполнение,
$ ./test
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.
Я ожидал, что программа лениво оценит getStdRandom каждый раз я выбираю объект от списка, заканчивая после выполнения так 5 раз. Почему это пытается оценить целый список?
Спасибо.
Существует ли лучший способ получить бесконечный список случайных чисел? Я хочу передать этот список в чистую функцию.
Править: Еще некоторое чтение показало что функция
randomList r = do g <- getStdGen
return $ randomRs r g
то, что я искал.
EDIT2: после чтения ответа camccann я понял это getStdGen получает новое семя на каждом вызове. Вместо этого лучше для использования этой функции в качестве простого одноразового случайного генератора списка:
import System.Random
randomList :: Random a => a -> a -> IO [a]
randomList r g = do s <- newStdGen
return $ randomRs (r,g) s
main = do r <- randomList 0 (50::Int)
print $ take 5 r
Но я все еще не понимаю почему мой mapM вызов не завершался. Очевидно не связанный со случайными числами, но чем-то, чтобы сделать с mapM возможно.
Например, я нашел, что следующее также не завершается:
randomList = mapM (\_->return 0) [0..]
main = do
randomInts <- randomList
print $ take 50000 randomInts
Что дает? Между прочим, по моему скромному мнению, вышеупомянутое randomInts функция должна быть в System.Random. Чрезвычайно удобно смочь к очень, просто генерируют случайный список в монаде IO и передают его в чистую функцию при необходимости, я не вижу, почему это не должно быть в стандартной библиотеке.
2 ответа
Я бы сделал что-то вроде этого, позволив randomRs выполнять работу с начальным RandomGen:
#! /usr/bin/env runhaskell
import Control.Monad
import System.Random
randomList :: RandomGen g => g -> [Int]
randomList = randomRs (0, 50000)
main :: IO ()
main = do
randomInts <- liftM randomList newStdGen
print $ take 5 randomInts
Что касается лени, то здесь происходит то, что mapM is (sequence. Map)
Его тип: mapM :: (Monad m) => (a -> mb) -> [a] -> m [b]
Он отображает функцию, давая [ mb] , а затем необходимо выполнить все эти действия, чтобы получить m [b] . Это последовательность, которой никогда не пройти через бесконечный список.
Это лучше объясняется в ответах на предыдущий вопрос: Является ли Haskell mapM ленивым?
Случайные числа в целом не являются строгими, но монадическими привязка - проблема в том, что mapM должен упорядочить весь список. Рассмотрим сигнатуру его типа, (a -> m b) -> [a] -> m [b] ; из этого следует, что он сначала отображает список типа [a] в список типа [mb] , затем последовательность , чтобы получить результат типа m [b] . Итак, когда вы привязываете результат применения mapM , например. помещая его в правую часть <- , это означает «сопоставьте эту функцию со списком, затем выполните каждое монадическое действие и объедините результаты обратно в один список» . Если список бесконечен, это, конечно, не закончится.
Если вам просто нужен поток случайных чисел, вам нужно сгенерировать список без использования монады для каждого числа.Я не совсем уверен, почему вы использовали тот дизайн, который у вас есть, но основная идея такова: с учетом начального значения используйте генератор псевдослучайных чисел для создания пары: 1) случайное число 2) новое начальное число , затем повторите с новым семенем. Любое заданное семя, конечно, будет каждый раз обеспечивать одну и ту же последовательность. Итак, вы можете использовать функцию getStdGen , которая предоставит новое семя в монаде IO ; затем вы можете использовать это семя для создания бесконечной последовательности в полностью чистом коде.
Фактически, System.Random предоставляет функции именно для этой цели, randomRs или randomRs вместо random и randomR .
Если по какой-то причине вы хотите сделать это самостоятельно, то, по сути, вы хотите развернуть . Функция развёртка из Data.List имеет сигнатуру типа (b -> Maybe (a, b)) -> b -> [a] , что довольно очевиден: для заданного значения типа b он применяет функцию, чтобы получить что-то типа a и новое значение генератора типа b , или Ничего , чтобы указать конец последовательности.
Вам нужен бесконечный список, поэтому вам никогда не придется возвращать Nothing . Таким образом, частичное применение randomR к желаемому диапазону и составление его с помощью Just дает следующее:
Just . randomR (0, 50000::Int) :: (RandomGen a) => a -> Maybe (Int, a)
Подача этого в разворачивание дает следующее:
unfoldr (Just . randomR (0, 50000::Int)) :: (RandomGen a) => a -> [Int]
.. .который выполняет именно то, что заявлено: учитывая экземпляр RandomGen , он будет создавать бесконечный (и ленивый ) список случайных чисел, сгенерированный из этого начального числа.