Творець лабіринтів

Випадковість

У чистій функціональній мові, як-от Elm, функція, викликана з тими самими аргументами, повинна завжди повертати те саме значення. Тому функцію із сигнатурою типу rand : Int можна реалізувати лише як rand = 4, що не віщує нічого доброго для генерації випадкових цілих чисел.

То як нам генерувати випадкові значення в Elm? Розділімо задачу на дві частини: спершу ми описуємо значення, яке хочемо згенерувати, за допомогою Random.Generator a, а потім генеруємо значення.

Перший спосіб згенерувати значення - створити Random.Seed за допомогою initialSeed : Int -> Seed, а потім скористатися step : Generator a -> Seed -> ( a, Seed ), яка повертає значення та нове зерно. Зауважмо, що обидві ці функції чисті, тож виклик їх двічі з тими самими аргументами дасть ті самі значення.

Другий спосіб згенерувати значення - скористатися generate : (a -> msg) -> Generator a -> Cmd msg, але це можна зробити лише всередині застосунку Elm. У такому разі середовище виконання Elm може використовувати step, а також зовнішні нечисті ресурси для генерації зерен.

Надалі ми зосередимося на генераторах.

Уявімо заради прикладів, що ми визначили за допомогою initialSeed і step функцію generate : Int -> Generator a -> List a, яка генерує кілька значень із генератора.

Модуль Random надає два базові генератори для цілих чисел і чисел з плаваючою комою в заданому діапазоні:

generate 5 (Random.int -5 5)
    --> [0, 3, -5, 5, 0]

generate 3 (Random.float 0 5)
    --> [1.61803, 3.14159, 2.71828]

Ці значення можна поєднати в кортежі або в масиви значень:

generate 2 (Random.list 3 (Random.int 0 3))
    --> [[0, 3, 3], [1, 3, 2]]

generate 2 (Random.pair (Random.int 0 3) (Random.float 10 10.3))
    --> [(0, 10.23412), (2, 10.17094)]

Пакет elm-community/random-extra надає значно більше генераторів для різних структур даних: рядків тексту (англ. string), дат, словників, масивів, множин тощо.

Ми можемо створювати генератори, які повертатимуть лише одне значення, за допомогою Random.constant:

generate 4 (Random.constant "hello")
    --> ["hello", "hello", "hello", "hello"]

Ми можемо випадково обирати із заданих елементів з однаковою ймовірністю за допомогою Random.uniform:

generate 5 (Random.uniform Red [Green, Blue])
    --> [Red, Blue, Blue, Green, Red]

Random.uniform приймає два аргументи (Red і [Green, Blue]), щоб гарантувати, що є принаймні одне значення для вибору, адже один список міг би бути порожнім.

Ми також можемо скоригувати ймовірності за допомогою Random.weighted:

generate 5 (Random.weighted (80, Red) [(15, Green), (5, Blue)])
    --> [Red, Red, Green, Red, Red]

Значення не обовʼязково мають давати в сумі 100, їх усе одно буде перенормовано.

Ми можемо зазирнути всередину генератора за допомогою Random.map:

generate 3 (Random.int 1 6 |> Random.map (\n -> n * 10))
    --> [30, 60, 10]

Ми також можемо використовувати Random.map2 аж до Random.map5, щоб поєднувати більше генераторів:

position =
    Random.map3
      (\x y z -> Position x y z)
      (Random.float -100 100)
      (Random.float -100 100)
      (Random.float -100 100)

generate 1 position
    --> [Position 33.788 -98.321 10.0845]

Для складніших потреб у нас є Random.andThen : (a -> Generator b) -> Generator a -> Generator b, який може використати значення, згенероване одним генератором, щоб створити інший:

bool = Random.uniform True [False]

failHalfOfTheTime : Generator a -> Generator (Maybe a)
failHalfOfTheTime generator =
    bool
        |> Random.andThen
            (\boolResult ->
                if boolResult then
                    Random.map Just generator

                else
                    Random.constant Nothing
            )

generate 6 (Random.int 0 1 |> failHalfOfTheTime)
    --> [Nothing, Just 1, Just 0, Nothing, Just 1, Nothing]

Іноді корисно визначити генератор, що посилається сам на себе. У таких випадках може знадобитися Random.lazy, щоб не дати компілятору розгортати генератор нескінченно.

type Peano
    = Zero
    | Next Peano


peano : Generator Peano
peano =
    Random.uniform (Random.constant Zero)
        [ Random.map Next (Random.lazy (\_ -> peano))
        ]
        |> Random.andThen identity

generate 12 peano
    --> [Zero, Next(Next(Zero)), Zero, Next(Zero), Zero, Zero, Next(Zero), Zero, Zero, Next(Zero), Next(Next(Next(Zero)))]

Цей приклад трохи складний, тож розберімо його.

Peano - це тип, який представляє додатні цілі числа: Zero - це 0, Next(Zero) - це 1, Next(Next(Zero)) - це 2 тощо. Ми визначаємо peano, щоб отримати випадкове число Peano.

Насамперед зауважмо, що Random.lazy нічого не додає до логіки, він лише заважає компілятору нескінченно вписувати peano в peano.

Ми використовуємо Random.uniform, щоб обрати між нулем (з імовірністю 50%) та іншим числом Peano плюс один (з імовірністю 50%). Однак, на відміну від попереднього прикладу, Random.uniform обирає не з-поміж значень (як-от Zero), а з-поміж генераторів (як-от Random.constant Zero), бо ми хочемо використати сам peano. Це означає, що Random.uniform поверне значення типу Generator (Generator Peano), а це не те, що нам потрібно.

Щоб «сплюснути» генератор, ми передаємо його в Random.andThen : (a -> Generator b) -> Generator a -> Generator b, де ми хочемо, щоб b було Peano. Оскільки Generator a - це Generator (Generator Peano), то a має бути Generator Peano, а функція (a -> Generator b) має бути типу (Generator Peano -> Generator Peano). Ми не хочемо нічого змінювати, тож identity - правильний вибір.

Нарешті, які числа буде давати peano? Ми знаємо, що він буде давати 0 у 50% випадків або ще одну ітерацію самого себе плюс один у 50% випадків. Це означає, що числа будуть 0 (у 50% випадків), 1 (у 25% випадків), 2 (у 12% випадків), 3 (у 6% випадків) тощо. peano може давати довільно великі числа, але з імовірністю, що експоненційно спадає.