Maze Maker

Random

In a pure functional language like Elm, a function called with the same arguments must always return the same value. Therefore a function with the type signature rand : Int can only be implemented as rand = 4, which does not bode well for generating random integers.

So how do we generate random values in Elm? We split the problem in two: first, we describe the value that we want to generate with a Random.Generator a, then we generate a value.

The first way to generate a value is to create a Random.Seed via initialSeed : Int -> Seed and then use step : Generator a -> Seed -> ( a, Seed ), which returns a value and a new seed. Note that both of these functions are pure, so calling them twice with the same arguments will produce the same values.

The second way to generate a value is by using generate : (a -> msg) -> Generator a -> Cmd msg, but that can only be done inside an Elm application. In that case, the Elm runtime may use step as well as outside, non-pure resources to generate seeds.

From now on, we will focus on generators.

Let us pretend, for the sake of showing examples, that we have defined with initialSeed and step a function generate : Int -> Generator a -> List a that generates a number of values from a generator.

The Random module provides two basic generators for generating integers and floats within a specific range:

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

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

Those values can be combined into tuples, or into lists of values:

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)]

The elm-community/random-extra package provides a lot more generators for various data structures: strings, dates, dictionaries, arrays, sets, etc.

We can create generators that will only return a single value using Random.constant:

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

We can randomly pick from given elements with equal probability using Random.uniform:

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

Random.uniform takes two arguments (Red and [Green, Blue]) to guarantee that there is at least one value to pick from, since a single list could be empty.

We can also tweak the probabilities using Random.weighted:

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

The values do not need to add up to 100, they will get renormalized anyway.

We can reach the inside of a generator with Random.map:

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

We can also use Random.map2 all the way to Random.map5 to combine more generators:

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]

For more complex uses, we have Random.andThen : (a -> Generator b) -> Generator a -> Generator b that can use the value generated by one generator to create another:

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]

It is sometimes useful to define a generator self-recursively. In those cases, you might need to use Random.lazy to keep the compiler from unrolling the generator infinitely.

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)))]

This example is a little heavy, so let's break it down.

Peano is a type that represents positive integers: Zero is 0, Next(Zero) is 1, Next(Next(Zero)) is 2, etc. We define peano to give us a random Peano number.

First of all, note that Random.lazy doesn't add anything to the logic, it merely prevents the compiler from writing peano into peano indefinitely.

We use Random.uniform to pick between zero (with 50% probability) and another Peano number plus one (with 50% probability). However, unlike with the previous example, Random.uniform is not picking from values (like Zero) but instead from generators (like Random.constant Zero) since we want to use peano itself. This means that Random.uniform will return a value of type Generator (Generator Peano), which is not want we need.

To "flatten" the generator, we pipe it into Random.andThen : (a -> Generator b) -> Generator a -> Generator b, where we want b to be Peano. Since Generator a is Generator (Generator Peano), a must be Generator Peano, and the function (a -> Generator b) must be of type (Generator Peano -> Generator Peano). We don't want to modify anything, so identity is the right choice.

Finally, what kind of numbers will peano produce? We know that it will produce 0 50% of the time, or another iteration of itself plus one 50% of the time. That means the numbers will be 0 (50% of the time), 1 (25% of the time), 2 (12% of the time), 3 (6% of the time), etc. peano can produce arbitrary large numbers, but with exponentially decreasing probability.