Próba znalezienia funkcji "losowej" w Haskell

Question

Właśnie dowiedziałem się o funkcji random.

Dla mojego zrozumienia, funkcja random przyjmuje wartość typu, która jest instancją RandomGen i zwraca losową wartość, której wartości możemy określić. Z drugiej strony, mksdGen pobiera Int i generuje generator losowy, którego potrzebuje funkcja.

Próbowałem wygenerować losowe wartości Bool. W tym celu wykonałem funkcję randomBool.

randomBool :: Int -> Bool 
randomBool = fst . random . mkStdGen 

Potem znalazłem dużo więcej niż FalseTrue s s przy małych ilościach. I byłem ciekawy temat i sprawdzane w następujący sposób

> length $ takeWhile randomBool [1..] 
53667 

myślę, oznacza to, że dla pierwszych 53667 liczb całkowitych dodatnich, random . mkStdGen zwrotów True, które nie wydają się być bardzo losowo do mnie. Czy to normalne? Czy robię coś złego, co sprawia, że ​​łatwiej jest uzyskać True?

Answer 1

Generator losowy utworzony przez mkStdGen niekoniecznie generuje wartość losową jako pierwszy wynik. Aby wygenerować następną liczbę losową, użyj losowego generatora zwróconego przez poprzednie wywołanie random.

Na przykład ten kod generuje 10 Bool s.

take 10 $ unfoldr (Just . random) (mkStdGen 1) :: [Bool] 

Answer 2

Nieformalnie, gdy dzwonisz mkStdGen z nasion, które są blisko siebie, dostaniesz dwa generatory „podobny”. W twoim przykładzie faktycznie tworzysz nowe generatory dla każdego dostarczonego materiału siewnego, a ponieważ te nasiona to 1, 2, 3 itd., Przyniosą podobne strumienie.

Po wywołaniu random z generatorem, to rzeczywiście wrócić nowy generator w drugim elemencie pary:

Prelude System.Random> random (mkStdGen 100) :: (Bool, StdGen) 
(True,4041414 40692) 

więc dobrym pomysłem jest użycie tej przewidzianej generator na następne wezwanie do random . Tj

Prelude System.Random> let (i, gen0) = random (mkStdGen 100) :: (Bool, StdGen) 
Prelude System.Random> let (j, gen1) = random gen0   :: (Bool, StdGen) 
Prelude System.Random> let (k, gen2) = random gen1   :: (Bool, StdGen) 
Prelude System.Random> (i, j, k) 
(True, False, False) 

więc zrobić kilka losowych wartości, chcesz przekazać jako generator stanie. Można to ustawić ręcznie za pomocą State monady albo coś, albo po prostu użyć funkcji randoms, który obsługuje przechodzącego w stan generatora dla Ciebie:

Prelude System.Random> take 10 $ randoms (mkStdGen 100) :: [Bool] 
[True,False,False,False,False,True,True,False,False,True] 

Jeśli nie szczególnie dbać o byciu w IO (zdarza) można użyć randomIO:

Prelude System.Random> import Control.Monad 
Prelude System.Random Control.Monad> replicateM 10 randomIO :: IO [Bool] 
[True,True,False,True,True,False,False,False,True,True] 

This section z LYAH może być przydatna do odczytu.

Answer 3

Komputery są deterministyczne i nie mogą generować liczb losowych. Raczej opierają się na matematycznych formułach, które zwracają rozkład liczb, które wyglądają losowo.Są to tak zwane generatory liczb pseudolosowych. Jednak z powodu determinizmu mamy problem, że gdybyśmy podczas tych inwokacji naszego programu uruchamiali te formuły w ten sam sposób, otrzymalibyśmy te same generatory liczb losowych. Oczywiście nie jest to dobre, ponieważ chcemy, aby nasze liczby były losowe! W związku z tym musimy dostarczyć generatorowi losowemu początkową wartość początkową, która zmienia się z biegu do uruchomienia. Dla większości ludzi (tj. Tych, którzy nie robią rzeczy kryptograficznych) generator liczb losowych jest zarzucany przez bieżący czas. W Haskell ten pseudolosowy generator jest reprezentowany przez typ StdGen. Funkcja mkStdGen służy do tworzenia generatora liczb losowych z materiałem siewnym. W przeciwieństwie do C, gdzie istnieje jeden globalny generator liczb losowych, w Haskell możesz mieć tylu, ile chcesz, i możesz tworzyć je z różnymi nasionami.

Jednak jest pewne zastrzeżenie: ponieważ liczby są pseudolosowe, nie ma gwarancji, że generatory liczb losowych utworzone z różnych liczb zwracających nasiona wyglądają losowo w porównaniu do innych. Oznacza to, że po wywołaniu randomBool i nadaniu jej kolejnych wartości początkowych, nie ma gwarancji, że liczba uzyskana z utworzonego przez użytkownika StdGen jest losowa w porównaniu z StdGen wysianą z jej następcą. Dlatego otrzymujesz prawie 50000 True.

Aby uzyskać dane wyglądające losowo, należy nadal korzystać z tego samego generatora liczb losowych. Jeśli zauważysz, funkcja Haskell random ma typ StdGen -> (a, StdGen). Ponieważ Haskell jest czysty, funkcjapobiera generator liczb losowych, generuje wartość pseudolosową (pierwszy element wartości zwracanej), a następnie zwraca nową StdGen, która reprezentuje generator zaszczepiony oryginalnym nasieniem, ale gotowa do podania nowa liczba losowa. Musisz zachować ten inny numer StdGen i przekazać go do następnej funkcji random, aby uzyskać losowe dane.

Oto przykład generowania trzech losowych sygnałów, a, b i c.

randomBools :: StdGen -> (Bool, Bool, Bool) 
randomBools gen = let (a, gen') = random gen 
         (b, gen'') = random gen'' 
         (c, gen''') = random gen''' 
        in (a, b, c) 

Wskazówki jak zmienna gen jest „gwintowane” za pośrednictwem połączeń do losowo.

Można uprościć przekazywanie stanu za pomocą monady stanu. Na przykład,

import Control.Monad.State 
import System.Random 

type MyRandomMonad a = State StdGen a 

myRandom :: Random a => MyRandomMonad a 
myRandom = do 
    gen <- get -- Get the StdGen state from the monad 
    let (nextValue, gen') = random gen -- Generate the number, and keep the new StdGen 
    put gen' -- Update the StdGen in the monad so subsequent calls generate new random numbers 
    return nextValue 

Teraz można napisać funkcję randomBools jak:

randomBools' :: StdGen -> (Bool, Bool, Bool) 
randomBools' gen = fst $ runState doGenerate gen 
    where doGenerate = do 
      a <- myRandom 
      b <- myRandom 
      c <- myRandom 
      return (a, b, c) 

Jeśli chcesz wygenerować (skończoną) wykaz Bool s, można zrobić

randomBoolList :: StdGen -> Int -> ([Bool], StdGen) 
randomBoolList gen length = runState (replicateM length myRandom) gen 

Zwróć uwagę, jak zwracamy StdGen jako drugi element zwróconej pary, aby umożliwić jej udostępnienie nowych funkcji.

Po prostu, jeśli chcesz wygenerować nieskończoną listę losowych wartości tego samego typu z StdGen, możesz użyć funkcji randoms. To ma podpis (RandomGen g, Random a) => g -> [a]. Aby wygenerować nieskończoną listę Bool przy użyciu początkowego seeda x, wystarczy uruchomić randoms (mkStdGen x). Możesz zaimplementować swój przykład za pomocą length $ takeWhile id (randoms (mkStdGen x)). Powinieneś zweryfikować, że otrzymujesz różne wartości dla różnych początkowych wartości x, ale zawsze ta sama wartość, jeśli dostarczasz tę samą x.

Wreszcie, jeśli nie interesuje Cię bycie związanym z monadą IO, Haskell dostarcza również globalny generator liczb losowych, podobnie jak języki imperatywne. Wywołanie funkcji randomIO w monadzie da ci losową wartość dowolnego typu, który ci się podoba (o ile jest to przynajmniej egzemplarz modelu typograficznego Random). Możesz użyć tego podobnie do myRandom powyżej, z wyjątkiem monady IO. Ma to dodatkową zaletę, że jest wstępnie zaimplementowany w środowisku wykonawczym Haskell, co oznacza, że ​​nie musisz się nawet martwić o utworzenie StdGen. Tak więc, aby stworzyć losową listę 10 Bool S w IO monady, wszystko co musisz zrobić, to replicateM 10 randomIO :: IO [Bool].

Nadzieja to pomaga :)