Video #30: Composable Randomness

Episode: Video #30 Date: Sep 17, 2018 Access: Members Only 🔒 URL: https://www.pointfree.co/episodes/ep30-composable-randomness

Description

Randomness is a topic that may not seem so functional, but it gives us a wonderful opportunity to explore composition. After a survey of what randomness looks like in Swift today, we’ll build a complex set of random APIs from just a single unit.

Video

Cloudflare Stream video ID: 10adf4287d56d6ab50f9728972838006 Local file: video_30_composable-randomness.mp4 *(download with --video 30)*

References

Transcript

— 0:06

Today we’re going to start a series of episodes on a topic that might not seem very functional: randomness.

— 0:13

Swift 4.2 introduces much-needed library support for randomness, which was designed from the ground up to be easier and safer to use than the existing available APIs. We’re going to take a look at some of the problems it was designed to solve and explore how we may have solved them in an alternate, functional API rooted in composition.

— 0:42

We’ll start by taking quick look at the original problems. Randomness in Swift: numbers

— 0:50

Prior to Swift 4.2, we were dependent on importing a number of C functions to produce random numbers, the most common one being arc4random , which returns a random UInt32 . import Darwin arc4random() // 2843712900

— 1:17

This isn’t the most useful interface. We almost always want a more specific random number than any unsigned, 32-bit integer. If we wanted to simulate a dice roll, we’d want a number between 1 and 6, which regularly leads to code like this: arc4random() % 6

— 1:35

Here we’re using the modulo operator to ensure a number between 0 and 5. We can add increment the result to get a number between 1 and 6. arc4random() % 6 + 1

— 1:53

This code is short and to the point, and pretty common to come across in a code base.

— 1:57

Unfortunately, it introduces what’s called “modulo bias”. Modulo bias comes into play whenever the value on the right side of the modulo operator (in this case 6) does not evenly divide UInt32.max . For in that case there are a few numbers that are underrepresented in UInt32 , and those numbers are less likely to be chosen randomly. Now, the bias is very, very tiny, on the order of 10^-10, but it’s still there and over time that can introduce real bias into your application.

— 2:29

There’s a sibling function that ships alongside arc4random called arc4random_uniform , which avoids this problem. It takes an upper limit and distributes the randomness evenly from zero. We can use it to redefine things: arc4random_uniform(6) + 1

— 2:57

This is much safer, and in fact the documentation recommends using arc4random_uniform over arc4random , but this recommendation is easy to miss or ignore, and even if you follow it, there’s almost always more work to do to make it useful, even simply adding 1 , as we do here.

— 3:12

Things become more of a mess when we want a more complicated range of numbers, say, a year starting at 1984 through 2018: arc4random_uniform(2018 - 1984) + 1984

— 3:43

This isn’t quite right because it generates numbers to, not through, 2018 , so the upper limit it will ever generate is 2017 . If we want to include 2018 , we need to remember to do a little extra math. arc4random_uniform(2018 + 1 - 1984) + 1984

— 4:00

This is gross, but at least we can bake it into its own function: func arc4random_uniform(between a: UInt32, and b: UInt32) -> UInt32 { return arc4random_uniform(b + 1 - a) + a } arc4random_uniform(between: 1984, and: 2018)

— 4:39

Now we have a friendlier, baseline API that bakes in common math that’s easy to get a bit wrong. We’re still kinda trapped in the world of UInt32 s, though, which don’t really translate nicely to other number types. Randomness in Swift: elements

— 4:54

Let’s look at one more common task we use randomness for: plucking a random element from an array.

— 5:00

Let’s say we have a type representing moves for a rock-paper-scissors game. We can use CaseIterable to get access to an array of all possible moves. enum Move: CaseIterable { case rock, paper, scissors } Move.allCases // [rock, paper, scissors]

— 5:17

If we want to pluck a random move, we can subscript into this array by passing its element count to arc4random_uniform . Move.allCases[Int(arc4random_uniform(UInt32(Move.allCases.count)))]

— 5:50

This is a bit verbose with the Int - UInt32 dance, but it’s not so bad. Still, it’s another common-enough operation that we might wanna define a helper for it. func arc4random_uniform<A>(element xs: [A]) -> A { return xs[Int(arc4random_uniform(UInt32(xs.count)))] } arc4random_uniform(element: Move.allCases)

— 6:45

But whenever we deal with index-based logic, it means that things are a bit more complicated. arc4random_uniform(element: []) Fatal error: Index out of range

— 7:12

Empty arrays are a runtime liability that we need to consider since the compiler doesn’t consider it for us.

— 7:25

The new APIs

— 7:25

Swift 4.2 introduced a brand new API designed to tackle the problems we’ve been coming across.

— 7:37

Swift now provides an API to handle returning a number given a range. UInt32.random(in: 1984...2018)

— 8:02

In fact, there’s no way to grab any random UInt32 . UInt32.random() Error: Cannot invoke ‘random’ with no arguments This isn’t really a problem, though, since we rarely want any random UInt32 . Even if we did, we can recover this functionality explicitly: UInt32.random(in: .min ... .max)

— 8:35

This decision was made because plucking a random number from a range is a much more common use case, and providing a default interface that avoids modulo bias makes things safer.

— 8:52

The new API goes further by defining static functions on numeric types that are more suitable for use in everyday code. For example, any UInt : UInt.random(in: 1984...2018) UInt.random(in: .min ... .max)

— 9:07

We can also ask for any Int : Int.random(in: 1984...2018) Int.random(in: .min ... .max)

— 9:13

It’s nice that the new APIs give us the ability to generate random numbers from more numbers than the UInt32 , which is what arc4random did.

— 9:30

This API still comes with a runtime caveat: an exclusive, empty range will crash. Int.random(in: 0..<0) Fatal error: Can’t get random value with an empty range

— 9:48

So this is what Swift gives us with respect to generating random values. Swift also gives us a new API for plucking random elements from arrays. Move.allCases.randomElement()

— 10:17

In this case, the element returned is wrapped in an optional, so if we try to pluck a random element from an empty array, we’ll get nil . [].randomElement() // nil Randomness in Swift: more

— 10:40

Random ranges of integers and random elements are super common, but the new API goes further and provides ways of generating random values on a few more types. We can, for example, generate a random Double within a range of doubles. Double.random(in: 0...1)

— 11:05

We can even generate a random Bool . Bool.random()

— 11:09

The arc4random way wasn’t so bad, but the new sugar is still nice. arc4random() % 2 == 0

— 11:28

The logic for generating a random Double would require a lot more work. Swift provides it for us.

— 11:40

Swift’s new randomness API solves a bunch of problems and even ships with some new sugar. It also deals with the fact that arc4random isn’t available on all platforms, which means all of the helpers we wrote won’t work on Linux. Rethinking randomness

— 12:32

The Swift API for randomness is kinda disconnected. It consists of a bunch of individual ideas that don’t really combine in any interesting ways. Today we are going to start over and explore what a random API could look like with composition in mind. We’ll aim to build the API off a few base, composable units that can then be built up to create more complex objects.

— 12:49

Let’s start by looking at arc4random again: arc4random // () -> UInt32

— 12:54

It’s a free function takes zero arguments and produces a UInt32 . We love free functions on Point-Free.

— 13:03

We love free functions because we can compose them, so maybe we can use plain ole function composition to transform arc4random into random functions that return more useful values.

— 13:14

Let’s say we wanted to build a function that produced a uniform, random Double between 0 and 1 . We’d wanna compose the following signatures. // () -> UInt32 // (UInt32) -> Double

— 13:33

We can use the arrow operator, which we introduced in our very first episode , to glue these functions together. let uniform = arc4random >>> { Double($0) / Double(UInt32.max) } // () -> Double

— 14:26

This looks promising, but as soon as we try to use it. uniform() Missing argument for parameter #1

— 14:30

The compiler is complaining because uniform expects an argument: Void . uniform(())

— 14:44

This works, but it isn’t a great start. Swift’s taken a zero-argument input and promoted it to a one-argument input in Void . It’s a non-intuitive quirk of Swift and likely to never be changed unfortunately.

— 15:07

For the sake of ergonomics, let’s define our own type that’ll act as a context that represents randomness. We’ll call it Gen , to represent a “generator” of random values, and it’ll be generic over the type of value it generates. struct Gen<A> { let run: () -> A }

— 15:33

We can now create a generator that merely wraps arc4random . let random = Gen(run: arc4random) // Gen<UInt32>

— 15:45

It works as we expect. When we call run on the generator we get a random number. random.run()

— 15:49

Given a Gen value, what are some ways that we can derive all new generators from it? Well, Gen is closely related to the Func type that has made an appearance a few times on this series: The Many Faces of Map The Many Faces of Zip: Part 2 The Many Faces of Zip: Part 3 struct Func<A, B> { let run: (A) -> B }

— 16:00

Except with Gen we fix the input type A with an empty tuple.

— 16:11

And we saw in our episode on map that Func has a map -like operation, which allows us to lift functions between types up to functions on Func ‘s. This is a very important tool for generating new generators from existing. So, let’s define map on Gen : extension Gen { func map<B>(_ f: @escaping (A) -> B) -> Gen<B> { return Gen<B> { f(self.run()) } } }

— 17:00

This is almost exactly like the map we defined on the Func type. The only difference is the weird Void and empty argument list quirk of Swift that we mentioned before.

— 17:09

We can test it out by doing a silly transformation. random.map(String.init) // Gen<String>

— 17:20

And now we have a brand new generator of strings that, when run, produces the string representation of a random UInt32 .

— 17:38

Let’s build a more useful generator, like the one that returns uniform Double values between 0 and 1 : let uniform = random.map { Double($0) / Double(UInt32.max) } // Gen<Double>

— 17:53

This is a brand new, reusable generator that we created it in a single line. We’re seeing that map on Gen is really just post-composition on its function.

— 18:05

Using it is simple enough. uniform.run()

— 18:16

We can use this uniform generator to derive additional generators.

— 18:26

For example, what if we wanted to generate a random Double within a specified range? func double(in range: ClosedRange<Double>) -> Gen<Double> { return uniform.map { t in t * (range.upperBound - range.lowerBound) + range.lowerBound } } We used a very simple “linear interpolation” formula to stretch the range 0 to 1 to any range. The uniform generator produces a value we can use to multiply against the range’s delta to get a random value inside that difference. We then add the range’s lower bound back to the result to ensure a number between the lower and upper bound.

— 20:13

Let’s try it out. double(in: 2...10) // Gen<Double>

— 20:22

We get a whole new generator of doubles, so let’s run it. double(in: 2...10).run()

— 20:33

It even works with negatives. double(in: -2...10).run()

— 20:44

Let’s compare ours to Swift’s new API. double(in: -2...10).run() Double.random(in: -2...10)

— 20:55

Our expressions aren’t any longer than the API Swift gives us, so that’s nice. But what’s really nice about our version is that double(in:) is really being powered by uniform , which is really being powered by random , our base unit of randomness, which was being delegated to arc4random . This is what it means to focus on small, composable units to build up larger, more complex machinery.

— 21:29

What if we want to generate a random Int from a given range? Now we may think we can take our new double(in:) function and derive int(in:) , but we’d quickly run into some serious problems with lossy Int - Double conversions and Int overflow.

— 21:49

We’re going to have to take a different path to solve this problem. The first step is to create a generator of random UInt64 s based off our random generator of UInt32 s with a fun trick. let uint64: Gen<UInt64> = .init { let lower = UInt64(random.run()) let upper = UInt64(random.run()) << 32 return lower + upper } Here we run our base generator of UInt32 twice, shifting one of the results by 32-bits to cover all 64-bits before combining them. This is a fun lil bit-shifting trick to generate uniform randomness for 64 bits by generating randomness in 32 bits…twice! uint64.run()

— 23:21

Now what about an Int given a range? We want to avoid problems around modulo bias and bounds-related overflow, which is complicated! We’re going to paste in a solution that’s similar to the implementation found in the Swift standard library. func int(in range: ClosedRange<Int>) -> Gen<Int> { return .init { var delta = UInt64( truncatingIfNeeded: range.upperBound &- range.lowerBound ) if delta == UInt64.max { return Int(truncatingIfNeeded: uint64.run()) } delta += 1 let tmp = UInt64.max % delta + 1 let upperBound = tmp == delta ? 0 : tmp var random: UInt64 = 0 repeat { random = uint64.run() } while random < upperBound return Int( truncatingIfNeeded: UInt64(truncatingIfNeeded: range.lowerBound) &+ random % delta ) } } The details aren’t important, but it’s worth noting that is uses our uint64 generator inside.

— 24:11

So let’s use it. int(in: -2...10) // Gen<Int> And now we have a brand new generator of Int s. Let’s run it. int(in: -2...10).run()

— 24:34

A nice thing about these generators is we now have a lightweight way of building reusable new ones. For example, the roll of a die: let roll = int(in: 1...6) // Gen<Int> It’s worth noting that roll isn’t a random number between one and six, it’s the ability to generate a random number between one and six. It’s a first-class value of Gen<Int> representing a random dice roll.

— 25:07

And remember Swift’s new Bool.random() API? Well, we can derive a similar generator quite easily: let bool = int(in: 0...1).map { $0 == 1 } // Gen<Bool>

— 25:27

And now we have a generator of random booleans just like that.

— 25:31

We can use it and compare it to Swift’s API. bool.run() Boolean.random()

— 25:41

The remaining feature our API lacks is plucking a random element from an array in a safe way. Our int generator makes this relatively easy. func element<A>(of xs: [A]) -> Gen<A?> { return int(in: 0...(xs.count - 1)).map { idx in guard !xs.isEmpty else { return nil } return xs[idx] } }

— 26:47

And we can create a new generator of rock-paper-scissors moves. let move = element(of: Move.allCases) // Gen<Move?>

— 27:06

And now we have a first-class value generator of optional moves. move.run() What’s the point?

— 27:15

We’ve now recreated most of Swift’s new API with our Gen type, which encapsulates the notion of randomness and has a map method that allows us to compose and create new generators out of old generators. It’s super composable and we were able to derive all of our generators from a single base generator. As cool as that all is, it’s probably time to ask: “what’s the point?” The Swift designers didn’t give us this API. They instead gave us their own collection of APIs. So why go against the grain and use our Gen type instead? Is it worth it?

— 27:58

We think so!

— 28:11

Let’s take a look at that last generator. move // Gen<Move?> This API returns an optional, which is safe, but we know that Move.allCases is never empty, so it’s a bit silly that we don’t generate an unwrapped value. We can hide this detail from our public API by mapping over the generator and force-unwrap its optional value. let move = element(of: Move.allCases).map { $0! } // Gen<Move>

— 28:42

And now we have a generator of non-optional moves, which is going to be a much more useful type throughout our application.

— 28:52

And this move generator can be used and reused! We’ve localized the unwrapping to one place in our code base. If we were calling randomElement we’d be tempted to just unwrap at the call site wherever we need a random move. Move.allCases.randomElement()!

— 29:43

Lightweight composition is much more at-hand with Gen because it has first-class support for composition: map . We’re not shackled to a static, unchanging API: we can take existing generators and derive whole new generators from them.

— 30:07

So just what other kinds of generators can we cook up that don’t exist in Swift’s new API? Gen<[A]>

— 30:17

While Swift has random defined on Bool and a bunch of numeric types, and has randomElement defined on arrays, why doesn’t it have random defined on arrays? [Element].random()

— 30:35

Well, we could extend Gen to return an array of random values given a count. extension Gen { func array(count: Int) -> Gen<[A]> { return Gen<[A]> { Array(repeating: (), count: count).map(self.run) } } }

— 31:29

For example, what if we wanted to roll a pair of dice? roll.array(count: 2)

— 31:49

This is something useful that Swift does not and cannot provide for us because it has no base unit of composition that allows for it. And remember, it’s a reusable unit. let rollPair = roll.array(count: 2) rollPair.run() rollPair.run() rollPair.run()

— 32:31

We now have the ability to take any generator of values and transform it into a generator of arrays. The arrays are of a fixed size, though. What if we wanted the size to be random? Well, we can use a generator for the count. extension Gen { func array(count: Gen<Int>) -> Gen<[A]> { return .init { Array(repeating: (), count: count.run()).map(self.run) } } } All we had to do was call count.run() , though it’s also fun that we could have implemented this function using map . extension Gen { func array(count: Gen<Int>) -> Gen<[A]> { return count.map { self.array(count: $0).run() } } }

— 33:26

What we have here is basically a higher-order generator: it’s a generator that combines a bunch of generators into one.

— 33:34

Let’s try it out. let aFewMoves = move.array(count: int(in: 0...3)) // Gen<[Move]>

— 33:55

And now we have a generator of arrays of moves. Let’s try it out. aFewMoves.run()

— 34:08

I think we’re really starting to see the point here. We were able to take a bunch of small units and compose them in more and more complex ways, which is something we couldn’t see in the more static APIs that shipped with Swift.

— 34:34

And for those times you don’t want the size to be random, but only the contents, you can always recover the previous functionality by simply providing a generator that always returns the same value: let rollPair = roll.array(count: .init { 2 })

— 35:01

A generator that always returns the same thing certainly isn’t very random, but there’s nothing stopping us from doing that. Goes to show how flexible this idea is. Gen

— 35:25

Let’s explore one more example of combining generators together and creating all new kinds of generators. What would it take to generate a password like those that Safari generates?

— 35:39

We want something to generate of the form: // huwKun-1zyjxi-nyxseh

— 35:46

Three segments of 6 random alphanumeric characters joined by hyphens.

— 35:52

Let’s think of randomness in terms of units that this kind of password is composed of. The smallest unit is the character. Given all of our potential characters: let chars = Array( "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" )

— 36:09

We can create a generator of alphanumeric characters. let alphanum = element(of: chars).map { $0! } // Gen<Character>

— 36:32

From this, we can create a generator of password segments. let passwordSegment = alphanum.array(count: .init { 6 }) .map { $0.map(String.init).joined() } // Gen<String> Here we took our array method to first produce a generator of arrays of 6 characters. Then we mapped into that generator, further mapped into the array inside, transformed each character to a string, and joined them together to produce a generator of strings.

— 37:21

And finally, we can create a password generator. let password = passwordSegment.array(count: .init { 3 }) .map { $0.joined(separator: "-") } // Gen<String>

— 37:42

Let’s take it for a spin. password.run() And we have a very random password! Conclusion

— 37:56

We started with simple units that mirrored Swift’s APIs. From these units, we were able to quickly and expressively derive new, more complex units that go far beyond Swift’s APIs. And this was all unlocked by composition. We were able to generate random arrays of elements by combining a random value generator with a random count generator. We were even able to generate random passwords by building from a bunch of tiny units!

— 38:34

And because we were focused on composition, we were able to base all of our many generators off a single unit: the random generator wrapping arc4random .

— 38:53

And if we look at our playground, we can see the number of times this unit was called for a single execution. In our most recent run it’s called 220 times! This one, single unit is powering everything , and that’s the power of composition! When you focus on small, composable units, and when you have the ability to generate new units from old units, you start to unlock so many things. This is just another example of what composition unlocks.

— 40:01

We still have a lot to explore in the world of randomness, but that will have to wait till next time! References Random Zalgo Generator Brandon Williams • Nov 20, 2018 We apply the ideas of composable randomness to build a random Zalgo generator, which is a way to apply gitchy artifacts to a string by adding strange unicode characters to it. It shows that we can start with very simple, small pieces and then compose them together to create a really complicated machine. https://www.pointfree.co/blog/posts/19-random-zalgo-generator Downloads Sample code 0030-composable-randomness Point-Free A hub for advanced Swift programming. Brought to you by Brandon Williams and Stephen Celis . Content Become a member The Point-Free Way Beta previews Gifts Videos Collections Free clips Blog More About Us Community Slack Mastodon Twitter BlueSky GitHub Contact Us Privacy Policy © 2026 Point-Free, Inc. All rights are reserved for the videos and transcripts on this site. All other content is licensed under CC BY-NC-SA 4.0 , and the underlying source code to run this site is licensed under the MIT License .