На этом шаге мы рассмотрим вопросы генерации таких чисел.
Воспользуемся простым, но вполне качественным алгоритмом для получения целых чисел, равномерно распределённых на интервале [0,2147483647].
Приведём его реализацию на языке Haskell [1, с.144]:
next_seed:: Int -> Int
next_seed n = case test>0 of
True -> test
False -> test+2147483647
where test = 48271*lo-3399*hi
hi = n `div` 44488
lo = n `mod` 44488
Начальное значение может быть выбрано произвольно. Для получения различных последовательностей следует применить данный алгоритм к другому начальному значению.
Вызов функции next_seed даёт первое псевдослучайное число, передаваемое ей снова в качестве нового аргумента. Для реализации этого подхода удобно использовать функционал iterate
rand:: [Int] rand = iterate next_seed 23765492
Из бесконечного списка, генерируемого функцией rand, следует выбрать требуемое число начальных элементов при помощи функции take:
> take 5 rand
Для получения списка случайных чисел, меньших некоторого заданного значения (например, 100), можно брать остаток от деления случайного числа на данное:
rand':: Int-> [Int] rand' a = [x `mod` a | x <- rand]
В результате использования этой функции получается бесконечный список чисел в диапазоне от 0 до 99:
> take 20 rand'
Существует большое число научно обоснованных критериев добротности генераторов случайных чисел. Но даже без соответствующей теории интуитивно ясно, что в случайной последовательности количество чётных и нечётных чисел должно быть приблизительно равно.
Напишем программу [1, с.145], подсчитывающую долю чётных и нечётных чисел в последовательности, получаемой с помощью описанного выше генератора случайных чисел.
Сначала определим функцию quantum, возвращающую пару чисел - число нечётных и чётных чисел в списке, являющемся аргументом данной функции:
quantum:: [Int] -> (Int,Int)
quantum [] = (0,0)
quantum (x:xs) = case odd x of
True -> (u+1,v)
False -> (u,v+1)
where (u,v) = quantum xs
Подсчитаем с её помощью число чётных и нечётных чисел среди первой тысячи целых чисел:
> quantum [1..1000] (500,500)
Функция proportion подсчитывает долю каждого элемента пары от их суммарного количества:
proportion:: (Int,Int) -> (Float,Float)
proportion (0,0) = (0.0,0.0)
proportion (0,_) = (0.0,1.0)
proportion (_,0) = (1.0,0.0)
proportion (a,b) = (fromInt a/c,fromInt b/c)
where c = fromInt (a+b)
Остаётся применить композицию этих функций к списку случайных чисел, полученного с помощью функции rn:
rn:: Int -> [Int] rn n = take n rand test:: Int -> (Float,Float) test = proportion . quantum . rn
Функция test определена в чисто функциональном стиле - как композиция трёх функций. Теперь можно провести тестирование полученной последовательности:
> test 500 (0.508,0.492) > test 5000 (0.5008,0.4992)
Как видим, доли чётных и нечётных чисел достаточно близки.
В заключение приведем несколько демонстрационных примеров.
-- Генерация псевдослучайных чисел с помощью функций -- модуля Random -- ************* import Random import IO -- *********** -- (1) Функция -- -- random:: (RandomGen g,Random a) => g -> (a,g) -- -- возвращает случайное значение и генератор в паре. -- Функция random принимает генератор случайности (источник -- случайности) и возвращает случайное значение и новый -- генератор случайности -- ********************* -- (2) Функция -- -- mkStdGen:: Int -> StdGen -- -- принимает целое число и основываясь на нём, возвращает -- генератор случайных чисел. -- Таким образом, функция mkStdGen является "ручным" -- (а не автоматическим) генератором случайности ------------------------------------------------ test1 = random (mkStdGen 100):: (Int,StdGen) ------------------------------------------------------------ -- Получим случайное число и представление нового генератора ------------------------------------------------------------ test2 = (fst test1,snd test1) --------------------------------------------------- -- Получим новое случайное число и новый генератор; -- число 949494 выбрано нами ----------------------------------------------- test3 = random (mkStdGen 949494):: (Int,StdGen) ----------------------------------------------- -- Генерация случайных значений различных типов ---------------------------------------------------- test3' = random (mkStdGen 949494):: (Float,StdGen) test3'' = random (mkStdGen 949494):: (Bool,StdGen) test3''' = random (mkStdGen 949494):: (Integer,StdGen) -- ****************************************************** -- Функция возвращает результат трёх подбрасываний монеты --------------------------------------------------------- three:: StdGen -> (Bool,Bool,Bool) three gen = (first,second,third) where (first,newGen) = random gen -- :: (Bool,StdGen) (second,newGen') = random newGen -- :: (Bool,StdGen) (third,newGen'') = random newGen' -- :: (Bool,StdGen) ---------------------------------------------------------------- test4 = map (three.mkStdGen) [21,22,943,944] -- *********** -- (3) Функция -- -- randoms:: (Random a,RandomGen b) => b -> [a] -- -- возвращает бесконечный список случайных значений по задан- -- ному генератору. -- Функция random принимает генератор случайности (источник -- случайности) и возвращает бесконечный список случайных -- значений ------------------------------------------------- test5 = take 5 $ randoms (mkStdGen 11) :: [Float] -- ************************** -- Реализация функции randoms --------------------------------------------- randoms':: (RandomGen g,Random a) => g -> [a] randoms' gen = val : randoms' newGen where (val,newGen) = random gen ------------------------------------------------- test6 = take 5 $ randoms' (mkStdGen 11):: [Float] -- ************************************************* -- Функция, которая генерирует конечный список чисел -- и новый генератор -------------------------------------------------------------- finiteRand:: (RandomGen g,Random a,Num n) => n -> g -> ([a],g) finiteRand 0 gen = ([],gen) finiteRand n gen = (value : restOfList,finalGen) where (value,newGen) = random gen (restOfList,finalGen) = finiteRand (n-1) newGen ----------------------------------------------------------- test7 = finiteRand 5 (mkStdGen 11) :: ([Float],StdGen) -- *********** -- (4) Функция -- -- randomR:: (RandomGen g,Random a) => (a,a) -> g -> ([a,a],g) -- -- возвращает пару, содержащую список случайных значений -- в заданном диапазоне и генератор ------------------------------------------------------ test8 = randomR (1,6) (mkStdGen 359353):: (Int,StdGen) -- *********** -- (5) Функция -- -- randomRs:: (Random a,RandomGen b) => (a,a) -> b -> [a] -- -- возвращает бесконечный список случайных значений по задан- -- ному генератору ---------------------------------------------------------- test9 = take 5 $ randomRs ('a','z') (mkStdGen 3):: [Char] test10 = take 5 $ randomRs (1,6) (mkStdGen 3):: [Int] test11 = take 5 $ randomRs (0,1) (mkStdGen 3) --:: [Float] -- **************************************** -- Случайные объекты в системе ввода-вывода -- **************************************** -- (1) Функция (действие!) -- -- getStdGen:: IO StdGen -- -- возвращает генератор случайных чисел и сохраняет его -- в глобальном генераторе. -- Внимание! Функция действует, если откомпилировать -- (создать файл *.exe) сценарий на языке Haskell ------------------------------------------------- main = do gen <- getStdGen putStrLn $ take 20 $ randomRs ('a','z') gen gen1 <- getStdGen putStrLn $ take 20 $ randomRs ('a','z') gen1 -- *********************** -- (2) Функция (действие!) -- -- newStdGen:: IO StdGen -- -- разбивает текущий глобальный генератор случайных чисел -- на два генератора; далее, действие замещает глобальный -- генератор на один из результирующих генераторов и воз- -- вращает второй генератор в качестве результата ------------------------------------------------- main' = do gen <- getStdGen putStrLn $ take 20 $ randomRs ('a','z') gen gen1 <- getStdGen putStrLn $ take 20 $ randomRs ('a','z') gen1 gen <- newStdGen putStrLn $ take 20 $ randomRs ('a','z') gen -- ************************************************ -- Генерация псевдослучайных чисел на отрезке [1,n] -- с использованием библиотеки Random ------------------------------------- func:: Int -> IO Int func n = getStdRandom (randomR (1,n)) ------------------------------------- -- Тестовые примеры: -------------------- test15 = func 13:: IO Int test16 = func 14:: IO Int
-- Демонстрация генерации различных псевдослучайных структур -- данных: -- (1) псевдослучайных натуральных чисел; -- (2) списка псевдослучайных натуральных чисел; -- (3) списка псевдослучайных действительных чисел, меньших -- 1, содержащего заданное количество элементов; -- (4) случайного нечёткого множества в заданном универсуме -- ********************************************************* import List -- ******************************************************** -- Функция, возвращающая псевдослучайное натуральное число; -- n - натуральное число, "затравка" ------------------------------------ next_seed:: Int -> Int next_seed n = case test>0 of True -> test False -> test+2147483647 where test = 48271*lo-3399*hi hi = n `div` 44488 lo = n `mod` 44488 -- ************************************************ -- Функция, генерирующая бесконечный список псевдо- -- случайных натуральных чисел ------------------------------ rand:: [Int] rand = iterate next_seed 23765492 -- ************************************************** -- Функция, генерирующая бесконечный список элементов -- в диапазоне от 0 до (a-1) ---------------------------- rand':: Int-> [Int] rand' a = [x `mod` a | x <- rand] -- ******************************************************* -- Функция, генерирующая подсписок целых чисел, содержащий -- от n-го до m-го числа из псевдослучайного списка чисел -- в диапазоне от 0 до (a-1) -------------------------------------- newRndLst:: Int -> Int -> Int -> [Int] newRndLst n m a = drop n (take (m+1) (rand' a)) -- ********************************************************* -- Функция, генерирующая список псевдослучайных действитель- -- ных чисел, меньших 1, содержащего (27-15) элементов ------------------------------------------------------------ realRndLst n m a = map (\x -> (fromInt $ truncate (x*100))/100) z1 where z = newRndLst n m a z1 = map (\x -> (fromInt x)/(fromInt $ maximum z)) z -- ********************************************************* -- Функция, генерирующая случайное нечёткое множество в уни- -- версуме univ; -- a - "затравка" для генерации различных случайных нечётких -- множеств --------------------------- rndFuz univ a = zip univ z3 where z = length univ z1 = newRndLst (fromInteger a) ((fromInteger a)+z-1) 20 {- любое положительное -} {- натуральное число -} z2 = map (\x -> (fromInt x)/(fromInt $ maximum z1)) z1 z3 = map (\x -> (fromInt $ truncate (x*100))/100) z2 -- *********************************************************** -- Неудачные тестовые примеры: ------------------------------ test1 = newRndLst 1 10 4 test2 = newRndLst 11 121 4 test3 = newRndLst 1000 2000 4 -------------------------------- test4 = sort (newRndLst 1 10 49) test5 = sort (newRndLst 1 6 49) -------------------------------- test6 = realRndLst 20 30 123 test7 = realRndLst 20 30 23 test8 = realRndLst 20 30 300 ---------------------------- test9 = rndFuz [1..10] 10 test10 = rndFuz [1..10] 100
(1)Роганова Н.А. Функциональное программирование. - М: ГИНФО, 2002. - 260 с.
Со следующего шага мы начнем рассматривать функционалы (функции высшего порядка).
