Является ли mapM в Haskell строгим? Почему эта программа получает переполнение стека?

Question

Следующая программа завершается корректно:

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 раз. Почему он пытается оценить весь список?

Спасибо.

Есть ли лучший способ получить бесконечный список случайных чисел? Я хочу передать этот список в чистую функцию.

EDIT: Некоторые более чтения показали, что функция

randomList r = do g <- getStdGen 
        return $ randomRs r g 

является то, что я искал.

EDIT2: после прочтения ответа от компании Camcann я понял, что 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 

Что это дает? Кстати, IMHO, вышеуказанная функция randomInts должна быть в System.Random. Очень удобно иметь очень генерировать случайный список в монаде IO и передавать его в чистую функцию, когда это необходимо, я не понимаю, почему это не должно быть в стандартной библиотеке.

Answer 1

Я хотел бы сделать что-то больше, как это, выпускающие 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 является (sequence . map)

Его тип: mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]

Это отображение функции, дающей [m b], а затем необходимо выполнить все эти действия, чтобы сделать m [b]. Это последовательность, которая никогда не пройдет через бесконечный список.

Это объясняется лучше в ответах предшествующему вопрос: Is Haskell's mapM not lazy?

Answer 2

Случайные числа в целом не является строгим, но монадическая связывание это - проблема здесь состоит в том, что mapM имеет секвенировать весь список. Рассмотрим его подпись типа, (a -> m b) -> [a] -> m [b]; как это подразумевается, то, что он делает, сначала map список типа [a] в список типов [m b], затем sequence этот список, чтобы получить результат типа m [b]. Таким образом, когда вы связываете результат применения mapM, , например., помещая его в правую часть <-, это означает, что «отображает эту функцию по списку, затем выполняет каждое монадическое действие и объединяет результаты обратно в один список». Если список бесконечен, это, конечно, не закончится.

Если вы просто хотите поток случайных чисел, вам нужно сгенерировать список, не используя монаду для каждого номера. Я не совсем уверен, почему вы использовали дизайн, который у вас есть, но основная идея заключается в следующем: учитывая начальное значение, используйте генератор псевдослучайных чисел для создания пары 1) случайного числа 2) нового семени , затем повторите с новым семенем. Любое заданное семя, конечно, будет давать одну и ту же последовательность каждый раз. Таким образом, вы можете использовать функцию getStdGen, которая обеспечит свежее семя в монаде IO; вы можете использовать это семя для создания бесконечной последовательности в полностью чистом коде.

В самом деле, System.Random обеспечивает функции именно с этой целью, randoms или randomRs вместо random и randomR.

Если по какой-то причине вы хотите сделать это самостоятельно, то, что вы хотите, по существу, является разворачивается. Функция unfoldr из Data.List имеет тип подписи (b -> Maybe (a, b)) -> b -> [a], которое говорит само за себя: Учитывая значение типа b, она применяет функцию, чтобы получить либо что-то типа a и новое значение генератора типа b или Nothing, чтобы указать конец последовательности.

Вы хотите бесконечный список, поэтому никогда не потребуется возвращать Nothing. Таким образом, частично применяя randomR на нужный диапазон и слагающих его с Just дает это:

Just . randomR (0, 50000::Int) :: (RandomGen a) => a -> Maybe (Int, a) 

кормления, что в unfoldr дает это:

unfoldr (Just . randomR (0, 50000::Int)) :: (RandomGen a) => a -> [Int] 

... который делает именно так, как он утверждает: Дано экземпляр RandomGen, он произведет бесконечный (и ленивый) список случайных чисел, сгенерированных из этого семени.