(Отредактировано) Как получить случайное число в Хаскеле без ввода-вывода

Question

(Отредактировано) Как получить случайное число в Хаскеле без ввода-вывода

Я хочу иметь функцию, которая возвращает разные stdGen в каждом звонке без IO. Я пытался использовать unsafePerformIO, как следующий код.

import System.IO.Unsafe
import System.Random

myStdGen :: StdGen
myStdGen = unsafePerformIO getStdGen

Но когда я пытаюсь позвонить myStdGen в ghci я всегда получаю одно и то же значение. Я злоупотребил unsafePerformIO? Или есть другие способы достичь моей цели?

РЕДАКТИРОВАТЬ Извините, я думаю, что я должен описать свой вопрос более точно.

На самом деле, я реализую вариант структуры данных Treap, для которой требуется специальная операция "слияния". Он полагается на некоторую случайность, чтобы гарантировать ожидаемую сложность времени амортизированного O(log n).

Я пытался использовать пару как (Tree, StdGen) сохранить генератор случайных чисел для каждого трепа. Вставляя новые данные в треп, я бы использовал random дать случайное значение новому узлу, а затем обновить мой генератор. Но я столкнулся с проблемой. У меня есть функция под названием empty который вернет пустой треп, и я использовал функцию myStdGen выше, чтобы получить генератор случайных чисел для этого трепа. Однако, если у меня есть два пустых трепа, их StdGen будет таким же. Поэтому после того, как я вставил данные в оба трепа и когда я хочу их объединить, их случайное значение также будет одинаковым. Поэтому я потерял случайность, на которую полагаюсь.

Вот почему я хотел бы иметь как-то "глобальный" генератор случайных чисел, который дает разные StdGen для каждого вызова, так что каждый пустой треп может иметь разные StdGen,

4

haskell unsafe-perform-io

Источник

user1097809 20 ноя '14 в 14:27

3 ответа

Решение

Я оскорблял unsafePerformIO

Черт возьми, да! "Отличительными чертами чистой функции" являются

Нет побочных эффектов
Относительно прозрачный, т. Е. Каждое последующее вычисление результата должно давать одно и то же.

На самом деле есть способ достичь своей "цели", но идея просто ошибочна.

myStdGen :: () -> StdGen
myStdGen () = unsafePerformIO getStdGen

Поскольку это (бесполезный) вызов функции вместо CAF, он оценит IO действие на каждый звонок отдельно.

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

РЕДАКТИРОВАТЬ при попытке я заметил, что getStdGen сам по себе всегда дает один и тот же генератор при использовании в данном процессе, поэтому даже если в приведенном выше примере используются более разумные типы, он не будет работать.

Обратите внимание, что правильное использование псевдослучайности в алгоритмах и т. Д.Не требует ввода-вывода везде - например, вы можете вручную заполнить ваш StdGen, но затем правильно распространять это с splitи т. д. Гораздо более приятный способ справиться с этим - с помощью монады случайности. Программа в целом будет всегда давать один и тот же результат, но внутренне иметь все разные случайные числа, необходимые для полезной работы.

В качестве альтернативы, вы можете получить генератор из IO, но все же написать свой алгоритм в чистой случайной монаде, а неIO,

Есть другой способ получить "случайность" в полностью чистом алгоритме: требуется, чтобы вход былHashable! Затем вы можете эффективно использовать любой аргумент функции в качестве случайного начального числа. Это немного странное решение, но оно может работать для вашего приложения Treap (хотя я считаю, что некоторые люди больше не будут классифицировать его как Treap, а как особый вид hashmap).

8

Источник

user745903 20 ноя '14 в 14:38

Да, вы злоупотребили unsafePerformIO, Есть очень мало веских причин для использования unsafePerformIOНапример, при взаимодействии с библиотекой C, а также при реализации нескольких основных библиотек (я думаю, ST будучи одним из них). Короче говоря, не используйте unsafePerformIO если вы действительно не уверены в том, что делаете. Он не предназначен для генерации случайных чисел.

Напомним, что функции в Haskell должны быть чистыми, то есть они зависят только от их входных данных. Это означает, что у вас может быть чистая функция, которая генерирует "случайное" число, но это число зависит от генератора случайных чисел, который вы передаете ему, вы можете сделать что-то вроде

myStdGen :: StdGen
myStdGen = mkStdGen 42

Тогда вы могли бы сделать

randomInt :: StdGen -> (Int, StdGen)
randomInt g = random

Но тогда вы должны использовать новый StdGen вернулись из этой функции, двигаясь вперед, или вы всегда будете получать один и тот же вывод из randomInt,

Так что вы можете быть удивлены, как вы генерируете случайные числа, не прибегая к IO? Ответ State монада. Это похоже на

newtype State s a = State { runState :: s -> (a, s) }

И его экземпляр монады выглядит как

instance Monad (State s) where
    return a = State $ \s -> (a, s)
    (State m) >>= f = State $ \s -> let (a, newState) = m s
                                        (State g)     = f a
                                    in g newState

С первого взгляда это немного сбивает с толку, но, по сути, все, что делает монада состояний - это сложная композиция функций. Смотрите LYAH для более подробного объяснения. Здесь важно отметить, что тип s не меняется между шагами, просто a параметр может измениться.

Вы заметите, что s -> (a, s) выглядит очень похоже на нашу функцию StdGen -> (Int, StdGen), с s ~ StdGen а также a ~ Int, Это означает, что если бы мы сделали

randomIntS :: State StdGen Int
randomIntS = State randomInt

Тогда мы могли бы сделать

twoRandInts :: State StdGen (Int, Int)
twoRandInts = do
    a <- randomIntS
    b <- randomIntS
    return (a, b)

Затем его можно запустить, указав начальное состояние:

main = do
    g <- getStdGen
    print $ runState twoRandInts g

StdGen все еще выходит из IO, но тогда вся логика сама происходит внутри государственной монады чисто.

5

Источник

user839246 20 ноя '14 в 14:37

Другие вопросы по тегам haskell unsafe-perform-io

user1324720 20 ноя '14 в 14:43 2014-11-20 14:43 · Accepted Answer · 2014-11-20 14:43

Это не очень хорошее применение unsafePerformIO,

Причина, по которой вы постоянно видите одно и то же число в GHCi, заключается в том, что сам GHCi не знает, что значение является нечистым, и поэтому запоминает значение с момента последнего вызова. Вы можете вводить команды ввода-вывода в верхний уровень GHCi, так что вы ожидаете увидеть другое значение, если вы просто наберете getStdGen, Однако это тоже не сработает из-за непонятной части работы GHCi, связанной с не возвращением выражений верхнего уровня. Вы можете включить это с :set +r:

> :set +r
> getStdGen
2144783736 1
> getStdGen
1026741422 1

Обратите внимание, что ваша нечистая функция, притворяющаяся чистой, все равно не будет работать.

> myStdGen
480142475 1
> myStdGen
480142475 1
> myStdGen
480142475 1

Вы действительно не хотите идти по этому пути. unsafePerformIO не должен использоваться таким образом, и при этом это не хорошая идея вообще. Есть способы получить то, что вы хотели (например, unsafePerformIO randomIO :: Int) но они не приведут вас к хорошим вещам. Вместо этого вы должны выполнять вычисления, основанные на случайных числах внутри случайной монады, и выполнять их в монаде IO.

Обновить

Я вижу из твоего обновления, почему ты хотел этого в первую очередь.

В этом ответе есть много интересных мыслей по проблеме случайности внутри иначе ссылочно-прозрачных функций.

Несмотря на то, что некоторые люди выступают за использование unsafePerformIO в этом случае это все еще плохая идея по ряду причин, которые изложены в различных частях этой страницы. В конце концов, если функция зависит от источника случайности, лучше указать ее в своем типе, и самый простой способ сделать это - поместить ее в случайную монаду. Это все еще чистая функция, только та, которая принимает генератор при вызове. Вы можете предоставить этот генератор, запросив случайный в главном IO рутина.

Хороший пример того, как использовать случайную монаду, можно найти здесь.