Video #20: NonEmpty

Episode: Video #20 Date: Jun 25, 2018 Access: Members Only 🔒 URL: https://www.pointfree.co/episodes/ep20-nonempty

Description

We often deal with collections that we know can never be empty, yet we use arrays to model them. Using the ideas from our last episode on algebraic data types, we develop a NonEmpty type that can be used to transform any collection into a non-empty version of itself.

Video

Cloudflare Stream video ID: 838fa29847907b8e5a8c19cd2c3fdbba Local file: video_20_nonempty.mp4 *(download with --video 20)*

References

Transcript

— 0:05

In our most recent episode on algebraic data types, we explored how we can use algebra to understand generics and recursive data structures in the Swift type system. Things got pretty abstract! We grounded the episode, though, in a useful type that doesn’t seem to get enough attention: the non-empty list—in fact, we gave it twice as much attention because math led us to two different formulas!

— 0:32

We deal with non-empty data regularly, but without a structure at hand it’s all too easy to reach for Array and inevitably we end up writing a bit of extra code to handle those empty cases. Today’s episode is all about embracing type-safe guarantees, avoiding those extra code paths, and building an ergonomic API over the non-empty list. Let’s build a low-friction, non-empty type suitable for your production code base!

— 0:57

Let’s start with what we came up with last time . Recap

— 1:07

Through some fun algebraic manipulations, we came across two different ways of looking at non-empty lists.

— 1:15

We started by defining a List type with two cases. enum List<A> { case empty indirect case cons(A, List<A>) }

— 1:47

Once we had this List type, we were able to define a NonEmptyList type as a struct that combines a required head element with a tail representing the rest of the list. struct NonEmptyList<A> { let head: A let tail: List<A> }

— 2:08

Then, through some other algebraic manipulation, we came across an equivalent, but completely different definition of a non-empty list. This time it was an enum that had a recursive case. enum NonEmptyList<A> { case singleton(A) indirect case cons(A, NonEmptyListSum<A>) }

— 2:34

We have a naming conflict, so let’s call the first type NonEmptyListProduct and the second one NonEmptyListSum . struct NonEmptyListProduct<A> { let head: A let tail: List<A> } enum NonEmptyListSum<A> { case singleton(A) indirect case cons(A, NonEmptyListSum<A>) }

— 2:44

The enum definition is pretty interesting because it doesn’t rely on another List type. Its definition is completely self-contained using recursion.

— 2:51

Both of these types are safe, but neither is particularly friendly. We’re used to working with Swift’s built-in Array type, which has a nice literal syntax. [1, 2, 3]

— 3:03

Constructing similar lists using our non-empty types is a lot noisier. NonEmptyListProduct(head: 1, tail: .cons(2, .cons(3, .empty))) NonEmptyListSum.cons(1, .cons(2, .singleton(3)))

— 3:31

Not only are these types a pain to construct, they currently lack all the functionality we expect in a collection, like looping over the elements, plucking the first (or last) element out, or just getting the element count.

— 3:48

It might be fun to reimplement this functionality ourselves, but our implementations would probably be much less performant than those that Swift ships with in the standard library. Swift also provides some impressive protocols that do most of the work for us! Let’s build a more ergonomic, non-empty type that takes advantage of these features. NonEmptyArray

— 4:17

Let’s start by defining a whole new NonEmptyArray type. struct NonEmptyArray<A> { var head: A var tail: [A] } This looks a lot like our previous struct, but rather than define our own List type, we’re utilizing Array , which ships with Swift and has all the performance characteristics we want.

— 4:38

Initializing a value is simple enough. NonEmptyArray(head: 1, tail: [2, 3]) // NonEmptyArray<Int>

— 4:48

This is already looking better than constructing our earlier types. The next thing we should do is make our debugging experience a little more pleasant. Let’s conform NonEmptyArray to CustomStringConvertible . extension NonEmptyArray: CustomStringConvertible { var description: String { return "\(head)\(tail)" } } NonEmptyArray(head: 1, tail: [2, 3]) // 1[2, 3]

— 5:09

Alright, that’s better. Next, let’s address that default initializer. It’s quite verbose. The argument labels don’t really seem necessary. extension NonEmptyArray { init(_ head: A, _ tail: [A]) { self.head = head self.tail = tail } }

— 5:31

Now, instantiating a non-empty list looks a bit better. NonEmptyArray(1, [2, 3]) // 1[2, 3]

— 5:37

But it’s kind of annoying to have to pass an empty array for non-empty arrays with a single element. NonEmptyArray(1, []) // 1[]

— 5:49

We could clean that up using a default argument. extension NonEmptyArray { init(_ head: A, _ tail: [A] = []) { self.init(head: head, tail: tail) } } NonEmptyArray(1) // 1[]

— 5:56

But better yet, we can use variadics and make constructing values look really nice. extension NonEmptyArray { init(_ head: A, _ tail: A...) { self.head = head self.tail = tail } } NonEmptyArray(1) // 1[] NonEmptyArray(1, 2, 3) // 1[2, 3]

— 6:34

We still have to do a bit of work to do to make this type nice to use. In order to unlock a bunch of standard library functionality, we need to conform this type to Swift’s Collection protocol. extension NonEmptyArray: Collection { }

— 6:54

Conforming to Collection is a matter of implementing the requirements mentioned in the documentation. Note The startIndex and endIndex properties A subscript that provides at least read-only access to your type’s elements The index(after:) method for advancing an index into your collection

— 7:33

Let’s conform using just a little math to account for our extra head element. extension NonEmptyArray: Collection { var startIndex: Int { return 0 } var endIndex: Int { return self.tail.endIndex + 1 } subscript(position: Int) -> A { return position == 0 ? self.head : self.tail[position - 1] } func index(after i: Int) -> Int { return i + 1 } }

— 8:33

Everything builds and we now have access to a lot of reusable code! let xs = NonEmptyArray(1, 2, 3) xs.forEach { print($0) } xs.count // 3 xs.first // 1

— 9:11

We have an issue, though, that we discussed briefly in our previous episode . The default implementation of first returns an Optional , which makes sense for collections that can be empty, but our type doesn’t have this problem. Luckily, as we saw last time, we can write an overload that assumes non-optionality! extension NonEmptyArray { var first: A { return self.head } }

— 9:37

This relies on a quirk of the Swift type system on how it handles optionals and overloads.

— 9:51

Now we have immediate access to the first element. No need to unwrap an optional. xs.first + 1 // 2

— 10:02

What about last ? xs.last Value of type ‘NonEmptyArray ’ has no member ‘last’

— 10:09

We’ve so far only done a minimal conformance to Collection , but Array has been equipped with a much richer structure. In this case, last is only available on types that also conform to BidirectionalCollection , which are collections that supports backward as well as forward traversal.

— 10:30

That’s easy enough to add, though! extension NonEmptyArray: BidirectionalCollection { func index(before i: Int) -> Int { return i - 1 } }

— 10:52

We can now grab the last element off our non-empty array, but it has the same problem that first had: it’s optional. Let’s write another overload. extension NonEmptyArray { var last: A { return self.tail.last ?? self.head } } And now we have immediate access to the last element. xs.last + 1 // 4

— 11:31

This wasn’t a lot of code but we already have something that’s pretty nice to use and useful! We could continue to add to it or start using it in real code. NonEmptyCollection

— 11:53

Our NonEmptyArray type is nice, but there are plenty of other collection types out there that would be useful to have non-empty versions of, like sets and dictionaries and even custom collections that we may have defined ourselves. With our current approach, we’d need to start from scratch every time!

— 12:15

Let’s start over and try to build a type that can be used with any collection, not just Array s. struct NonEmpty<C: Collection> { var head: C.Element var tail: C }

— 12:41

This looks a lot like NonEmptyArray , but we’re now generic over the collection type. It’s also clearly non-empty because it has to contain at least one element in the head .

— 12:54

Instantiation still isn’t nice. NonEmpty<[Int]>(head: 1, tail: [2, 3]) // NonEmpty<Array<Int>>

— 13:08

Like last time, we want to build a better initializer. init(_ head: C.Element, _ tail: C.Element...) { self.head = head self.tail = tail } Cannot assign value of type ‘[C.Element]’ to type ‘C’ Unfortunately, we can’t make a variadic initializer. The variadic argument, tail , is an Array , not the generic Collection we need, and there’s no way of converting an array into any Collection .

— 13:47

We can at least drop the argument labels. init(_ head: C.Element, _ tail: C) { self.head = head self.tail = tail }

— 13:54

So now this is what instantiating a non-empty array looks like: NonEmpty<[Int]>(1, [2, 3]) // NonEmpty<Array<Int>>

— 13:58

What about a value where the tail’s empty? NonEmpty<[Int]>(1, []) // NonEmpty<Array<Int>> It’s be nice to get rid of those empty brackets, but we can’t use a default argument like last time. init(_ head: C.Element, _ tail: C = []) { self.head = head self.tail = tail } Default argument value of type ‘[Any]’ cannot be converted to type ‘C’

— 14:10

We don’t know what type of C we have and we don’t have a way of instantiating an empty version of it.

— 14:20

What’s it look like to instantiate some other non-empty types? We can now build a non-empty set! NonEmpty<Set<Int>>(1, [2, 3]) // NonEmpty<Set<Int>>

— 14:32

We can even build a non-empty dictionary! We just use a key-value tuple as the head element. NonEmpty<[Int: String]>( (1, "Blob"), [2: "Blob Junior", 3: "Blob Senior"] ) // NonEmpty<Dictionary<Int, String>>

— 15:05

This all compiles, and we now have non-empty versions of sets, arrays, and even dictionaries.

— 15:14

The debugging still doesn’t look great, though, so let’s copy over the CustomStringConvertible conformance from earlier. extension NonEmpty: CustomStringConvertible { var description: String { return "\(head)\(tail)" } }

— 15:24

Now we get a proper print-out of what we expect. NonEmpty<[Int]>(1, [2, 3]) // 1[2, 3] NonEmpty<[Int]>(1, []) // 1[] NonEmpty<Set<Int>>(1, [2, 3]) // 1[2, 3] NonEmpty<[Int: String]>( (1, "Blob"), [2: "Blob Junior", 3: "Blob Senior"] ) // (key: 1, value: "Blob")[2: "Blob Junior", 3: "Blob Senior"]

— 15:41

This is impressive stuff! With just a few lines of code we have non-empty versions of all these different collections, kind of out of nowhere and for free. The only price we’ve had to pay is that we had to abandon the variadic initializer from before.

— 15:59

There’s another collection we use every day but we may not really think of it as a collection too often. For example, we now have access to the concept of a non-empty string! NonEmpty<String>("B", "lob")

— 16:21

The head is the first Character and the tail is the rest of the string. This is super impressive! We can now model our types in ways that better reflect reality, even the idea of strings that can never be empty.

— 16:36

It was kind of a bummer to lose our variadic initializer from earlier, but there’s something we can do. Array conforms to RangeReplaceableCollection , which is a collection protocol that supports replacing a range of elements with the elements of another collection. It also includes functionality that can construct an instance given an array of values, which is exactly we need for our variadic initializer. extension NonEmpty where C: RangeReplaceableCollection { init(_ head: C.Element, _ tail: C.Element...) { self.init(head, C(tail)) } }

— 17:32

Now we can construct a value. NonEmpty<[Int]>(1, 2, 3) // 1[2, 3] So now we’ve even recovered access to that variadic initializers for any collection that is range-replaceable. There are still plenty of collections that aren’t range-replaceable, but at least we got something. Collection conformance

— 18:05

We now have a really nice interface for initialization, but we still can’t treat our NonEmpty type as a collection itself. So let’s conform it to collection.

— 18:15

Let’s start by pasting in our earlier code and modifying it. extension NonEmpty: Collection { var startIndex: Int { return 0 } var endIndex: Int { return self.tail.endIndex + 1 } subscript(position: Int) -> A { return position == 0 ? self.head : self.tail[position - 1] } func index(after i: Int) -> Int { return i + 1 } } Binary operator ‘+’ cannot be applied to operands of type ‘C.Index’ and ‘Int’ Use of undeclared type ‘A’

— 18:23

We get a coupla errors right off the bat. First, A needs to be replaced with C.Element , and then we’re down to dealing with the fact that the Collection protocol doesn’t guarantee that its Index associated type is an Int . And non- Int -based indices are fairly common, like sets, dictionaries, and strings.

— 18:56

We need to create a custom Index type. We can model it using an enum. extension NonEmpty: Collection { enum Index { case head case tail(C.Index) } } Our Index enum has two cases, head denotes an index pointing to the head element, while tail merely wraps the tail collection’s Index .

— 19:18

A Collection ‘s index needs to conform to Comparable , so let’s add a conformance. We can use a switch statement to guide us through the possible cases. extension NonEmpty: Collection { enum Index: Comparable { case head case tail(C.Index) static func < (lhs: Index, rhs: Index) -> Bool { switch (lhs, rhs) { case (.head, .tail): return true case (.tail, .head): return false case (.head, .head): return false case let (.tail(l), .tail(r)): return l < r } } } }

— 20:18

Now we just need to use this custom Index in our conformance. var startIndex: Index { return .head } var endIndex: Index { return .tail(self.tail.endIndex) } subscript(position: Index) -> C.Element { switch position { case .head: return self.head case let .tail(index): return self.tail[index] } } func index(after i: Index) -> Index { switch i { case .head: return .tail(self.tail.startIndex) case let .tail(index): return .tail(self.tail.index(after: index)) } }

— 21:33

The startIndex and endIndex were easy enough: we return .head and wrap up our tail’s endIndex accordingly. The subscript and index(after:) methods took a bit more work, but switch statements guided us along and the code mostly wrote itself!

— 21:45

With that, we now have access to all of those standard library goodies. let ys = NonEmpty<[Int]>(1, 2, 3) ys.forEach { print($0) } // 1 // 2 // 3 ys.count // 3 ys.first // 1

— 22:15

That last result, unfortunately, is wrapped in an optional, like last time. Easy peasy! We can solve it the same way as we did last time. extension NonEmpty { var first: C.Element { return self.head } }

— 22:38

This gives us immediate access to our element again. No need to deal with optionals. ys.first + 1 // 2 Conditional conformance

— 22:45

What about last ? It’s a bit trickier this time because it only exists on BidirectionalCollection , and our NonEmpty type only constrains its generic to Collection .

— 22:55

Swift has a pretty new feature that helps us solve this problem: conditional conformance! We can write a protocol extension that conditionally conforms NonEmpty to be a BidirectionalCollection wherever the underlying collection is also bidirectional. extension NonEmpty: BidirectionalCollection where C: BidirectionalCollection { func index(before i: Index) -> Index { switch i { case .head: return .tail(self.tail.index(before: self.tail.startIndex)) case let .tail(index): return index == self.tail.startIndex ? .head : .tail(self.tail.index(before: index)) } } }

— 24:30

Now we have access to last ! But it’s optional, so let’s add another extension. extension NonEmpty where C: BidirectionalCollection { var last: C.Element { return self.tail.last ?? self.head } }

— 24:56

And now we have immediate access to last . ys.last + 1 // 4 Sugar, constrained

— 25:02

There’s something we typically do with collections, which is to use subscripts to access an element at a specific index. What’s that look like?

— 25:14

We could try to subscript into a non-empty collection using an Int . ys[0] But we get an error. Cannot subscript a value of type ‘NonEmpty<[Int]>’ with an index of type ‘Int’ This makes sense, because NonEmpty uses its own index type.

— 25:29

So, to access that first element, what we really want to do here is to use the head case of that Index enum. ys[.head] // 1

— 25:36

And if we want to reach deeper into our collection, we can use the tail case, starting with 0 . ys[.tail(0)] // 2 ys[.tail(1)] // 3

— 25:49

This isn’t so bad! It’s nice that it’s super explicit that we’re grabbing the “head” element or an element out of the “tail”, and when we see this syntax we know right away that we’re dealing with a non-empty collection. We can still make the common Int index case a little nicer using a constrained protocol extension. extension NonEmpty where C.Index == Int { subscript(position: Int) -> C.Element { return self[position == 0 ? .head : .tail(position - 1)] } } Correction This implementation is not entirely correct because it does not account for collections whose startIndex is not zero, like array slices. The correct implementation should adjust the .tail index by: .tail(self.tail.startIndex + position - 1) . Thanks to Ole Begemann for pointing this out in a GitHub issue .

— 26:40

Now we’re free to access elements using an Int . ys[0] // 1 ys[1] // 2 ys[2] // 3

— 26:49

Seeing this syntax makes it all too tempting to modify a value at a given index. var zs = NonEmpty<[Int]>(1, 2, 3) zs[0] = 42 Cannot assign through subscript: subscript is get-only

— 21:02

This doesn’t work because we’ve only conformed NonEmpty to be a Collection (and conditionally as a BidirectionalCollection . Setting via subscript lives on another protocol, MutableCollection . So let’s add another conditional conformance and let Xcode stub things out for us. extension NonEmpty: MutableCollection where C: MutableCollection { subscript(position: Index) -> C.Element { get { } set(newValue) { } } }

— 27:37

The get is a simple copy-paste from earlier, while set is also similar and only requires a few changes. extension NonEmpty: MutableCollection where C: MutableCollection { subscript(position: Index) -> C.Element { get { switch position { case .head: return self.head case let .tail(index): return self.tail[index] } } set(newValue) { switch position { case .head: self.head = newValue case let .tail(index): self.tail[index] = newValue } } } }

— 27:58

Now we should be able to mutate our non-empty array. zs[0] = 42 Cannot assign through subscript: subscript is get-only Whoops! We need to remember to use our custom index type, so what we really want is this: zs[.head] = 42 zs // 42[2, 3]

— 28:15

Let’s add another Int subscript helper for mutable collections to make this a bit nicer. extension NonEmpty where C: MutableCollection, C.Index == Int { subscript(position: Int) -> C.Element { get { return self[position == 0 ? .head : .tail(position - 1)] } set(newValue) { self[position == 0 ? .head : .tail(position - 1)] = newValue } } }

— 28:59

And now we can update an element using simple integers. zs[0] = 42 zs[1] = 1000 zs[2] = 19 zs // 42[1000, 19]

— 29:13

And we just keep improving the ergonomics of this time! There are a bunch of other protocols we probably want to conform this type to, like Equatable and Hashable and Comparable and so on, but we’ll leave those as exercises for the viewer. A setback

— 29:45

There’s a problem with our implementation. Non-empty sets don’t quite work as we expect. The Set type has an expectation that all of its values are unique, but we haven’t baked this concept into our type.

— 30:05

When you create a Set , you may notice that it conveniently removes duplicate elements. let set = Set([1, 1, 2, 3]) // {3, 1, 2} set.count // 3

— 30:22

However, if we try to do the same thing with our non-empty set: let nonEmptySet = NonEmpty(1, Set([1, 2, 3])) // 1[1, 3, 2] nonEmptySet.count // 4 If a duplicate head element appears in the tail , the non-empty set misses this and we have to deal with a duplicate.

— 30:42

We can solve this, though, using constrained extension when the underlying collection is also a SetAlgebra , which is a protocol that models much of the interface of sets: extension NonEmpty where C: SetAlgebra { init(_ head: C.Element, _ tail: C) { var tail = tail tail.remove(head) self.head = head self.tail = tail } } We just need to ensure that tail does not include head , so we make a quick, local copy and remove any potential head elements. Now, when we attempt to create a non-empty set with a duplicate element, it works as expected. let nonEmptySet = NonEmpty(1, Set([1, 2, 3])) // 1[2, 3] nonEmptySet.count // 3 We’ve now prevented those duplicate elements from entering our non-empty sets.

— 31:41

SetAlgebra also allows initialization from an array, much like RangeReplaceableCollection , but one does not inherit from the other. So, if we want to have a variadic initializer, we’ll have to write another one ourselves: extension NonEmpty where C: SetAlgebra { init(_ head: C.Element, _ tail: C.Element...) { var tail = C(tail) tail.remove(head) self.head = head self.tail = tail } }

— 32:23

Now we’ve expanded our variadic ergonomics to non-empty, set-like collections! NonEmpty<Set<Int>>(1, 1, 2, 3) // 1[2, 3]

— 32:27

More and more we’re improving the ergonomics of our non-empty type, but we’re also ensuring our expectations for its underlying type holds true.

— 32:38

There are other types with specific semantics that we should worry about. Dictionaries, for example, have a similar requirement, where keys should not be duplicated. We should write a similar initializer in this case, but we’ll leave it as an exercise for the viewer. Type alias for inference

— 33:00

There’s another small thing we can introduce for ergonomics.

— 33:08

Because NonEmpty wraps a container type, instantiating sets and arrays require extra typing where Swift can normally infer things for us. For example: Set([1, 2, 3]) Swift was able to infer the type Set<Int> without an explicit set of generic brackets.

— 33:33

The problem with NonEmpty is that the collection type quickly becomes ambiguous. NonEmpty(1, 1, 2, 3) This just doesn’t work. It doesn’t know if it’s dealing with arrays, or sets, or something else entirely.

— 33:49

We can give the type checker a little help for common cases using type aliases! typealias NonEmptySet<A> = NonEmpty<Set<A>> where A: Hashable

— 34:11

Now we let Swift do its type inference thing. NonEmptySet(1, 1, 2, 3) // 1[2, 3] This read much more nicely with much less noise.

— 34:26

Let’s do the same for Array ! typealias _NonEmptyArray<A> = NonEmpty<[A]> We already defined NonEmptyArray earlier, so let’s prefix it with an underscore for now just to get things running.

— 34:44

And using this type alias, we get access to better inference. _NonEmptyArray(1, 1, 2, 3) // 1[1, 2, 3]

— 34:55

It’s nice that we can just keep chipping away at this API, and we could keep going! What’s the point?

— 35:06

Now, it’s amazing that we’ve created this non-empty type that wraps any collection and provides, instantly, a whole new type that represents the non-empty version of that collection, provably at compile-time, and with very little code! But, like every week, let’s ask “what’s the point?” so that we can explore just how this type can be used to improve our everyday code.

— 35:51

Many times we create or work with APIs that deal with arrays even though we know the empty state is supposed to be impossible.

— 36:15

Let’s take the example of adding a groupBy method to Sequence : extension Sequence { func groupBy<A>(_ f: (Element) -> A) -> [A: [Element]] { var result: [A: [Element]] = [:] for element in self { let key = f(element) if result[key] == nil { result[key] = [element] } else { result[key]?.append(element) } } return result } }

— 37:23

How can we use this? Array(1...10) .groupBy { $0 % 3 } // [0: [3, 6, 9], 1: [1, 4, 7, 10], 2: [2, 5, 8]] "Mississippi" .groupBy { $0 } // ["M": ["M"], "i": ["i", "i", "i", "i"], "s": ["s", "s", "s", "s"], "p": ["p", "p"]]

— 38:02

Notice that the arrays inside this dictionary are all non-empty, and looking at the implementation of groupBy we see it’s completely impossible for the array to be empty because we only create an array if we have a value to start with.

— 38:28

Let’s try changing the return type to use NonEmpty<[Element]> and see what we have to fix. func groupBy<A: Hashable>(_ f: (Element) -> A) -> [A: NonEmpty<[Element]>] { var result: [A: NonEmpty<[Element]>] = [:] for element in self { let key = f(element) if result[key] == nil { result[key] = NonEmpty(element) } else { result[key]?.append(element) } } return result }

— 38:57

Most of this was fairly straightforward! But we have one issue. Value of type ‘NonEmpty<[Element]>’ has no member ‘append’ This is because append comes from RangeReplaceableCollection , and even though we’ve encountered this protocol a number of times in this episode, we still haven’t conformed NonEmpty to it, and that’s because RangeReplaceableCollection holds a lot of destructive methods in it, including the ability to initialize an empty collection. NonEmpty is fundamentally incompatible.

— 39:24

That doesn’t mean we can’t forward on the non -destructive methods! In this case: extension NonEmpty where C: RangeReplaceableCollection { mutating func append(_ newElement: C.Element) { self.tail.append(newElement } }

— 39:49

Now everything compiles and groupBy can return a dictionary of non-empty arrays! Array(1...10) .groupBy { $0 % 3 } .debugDescription // [0: 3[6, 9], 1: 1[4, 7, 10], 2: 2[5, 8]] All the code paths we would have to worry about with empty arrays go away!

— 40:27

These things are hiding everywhere in plain sight! We just don’t see them and how they could benefit our code.

— 40:37

Recently, Swift got a revamped Random API , and the discussion involved a randomElement method, which vends a random element from a collection. For example: [1, 2, 3].randomElement() // Int? This method returns an optional Int , which makes sense. Just like the first and last properties return optionals, it too must account for empty collections. Unfortunately, we get the same behavior using NonEmpty . NonEmpty<[Int]>(1, 2, 3).randomElement() // Int? This doesn’t make a whole lot of sense, of course, because we know that our non-empty array contains at least one value.

— 41:32

Let’s solve this with another extension. extension NonEmpty { func safeRandomElement() -> C.Element { return self.randomElement() ?? self.head } } Rather than overload randomElement() , we’ve written a safeRandomElement() that can delegate to the underlying implementation.

— 42:06

Now we have immediate, safe access to a random element. NonEmpty<[Int]>(1, 2, 3).randomElement() + 1 // Int

— 42:23

It’s common to want to return a random element from a set of known elements at compile time, and it’s nice that NonEmpty can simplify our code here, helping us avoid having to deal with optionality and that empty case.

— 42:54

Let’s take another, perhaps more esoteric, example. GraphQL is a query language for APIs that’s getting more and more popular. We might write a client that generates a query from a list of fields for a GraphQL type, and we may default to using a plain ole array or set since that’s what’s available to us in the standard library.

— 43:22

A raw GraphQL query is a string that looks something like this: // { email name } Curly braces wrap the fields of a type that you want returned, in this case we want just the email and the name of a user.

— 43:39

A problem arises with an empty query. // {} This is invalid! The server will send back an error if the client makes this kind of query, and so the client is going to have to deal with these kinds of errors. Let’s say we modeled a GraphQL type’s fields using an enum enum UserField: String { case id case name case email }

— 44:05

How might we use this type to build up a query? func query(_ fields: Set<UserField>) -> String { return (["{\n"] + fields.map { " \($0.rawValue)\n" } + ["}\n"]) .joined() }

— 44:23

Calling this function is simple enough. print(query([.name, .email])) // { // name // email // } But now we have a potential runtime error. We reached for Set because it was at-hand, but now our client is free to generate invalid queries at compile time. print(query([])) // { // }

— 44:45

As we saw, this is invalid, so let’s fix that! All we have to do is change Set to NonEmptySet ! func query(_ fields: NonEmptySet<UserField>) -> String { return (["{\n"] + fields.map { " \($0.rawValue)\n" } + ["}\n"]) .joined() } And update our call site. print(query(.init(.email, .name)))

— 45:13

And just like that we’ve eliminated a runtime error! We’re no longer able to construct invalid queries at compile-time using this interface and it didn’t take a lot of work!

— 45:23

We were able to write a function that takes a Set , change it to take a NonEmptySet , and none of the function body had to change! The only work we had to do was at the call site.

— 45:33

Those were three fantastic reasons to use NonEmpty , but let’s do one more to really hit it home.

— 45:43

On this series we’ve covered the Result type a few times. enum Result<Value, Error> { case success(Value) case failure(Error) }

— 45:56

There’s a specialization of the Result type that’s common enough to have appeared in many libraries over many languages and has its own name, Validated . enum Validated<Value, Error> { case valid(Value) case invalid([Error]) } It’s very similar to Result , but its invalid case returns an array of all the things that went wrong during validation.

— 46:29

It’s easy enough to produce some Validated values, for instance, a valid password: let validatedPassword = Validated<String, String>.valid("blobisawesome")

— 46:45

What about an invalid password? let validatedPassword = Validated<String, String> .invalid(["Too short", "Didn't contain any numbers"])

— 47:07

What does it mean, though, to provide an empty array to the invalid case? let validatedPassword = Validated<String, String>.invalid([]) We have an invalid value but no errors to tell us why it’s invalid. Having no errors may make us think that it is valid, but we have no value to work with. What we probably wanted to use here was NonEmpty . enum Validated<Value, Error> { case valid(Value) case invalid(NonEmpty<[Error]>) }

— 47:42

And now our empty case isn’t possible, and we just need to provide our non-empty case with the appropriate API. let validatedPassword = Validated<String, String> .invalid(.init("Too short", "Didn't contain any numbers"))

— 47:50

With this one change we’ve improved this Validated type to properly represent what we know it should represent. It’s completely nonsensical to have an invalid state with no errors, so now we’re forcing anyone using Validated to provide at least one error.

— 48:10

Non-empty collections are everywhere and easy to miss. We encourage our viewers to look at their own code bases and find collections that should never be empty and, better yet, model them this way!

— 48:34

This all started from taking an abstract foundation of using algebraic data types to understand generics and recursion using strange formulas of infinite sums! And we used that to guide us to this useful and usable non-empty type that can improve our everyday code.

— 48:56

And while we only briefly introduced Validated , it’ll be making more appearances in future episodes. There are some very interesting concepts that come along with it! References NonEmpty Brandon Williams & Stephen Celis • Jul 25, 2018 NonEmpty is one of our open source projects for expressing a type safe, compiler proven non-empty collection of values. https://github.com/pointfreeco/swift-nonempty Validated Brandon Williams & Stephen Celis • Aug 17, 2018 Validated is one of our open source projects that provides a Result -like type, which supports a zip operation. This means you can combine multiple validated values into a single one and accumulate all of their errors. https://github.com/pointfreeco/swift-validated Downloads Sample code 0020-nonempty 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 .