Как функциональные языки обрабатывают случайные числа?

68

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

Как же тогда вы создаете функцию, которая принимает семя в качестве параметра, а затем возвращает случайное число на основе этого семени?

Я имею в виду, что это, кажется, идет вразрез с одной из вещей, которые так хороши в функциях, верно? Или я что-то здесь полностью упускаю?

Электрический кофе
источник

Ответы:

89

Вы не можете создать чистую функцию с именем, randomкоторая будет давать разные результаты при каждом вызове. На самом деле, вы даже не можете «вызывать» чистые функции. Вы применяете их. Так что вы ничего не упускаете, но это не означает, что случайные числа в функциональном программировании запрещены. Позвольте мне продемонстрировать, что я буду использовать синтаксис Haskell повсюду.

Исходя из императивного фона, вы можете изначально ожидать, что случайный тип будет иметь следующий вид:

random :: () -> Integer

Но это уже исключено, потому что случайный не может быть чистой функцией.

Рассмотрим идею стоимости. Ценность является неизменной вещью. Он никогда не меняется, и каждое наблюдение, которое вы можете сделать по этому поводу, является постоянным на все времена.

Понятно, что random не может дать целочисленное значение. Вместо этого он генерирует случайную переменную типа Integer. Это тип может выглядеть так:

random :: () -> Random Integer

За исключением того, что передача аргумента совершенно не нужна, функции чисты, поэтому одна из random ()них так же хороша, как и другая random (). Я дам случайный, с этого момента, этот тип:

random :: Random Integer

Что все хорошо, но не очень полезно. Вы можете ожидать, что сможете писать выражения как random + 42, но не можете, потому что это не проверяет тип. Вы ничего не можете сделать со случайными переменными, пока.

Это поднимает интересный вопрос. Какие функции должны существовать для работы со случайными переменными?

Эта функция не может существовать:

bad :: Random a -> a

любым полезным способом, потому что тогда вы могли бы написать:

badRandom :: Integer
badRandom = bad random

Что вносит несоответствие. badRandom, предположительно, является значением, но это также случайное число; противоречие.

Может быть, мы должны добавить эту функцию:

randomAdd :: Integer -> Random Integer -> Random Integer

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

randomMap :: (a -> b) -> Random a -> Random b

Вместо того чтобы писать random + 42, теперь мы можем писать randomMap (+42) random.

Если бы все, что у вас было, было randomMap, вы бы не смогли объединить случайные переменные вместе. Вы не могли бы написать эту функцию, например:

randomCombine :: Random a -> Random b -> Random (a, b)

Вы можете попробовать написать это так:

randomCombine a b = randomMap (\a' -> randomMap (\b' -> (a', b')) b) a

Но это неправильный тип. Вместо того, чтобы в конечном итоге с Random (a, b), мы в конечном итоге сRandom (Random (a, b))

Это можно исправить, добавив еще одну функцию:

randomJoin :: Random (Random a) -> Random a

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

randomBind :: Random a -> (a -> Random b) -> Random b

Не сразу очевидно, что это на самом деле решает проблему, но это так:

randomCombine a b = randomBind a (\a' -> randomMap (\b' -> (a', b')) b)

Фактически, можно написать randomBind в терминах randomJoin и randomMap. Также возможно написать randomJoin в терминах randomBind. Но я оставлю это как упражнение.

Мы могли бы немного упростить это. Позвольте мне определить эту функцию:

randomUnit :: a -> Random a

randomUnit превращает значение в случайную величину. Это означает, что у нас могут быть случайные переменные, которые на самом деле не случайны. Это всегда было так, хотя; мы могли бы сделать randomMap (const 4) randomраньше. Хорошей идеей для определения randomUnit является то, что теперь мы можем определить randomMap в терминах randomUnit и randomBind:

randomMap :: (a -> b) -> Random a -> Random b
randomMap f x = randomBind x (randomUnit . f)

Хорошо, теперь мы куда-то добираемся. У нас есть случайные величины, которыми мы можем манипулировать. Тем не мение:

  • Не очевидно, как мы могли бы на самом деле реализовать эти функции,
  • Это довольно громоздко.

Реализация

Я буду решать псевдослучайные числа. Возможно реализовать эти функции для реальных случайных чисел, но этот ответ уже становится довольно длинным.

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

runRandom :: Seed -> Random a -> a

Я собираюсь определить тип Random следующим образом:

data Random a = Random (Seed -> (Seed, a))

Затем нам просто нужно предоставить реализации randomUnit, randomBind, runRandom и random, что довольно просто:

randomUnit :: a -> Random a
randomUnit x = Random (\seed -> (seed, x))

randomBind :: Random a -> (a -> Random b) -> Random b
randomBind (Random f) g =
  Random (\seed ->
    let (seed', x) = f seed
        Random g' = g x in
          g' seed')

runRandom :: Seed -> Random a -> a
runRandom seed (Random f) = (snd . f) seed

Для случайного, я собираюсь предположить, что уже есть функция типа:

psuedoRandom :: Seed -> (Seed, Integer)

В этом случае случайный просто Random psuedoRandom.

Делать вещи менее громоздкими

У Haskell есть синтаксический сахар, чтобы сделать такие вещи приятнее на глазах. Это называется do-notation, и чтобы использовать все это, нам нужно создать экземпляр Monad for Random.

instance Monad Random where
  return = randomUnit
  (>>=) = randomBind

Готово. randomCombineиз раньше можно было теперь написать:

randomCombine :: Random a -> Random b -> Random (a, b)
randomCombine a b = do
  a' <- a
  b' <- b
  return (a', b')

Если бы я делал это для себя, я бы даже пошел на шаг дальше и создал бы экземпляр Applicative. (Не волнуйтесь, если это не имеет смысла).

instance Functor Random where
  fmap = liftM

instance Applicative Random where
  pure = return
  (<*>) = ap

Тогда randomCombine может быть написано:

randomCombine :: Random a -> Random b -> Random (a, b)
randomCombine a b = (,) <$> a <*> b

Теперь, когда у нас есть эти экземпляры, мы можем использовать >>=вместо randomBind, join вместо randomJoin, fmap вместо randomMap, return вместо randomUnit. Мы также получаем целый набор функций бесплатно.

Стоит ли оно того? Можно утверждать, что добраться до этой стадии, где работа со случайными числами не является полностью ужасной, было довольно сложно и многословно. Что мы получили в обмен на эти усилия?

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

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

dan_waterworth
источник
6
+1 за хороший пример практического использования аппликативных функторов / монад.
jozefg
9
Хороший ответ, но он идет слишком быстро с некоторыми шагами. Например, зачем bad :: Random a -> aвводить несоответствия? Что в этом плохого? Пожалуйста, продвигайтесь медленно в объяснении, особенно для первых шагов :) Если бы вы могли объяснить, почему «полезные» функции полезны, это может быть ответ из 1000 пунктов! :)
Андрес Ф.
@AndresF. Хорошо, я немного пересмотрю.
dan_waterworth
1
@AndresF. Я пересмотрел свой ответ, но не думаю, что достаточно объяснил, как вы можете использовать это на практике, поэтому я вернусь к нему позже.
dan_waterworth
3
Замечательный ответ. Я не функциональный программист, но я понимаю большинство концепций, и я «играл» с Haskell. Это тот тип ответа, который информирует спрашивающего и побуждает других глубже копать и узнавать больше о теме. Хотел бы я дать вам несколько дополнительных очков выше 10 из моего голосования.
RLH
10

Вы не ошиблись. Если вы дадите одно и то же начальное число ГСЧ дважды, то первое возвращаемое им псевдослучайное число будет одинаковым. Это не имеет ничего общего с функциональным программированием против побочных эффектов; определение семени является то , что конкретный вход вызывает определенный вывод хорошо распределенных , но определенно не-случайных значений. Вот почему он называется псевдослучайным, и часто полезно иметь, например, писать предсказуемые модульные тесты, надежно сравнивать различные методы оптимизации для одной и той же проблемы и т. Д.

Если вы на самом деле хотите получить от компьютера не псевдослучайные числа, вам нужно подключить его к чему-то действительно случайному, например, к источнику распада частиц, непредсказуемым событиям, происходящим в сети, в которой работает компьютер, и т. Д. получить право и, как правило, дорого, даже если это работает, но это единственный способ не получить псевдослучайные значения (обычно значения, которые вы получаете от вашего языка программирования, основаны на некотором начальном числе, даже если вы явно не предоставили его).

Это и только это может поставить под угрозу функциональную природу системы. Поскольку генераторы, не являющиеся псевдослучайными, встречаются редко, это случается не часто, но да, если у вас действительно есть метод, генерирующий истинные случайные числа, то хотя бы этот маленький кусочек вашего языка программирования не может быть на 100% чисто функциональным. Будет ли язык делать исключение для него или нет, это просто вопрос прагматичности реализации языка.

Килиан Фот
источник
9
Настоящий ГСЧ вообще не может быть компьютерной программой, независимо от того, является ли она чистой (функциональной) или нет. Нам всем известна цитата фон Неймана об арифметических методах получения случайных цифр (те, кто этого не делают, ищут это - желательно все, а не только первое предложение). Вам нужно будет взаимодействовать с недетерминированным оборудованием, которое, конечно, тоже нечисто. Но это просто ввод / вывод, который несколько раз примирился с чистотой в самых разных аспектах. Ни один язык, который каким-либо образом пригоден для использования, не запрещает ввод-вывод полностью - иначе вы даже не увидите результат программы.
Что за голосование против?
10
6
Почему внешний и действительно случайный источник может поставить под угрозу функциональную природу системы? Это все еще "тот же вход -> тот же выход". Если вы не рассматриваете внешний источник как часть системы, но тогда он не будет "внешним", не так ли?
Андрес Ф.
4
Это не имеет ничего общего с PRNG против TRNG. Вы не можете иметь непостоянную функцию типа () -> Integer. Вы можете иметь чисто функциональный тип PRNG PRNG_State -> (PRNG_State, Integer), но вам придется инициализировать его нечистыми средствами).
Жиль "ТАК - перестань быть злым"
4
@ Брайан Согласен, но формулировка («подключи это к чему-то действительно случайному») предполагает, что случайный источник является внешним по отношению к системе. Следовательно, сама система остается чисто функциональной; это источник ввода, которого нет.
Андрес Ф.
6

Один из способов - думать о нем как о бесконечной последовательности случайных чисел:

IEnumerable<int> randomNumberGenerator = new RandomNumberGenerator(seed);

То есть просто думайте об этом как о бездонной структуре данных, как о том, Stackкуда вы можете только позвонить Pop, но вы можете называть это вечно. Как и в обычном неизменном стеке, взятие одного из верха дает вам другой (другой) стек.

Поэтому неизменный (с ленивым вычислением) генератор случайных чисел может выглядеть так:

class RandomNumberGenerator
{
    private readonly int nextSeed;
    private RandomNumberGenerator next;

    public RandomNumberGenerator(int seed)
    {
        this.nextSeed = this.generateNewSeed(seed);
        this.RandomNumber = this.generateRandomNumberBasedOnSeed(seed);
    }

    public int RandomNumber { get; private set; }

    public RandomNumberGenerator Next
    {
        get
        {
            if(this.next == null) this.next = new RandomNumberGenerator(this.nextSeed);
            return this.next;
        }
    }

    private static int generateNewSeed(int seed)
    {
        //...
    }

    private static int generateRandomNumberBasedOnSeed(int seed)
    {
        //...
    }
}

Это функционально.

Скотт Уитлок
источник
Я не вижу , как создать бесконечный список случайных чисел легче работать, чем функции , как: pseudoRandom :: Seed -> (Seed, Integer). Вы могли бы даже написать функцию такого типа[Integer] -> ([Integer], Integer)
dan_waterworth
2
@dan_waterworth на самом деле это имеет большой смысл. Целое число нельзя назвать случайным. Список номеров может иметь это свойство. Таким образом, случайный генератор может иметь тип int -> [int], т.е. функцию, которая берет начальное число и возвращает случайный список целых чисел. Конечно, у вас может быть государственная монада, чтобы получить нотацию Хаскелла. Но как общий ответ на вопрос, я думаю, что это действительно полезно.
Саймон Бергот
5

То же самое для не функциональных языков. Игнорирование слегка отдельной проблемы действительно случайных чисел здесь.

Генератор случайных чисел всегда принимает начальное значение и для одного и того же начального числа возвращает одну и ту же последовательность случайных чисел (очень полезно, если вам нужно протестировать программу, которая использует случайные числа). По сути, он начинается с выбранного вами начального числа, а затем использует последний результат в качестве начального значения для следующей итерации. Таким образом, большинство реализаций являются «чистыми» функциями в том виде, как вы их описываете: принимайте значение и для одного и того же значения всегда возвращайте один и тот же результат.

Торстен Мюллер
источник