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

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

8 голосов
/ 29 июля 2010

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

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

это то, что я искал.

РЕДАКТИРОВАТЬ 2: после прочтения ответа 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. Очень удобно иметь возможность просто генерировать случайный список в монаде ввода-вывода и передавать его в чистую функцию при необходимости, я не понимаю, почему этого не должно быть в стандартной библиотеке.

Ответы [ 2 ]

12 голосов
/ 29 июля 2010

Случайные числа в целом не являются строгими, но монадное связывание - проблема в том, что 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, он создаст бесконечный (и ленивый ) список случайных чисел, сгенерированных из этого начального числа.

5 голосов
/ 29 июля 2010

Я бы сделал что-то вроде этого, позволяя randomR делать работу с начальным 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]. Эта последовательность никогда не пройдет через бесконечный список.

Это лучше объясняется в ответах на предыдущий вопрос: Карта Хаскелла M не ленива?

...