Criador de Labirintos

Aleatoriedade

Em uma linguagem funcional pura como Elm, uma função chamada com os mesmos argumentos precisa sempre retornar o mesmo valor. Portanto, uma função com a assinatura de tipo rand : Int só pode ser implementada como rand = 4, o que não é nada promissor para gerar números inteiros aleatórios.

Então, como geramos valores aleatórios em Elm? Dividimos o problema em dois: primeiro, descrevemos o valor que queremos gerar com um Random.Generator a; depois, geramos um valor.

A primeira forma de gerar um valor é criar um Random.Seed com initialSeed : Int -> Seed e depois usar step : Generator a -> Seed -> ( a, Seed ), que retorna um valor e uma nova semente. Repare que essas duas funções são puras, então chamá-las duas vezes com os mesmos argumentos produzirá os mesmos valores.

A segunda forma de gerar um valor é usar generate : (a -> msg) -> Generator a -> Cmd msg, mas isso só pode ser feito dentro de uma aplicação Elm. Nesse caso, o ambiente de execução do Elm pode usar step, assim como recursos externos não puros, para gerar sementes.

De agora em diante, vamos nos concentrar nos geradores.

Vamos supor, para fins de exemplo, que definimos com initialSeed e step uma função generate : Int -> Generator a -> List a que gera uma certa quantidade de valores a partir de um gerador.

O módulo Random fornece dois geradores básicos para gerar números inteiros e números de ponto flutuante dentro de um intervalo específico:

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

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

Esses valores podem ser combinados em tuplas ou em listas de valores:

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

O pacote elm-community/random-extra fornece muito mais geradores para diversas estruturas de dados: strings, datas, dicionários, arrays, conjuntos etc.

Podemos criar geradores que retornam apenas um único valor usando Random.constant:

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

Podemos escolher aleatoriamente entre elementos dados com igual probabilidade usando Random.uniform:

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

Random.uniform recebe dois argumentos (Red e [Green, Blue]) para garantir que haja pelo menos um valor para escolher, já que uma única lista poderia estar vazia.

Também podemos ajustar as probabilidades usando Random.weighted:

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

Os valores não precisam somar 100, eles serão renormalizados de qualquer forma.

Podemos alcançar o interior de um gerador com Random.map:

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

Também podemos usar Random.map2 até Random.map5 para combinar mais geradores:

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]

Para usos mais complexos, temos Random.andThen : (a -> Generator b) -> Generator a -> Generator b, que pode usar o valor gerado por um gerador para criar outro:

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]

Às vezes é útil definir um gerador de forma autorrecursiva. Nesses casos, talvez você precise usar Random.lazy para impedir que o compilador expanda o gerador infinitamente.

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

Este exemplo é um pouco pesado, então vamos analisá-lo por partes.

Peano é um tipo que representa números inteiros positivos: Zero é 0, Next(Zero) é 1, Next(Next(Zero)) é 2 etc. Definimos peano para nos dar um número Peano aleatório.

Antes de tudo, repare que Random.lazy não adiciona nada à lógica; ele apenas impede que o compilador escreva peano dentro de peano indefinidamente.

Usamos Random.uniform para escolher entre zero (com 50% de probabilidade) e outro número Peano mais um (com 50% de probabilidade). No entanto, diferentemente do exemplo anterior, Random.uniform não está escolhendo entre valores (como Zero), mas sim entre geradores (como Random.constant Zero), já que queremos usar o próprio peano. Isso significa que Random.uniform retornará um valor do tipo Generator (Generator Peano), que não é o que precisamos.

Para "achatar" o gerador, usamos o pipe para passá-lo a Random.andThen : (a -> Generator b) -> Generator a -> Generator b, em que queremos que b seja Peano. Como Generator a é Generator (Generator Peano), a deve ser Generator Peano, e a função (a -> Generator b) deve ter o tipo (Generator Peano -> Generator Peano). Não queremos modificar nada, então identity é a escolha certa.

Por fim, que tipo de números peano vai produzir? Sabemos que ele vai produzir 0 em 50% das vezes, ou outra iteração dele mesmo mais um em 50% das vezes. Isso significa que os números serão 0 (50% das vezes), 1 (25% das vezes), 2 (12% das vezes), 3 (6% das vezes) etc. peano pode produzir números arbitrariamente grandes, mas com probabilidade decrescente de forma exponencial.