Среднее из большого числа бросков кубиков в Хаскеле - PullRequest
Новая
       16

Среднее из большого числа бросков кубиков в Хаскеле

4 голосов
/ 22 августа 2011

В попытке лучше изучить Haskell, я пытаюсь написать программу, которая отображает среднее значение суммы 2 кубиков, брошенных X раз.Это довольно просто в C, Java, Python ... но я застрял в Haskell.Вот наивная попытка: 

import System.Random

main = do
    g <- getStdGen
    let trials = 10000000
    let rolls = take trials (randomRs (2, 12) g :: [Int])
    let average = div (sum rolls) trials
    print average

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

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

Должен быть лучший способ написать эту программу.В версиях C, Java и Python это простая задача.Я посмотрел этот пост (и понимаю около 75% материала), но когда я адаптирую этот код к этой ситуации, суммирование последовательности R [Int] не работает (и яне уверен, как «развернуть» [Int]).Что я делаю неправильно?Какой правильный путь?Как мне достичь просветления случайных чисел в Haskell?

Редактировать: в дополнение к выбранному ответу, как указывает rtperson ниже, моделирование 2 кубиков некорректно;на самом деле это должна быть сумма двух независимых бросков от 1 до 6.

Ответы [ 2 ]

7 голосов
/ 22 августа 2011

sum бесполезно суммировать длинный список, он работает в линейном пространстве. Попробуйте эту строгую версию sum: 

sum' = foldl' (+) 0

foldl' определяется в Data.List.

EDIT Более подробную информацию можно найти в этой статье на HaskellWiki .

4 голосов
/ 22 августа 2011

На самом деле вероятности здесь неправильно смоделированы. Когда код написан, есть такая же возможность получить от 2 до 12. Но это не так, как работают кости. Из 12 возможных результатов есть только один способ получить 2 (через 1 и 1) и 12 (через 6 и 6). Но есть 6 способов получить 7 (1-6, 2-5, 3-4, 4-3, 5-2, 6-1). Моделирование броска двух кубиков, а не одного шанса от 2 до 12, дало бы правильное ожидаемое значение 7.

Однако - и вот где ваши волосы действительно начнут завиваться - вы не можете просто сделать что-то вроде следующего: 

let rolls1 = take trials (randomRs (1, 6) g :: [Int])
let rolls2 = take trials (randomRs (1, 6) g :: [Int])

Потому что rolls 1 и rolls 2 дадут одинаковые результаты. 

*Main> let rolls = zip rolls1 rolls2
*Main> take 10 rolls
[(3,3),(4,4),(5,5),(3,3),(5,5),(1,1),(3,3),(1,1),(3,3),(3,3)]

Таким образом, ваш результат всегда будет четным и, следовательно, останется неправильным ответом 6.

Чтобы получить два совершенно случайных списка, вам нужно создать новый StdGen: 

import System.Random
import Data.List

main = do
    g <- getStdGen
    b <- newStdGen   -- calls "split" on the global generator
    let trials = 10000000
    let rolls1 = take trials (randomRs (1, 6) g :: [Int])
    let rolls2 = take trials (randomRs (1, 6) b :: [Int])
    let rolls = zipWith (+) rolls1 rolls2
    let average = div (foldl' (+) 0 rolls) trials
    print average

(Обратите внимание, что я специально избегаю использовать для этого монаду штата. Пожалуйста.)

Это занимает больше времени, чем оригинальная версия, но лень zipWith в сочетании со строгостью foldl' гарантируют, что вы не переполните стек.

Если вы просто пытаетесь устранить переполнение, ответ n.m. будет правильным. Строгость foldl' устранит проблему с производительностью. Но в этом случае получение правильного ответа также научит вас тому, как генерировать случайные числа в Haskell.

...