Criador de Labirintos

Random

Numa linguagem puramente funcional como o Elm, uma função chamada com os mesmos argumentos tem de devolver sempre o mesmo valor. Por isso, uma função com a assinatura de tipo rand : Int só pode ser implementada como rand = 4, o que não augura nada de bom para gerar números inteiros aleatórios.

Então como é que 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 uma Random.Seed através de initialSeed : Int -> Seed e depois usar step : Generator a -> Seed -> ( a, Seed ), que devolve um valor e uma nova semente. Repara que ambas as funções são puras, por isso chamá-las duas vezes com os mesmos argumentos produz 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 runtime do Elm pode usar step, bem como recursos externos não puros, para gerar sementes.

A partir de agora, vamos focar-nos nos geradores.

Vamos supor, para efeitos de exemplo, que definimos com initialSeed e step uma função generate : Int -> Generator a -> List a que gera uma série 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 vírgula 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 tuplos, 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 muitos mais geradores para várias estruturas de dados: strings, datas, dicionários, arrays, conjuntos, etc.

Podemos criar geradores que devolvem apenas um único valor com Random.constant:

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

Podemos escolher aleatoriamente entre determinados elementos, com igual probabilidade, com 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 há pelo menos um valor de onde escolher, uma vez que uma única lista poderia estar vazia.

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

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

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

Podemos chegar ao 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 utilizações mais complexas, 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]

Por vezes, é útil definir um gerador de forma autorrecursiva. Nesses casos, podes precisar de 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, por isso 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 mais, repara que Random.lazy não acrescenta nada à lógica: 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, ao contrário do exemplo anterior, Random.uniform não está a escolher entre valores (como Zero), mas sim entre geradores (como Random.constant Zero), uma vez que queremos usar o próprio peano. Isto significa que Random.uniform vai devolver um valor do tipo Generator (Generator Peano), que não é o que precisamos.

Para «achatar» o gerador, encaminhamo-lo para Random.andThen : (a -> Generator b) -> Generator a -> Generator b, onde queremos que b seja Peano. Como Generator a é Generator (Generator Peano), a tem de ser Generator Peano, e a função (a -> Generator b) tem de ser do tipo (Generator Peano -> Generator Peano). Não queremos modificar nada, por isso identity é a escolha certa.

Por fim, que tipo de números vai o peano produzir? Sabemos que vai produzir 0 em 50% dos casos, ou outra iteração de si próprio mais um nos restantes 50%. 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. O peano pode produzir números arbitrariamente grandes, mas com probabilidade decrescente de forma exponencial.