--- title: Rolling Random Romans teaser: A dive into functional random generators. tags: elm,functional programming author: Joël Quenneville published_on: 2016-04-18 --- I've recently been reading about the Roman Republic as well as digging into the [Elm language][elm-lang]. I decided to try my hand at randomly generating Roman names. This would involve multiple random components, both dependent and independent. [elm-lang]: http://elm-lang.org/ ## Roman names Romans names during the republican period followed a pattern known as the _tria nomina_. They were composed of: * **Praenomen** a personal name given to an individual. * **Nomen** a family or clan name. * **Cognomen** an optional nickname. Some of these were hereditary and identified particular branches of a family. * **Agnomen** an optional nickname, given if you already had a cognomen. ## Random in a functional world In a functional language like Elm, all functions must be **pure**, that is that a function should always return the same output given the same arguments. Random operations are inherently **not pure**. You call your random function and might get a different value each time. That's the whole point. Elm tackles this issue via a divide-and-conquer approach. It separates the process of **generating randomness** from the process of **converting that randomness into data or operations** such as a number or picking an item from a list. Randomness in Elm is represented by a `Seed` while values are generated from `Generator`s. The two are combined together with the `Random.generate` function to generate a random value based on the randomness of the seed. [`Random.generate : Generator a -> Seed -> (a, Seed)`] is a pure function, it will return the same value every time it is called with the same seed and generator. Note that is type of random number generation, called [deterministic random or pseudorandom] generation, while great for applications like procedurally generating a game level or displaying a list in random order is not cryptographically secure and should not be used for security-related functionality. [`Random.generate : Generator a -> Seed -> (a, Seed)`]: http://package.elm-lang.org/packages/elm-lang/core/2.1.0/Random#generate [deterministic random or pseudorandom]: https://en.wikipedia.org/wiki/Pseudorandom_number_generator ## Dealing with seeds We still haven't solved the issue. Where do the random seeds come from? Is this a "turtles all the way down" kind of problem? At least initially, the random seed is passed into the program from the outside world. It could be generated by JavaScript and passed in via a port, it might come from a time signal, it might even be user input (a common pattern when generating maps in games). Once we have a seed, we don't want to keep using it multiple times because that will keep giving us the same values. To solve this problem, `Random.generate` doesn't just return a random value. Instead it returns a tuple of `(value, newSeed)`. We can then use this new seed in our next random calculation. Any number of random operations can be chained together like this, each using the seed generated by the previous operation. ![diagram of chaining random operations and passing seeds](https://images.thoughtbot.com/rolling-random-romans/CXmzyILZRnerZZw24S5U_random-generate.png) ## Thinking in generators Dealing with seeds quickly gets cumbersome, particularly when generating more complex random data. There are at least 6 random operations required to generate our random Roman names: * pick a random praenomen from a `Generator String` * pick a random nomen from a `Generator String` * randomly decide if this character has a cognomen from a `Generator Bool` * if yes pick a random cognomen from a `Generator String` * randomly decide if this character has an agnomen from a `Generator Bool` * if yes pick a random agnomen from a `Generator String` In an imperative language, I would generate these 6 values individually and then combine them together to get a full name. In Elm, it's better to transform and combine simple generators into more complex generators. Ideally, we would only call `Random.generate` once with a `Generator Roman`. ## Simple transformations The [`NoRedInk/elm-random-extra`] package provides some great utility functions that are not available in the core `Random` module. In particular, it provides the [`selectWithDefault : a -> List a -> Generator a`] function that picks a random value from a list or returns a default if the list is empty. We can use this to create a generator of praenomenina: ```elm import Random.Extra as RandomE import Random exposing(Generator) praenomen : Generator String praenomen = RandomE.selectWithDefault "Marcus" ["Marcus", "Quintus", "Gaius"] ``` Now we can define a very simple `Roman` type: ```elm type alias Roman = { praenomen : String } ``` We can transform the `praenomen` generator into a `roman` generator by using [`Random.map : (a -> b) -> Generator a -> Generator b`]. ```elm roman : Generator Roman roman = Random.map Roman praenomen ``` `Random.map` takes a function that will transform the values returned by the given generator. Here, we're using the constructor function `Roman : String -> Roman` to convert the string returned by the `praenomen` generator (e.g. "Marcus") into a roman (e.g. `{ praenomen = "Marcus" }`). Note that we haven't actually generated values here, only described how to transform them when they are generated. [`NoRedInk/elm-random-extra`]: http://package.elm-lang.org/packages/NoRedInk/elm-random-extra/2.1.1 [`selectWithDefault : a -> List a -> Generator a`]: http://package.elm-lang.org/packages/NoRedInk/elm-random-extra/2.1.1/Random-Extra#selectWithDefault [`Random.map : (a -> b) -> Generator a -> Generator b`]: http://package.elm-lang.org/packages/elm-lang/core/3.0.0/Random#map ## Combining generators Adding a `nomen` generator is very similar to our `praenomen` generator: ```elm nomen : Generator String nomen = RandomE.selectWithDefault "Julius" ["Julius", "Cornelius", "Junius"] ``` we can add a nomen to our `Roman` type: ```elm type alias Roman = { praenomen : String , nomen : String } ``` Our constructor now has two arguments: `Roman : String -> String -> Roman`. Just like `List`, `Random` has `map2`, `map3`, and friends which allow us to map a function that takes _n_ arguments over _n_ generators. ```elm roman : Generator Roman roman = Random.map2 Roman praenomen nomen ``` Again, we aren't actually generating any random values here, just saying "to generate a random Roman, generate a random praenomen and nomen and pass them to the `Roman` function". ## Complex values Adding a cognomen isn't quite as straightforward because not all Romans have one. Our `Roman` type would now look like: ```elm type alias Roman = { praenomen : String , nomen : String , cognomen : Maybe String } ``` `Maybe` represents an optional value. Valid cognomina could be `Just "Caesar"` and `Nothing`. A generator that returns `Nothing` 50% of the time and `Just String` 50% of the time might look like: ```elm import Random.Maybe as RandomM cognomen : Generator (Maybe String) cognomen = RandomE.selectWithDefault "Metellus" ["Metellus", "Caesar", "Brutus"] |> RandomM.maybe ``` The first line is familiar by now. [`Random.Maybe.maybe : Generator a -> Generator (Maybe a)`] is a function provided by the `NoRedInk/elm-random-extra` package. It takes a generator as input and will wrap the values of that generator in `Just` 50% of the time and return `Nothing` otherwise. Now we can add the `cognomen` generator to the list of generators mapped by the `roman` generator. ```elm roman : Generator Roman roman = Random.map3 Roman praenomen nomen cognomen ``` [`Random.Maybe.maybe : Generator a -> Generator (Maybe a)`]: http://package.elm-lang.org/packages/NoRedInk/elm-random-extra/2.1.1/Random-Maybe#maybe ## Dependent values Like the cognomen, the agnomen is also an optional value. ```elm type alias Roman = { praenomen : String , nomen : String , cognomen : Maybe String , agnomen : Maybe String } ``` There is a twist. _We should only roll an agnomen for Romans that already have a cognomen_. Romans with a cognomen of `Nothing` should also have an agnomen of `Nothing`. Due to this dependency, the `agnomen` generator takes in a cognomen as an argument. ```elm agnomen : Maybe String -> Generator (Maybe String) agnomen cognomen' = case cognomen' of Nothing -> RandomE.constant Nothing Just _ -> RandomE.selectWithDefault "Pius" ["Pius", "Felix", "Africanus"] |> RandomM.maybe ``` Note that the cognomen passed into this function is an actual value (`Maybe String`) and not a generator. We pattern match on that value and return either return a generator that always returns `Nothing` or a generator that randomly returns either `Nothing` or `Just` a random agnomen from the list. So how do we combine this generator with the others to get a Roman generator? `Random` provides the [`Random.andThen : Generator a -> (a -> Generator b) -> Generator b `] function that allows us to **chain two dependent random operations**. ```elm roman : Generator Roman roman = let agnomen' = cognomen `andThen` agnomen in Random.map4 Roman praenomen nomen cognomen agnomen' ``` [`Random.andThen : Generator a -> (a -> Generator b) -> Generator b `]: http://package.elm-lang.org/packages/elm-lang/core/3.0.0/Random#andThen ## Correctly combining dependent values The latest implementation of the `roman` generator has a bug in it. The `cognomen` generator is being called _twice_. Once to generate the cognomen and again when generating the agnomen. This means it is possible to get a Roman that has an agnomen but no cognomen. We want the _same cognomen_ to be used for both the Roman's cognomen and generating the agnomen. We can handle this by creating a `nickNames` generator that returns a tuple of `(cognomen, agnomen)`. Our `roman` generator would now look like: ```elm roman : Generator Roman roman = let nickNames' = cognomen `andThen` nickNames roman' pn n (cn, an) = Roman pn n cn an in Random.map3 roman' praenomen nomen nickNames' ``` We can can no longer use the `Roman` constructor directly in our `map3` function because some of the values are combined together in a tuple. Notice that we only call the `cognomen` generator once here. The `nickNames` generator would look like: ```elm nickNames : Maybe String -> Generator (Maybe String, Maybe String) nickNames cognomen = case cognomen of Just _ -> Random.map (\agnomen' -> (cognomen, agnomen')) agnomen Nothing -> RandomE.constant (Nothing, Nothing) ``` Since `nickNames` now takes care of calling the dependency on whether or not the cognomen is present, we can simplify the `agnomen` generator to: ```elm agnomen : Generator (Maybe String) agnomen = RandomE.selectWithDefault "Pius" ["Pius", "Felix", "Africanus"] |> RandomM.maybe ``` ## Viewing the results We now have a `Generator Roman` that will randomly generate a Roman with a valid _tria nomina_. Now we need to display it. We can add a `name` function that will turn a `Roman` into a formatted string. ```elm name : Roman -> String name roman = let cognomen' = Maybe.withDefault "" roman.cognomen agnomen' = Maybe.withDefault "" roman.agnomen in String.join " " [roman.praenomen, roman.nomen, cognomen', agnomen'] ``` We also need to actually generate the Roman based on a random seed passed in via a **port** and display the name to the user: ```elm randomRoman : Roman randomRoman = Random.generate RandomR.roman (Random.initialSeed jsSeed) |> fst port jsSeed : Int main : Html main = main' [] [ h1 [] [ text "Rolling Random Romans" ] , p [] [ randomRoman |> Roman.name |> text ] ] ``` Finally, we need to generate a random initial seed in javascript and pass it to the port (`main.js` is the compiled Elm program): ```html ``` That's how you roll random Romans. ## Deja vu If calling `map` and `andThen` seem familiar from working with other types such as `List`, `Signal`, and `Maybe`, that's because there is a pattern going on here. In functional terminology, types that have `map` functions are called **Functors** and types that have an `andThen` function are the infamous **Monad**. ## Lessons from `Random` Working with `Random` and `Generator`, I've learned to approach purely functional randomness with a different mindset. Some big takeaways were: * Don't call `Random.generate` all the time, instead try to **think in terms of generators**. * **Transform** generators from one type to another with `Random.map` * Combine **independent** generators together with `Random.map2` and family * Chain multiple **dependent** random operations with `Random.andThen` * Any complex generator can be built up from simpler generators via these functions. ## Rolling really realistic Romans There is a lot more fun to be had with Romans and randomness. We can keep using the patterns discussed earlier to make our generated names more realistic by adding more variables and dependencies. * Romans had a different naming scheme for women and men. We could randomly generate a gender and then conditionally generate the proper name based of the result. * Romans were also broken into two broad social classes: patricians and plebians. Some families (and thus the nomen) were exclusively patrician while others were exclusively plebian. Some families had both patrician and plebian branches. We could assign a random social status and then conditionally pick the nomen from a list of historical patrician or plebian names. * Some cognomina such as "Caesar" were hereditary and identified a particular branch of a family (in this case the Julia family). We could conditionally generate the cognomen based on the nomen from a list of historical cognomina used by that family. For characters without a hereditary cognomen we can still generate a random cognomen or `Nothing`. * Some families strongly preferred (or avoided) a set of praenomina. We could generate the praenomen biased by family preferences. * Any time we've done one thing or another, we've used a 50% chance. Not all rolls should have even distribution of outcomes. ## Source and demos I've published [the source for this article] on GitHub. I've also implemented the "really realistic" features described above as [version 2]. In addition, I've published a [demo of version 2]. [the source for this article]: https://github.com/JoelQ/rolling-random-romans/tree/v1.0.0 [version 2]: https://github.com/joelq/rolling-random-romans [demo of version 2]: https://joelq.github.io/rolling-random-romans/ ## ElmConf talk The content of this article was updated for Elm 0.18 and turned into a talk [given at the first ElmConf](https://www.youtube.com/watch?v=YxGWQdFo2Yc).