A new Swift video series exploring functional programming and more.
#20 • Monday Jun 25, 2018 • Subscriber-only

NonEmpty

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.

This episode builds on concepts introduced previously:

#20 • Monday Jun 25, 2018 • Subscriber-only

NonEmpty

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.

This episode builds on concepts introduced previously:


Subscribe to Point‑Free

This episode is for subscribers only. To access it, and all past and future episodes, become a subscriber today!

See subscription optionsorLog in

Sign up for our weekly newsletter to be notified of new episodes, and unlock access to any subscriber-only episode of your choosing!

Sign up for free episode

Introduction

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!

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!

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

Subscribe to Point-Free

👋 Hey there! Does this episode sound interesting? Well, then you may want to subscribe so that you get access to this episodes and more!


Exercises

  1. Why shouldn’t NonEmpty conditionally conform to SetAlgebra when its underlying collection type also conforms to SetAlgebra?

  2. Define the following method:

    extension NonEmpty where C: SetAlgebra {
      func contains(_ member: C.Element) -> Bool
    }
    

    Note that SetAlgebra does not require that elements are equatable, so utilize other methods on SetAlgebra to make this check.

  3. Define the following method:

    extension NonEmpty where C: SetAlgebra {
      func union(_ other: NonEmpty) -> NonEmpty
    }
    

    Ensure that no duplicate head element enters the resulting non-empty set. The following property should hold true:

    NonEmptySet(1, 2, 3).union(NonEmptySet(3, 2, 1)).count == 3
    
  4. Define a helper subscript on NonEmpty to access a non-empty dictionary’s element using the dictionary key. You can constrain the subscript over Key and Value generics to make this work.

  5. Our current implementation of NonEmpty allows for non-empty dictionaries to contain the head key twice! Write a constrained extension on NonEmpty to prevent this from happening. You will need create a DictionaryProtocol for Dictionary in order to make this work because Swift does not currently support generic extentions.

    // Doesn't work
    extension <Key, Value> NonEmpty where Element == [Key: Value] {}
    
    // Works
    protocol DictionaryProtocol {
      /* Expose necessary associated types and interface */
    }
    extension Dictionary: DictionaryProtocol {}
    extension NonEmpty where Element: DictionaryProtocol {}
    

    Look to the standard library APIs for inspiration on how to handle duplicate keys, like the init(uniqueKeysAndValues:) and init(_:uniquingKeysWith:) initializers.

  6. Define updateValue(_:forKey:) on non-empty dictionaries.

  7. Define merge and merging on non-empty dictionaries.

  8. Swift Sequence contains two joined methods that flattens a nested sequence given an optional separator sequence. For example:

    ["Get ready", "get set", "go!"].joined("...")
    // "Get ready...get set...go!"
    
    [[1], [1, 2], [1, 2, 3]].joined([0, 0])
    // [1, 0, 0, 1, 2, 0, 0, 1, 2, 3]
    

    A non-empty collection of non-empty collections, when joined, should also be non-empty. Write a joined function that does so. How must the collection be constrained?

  9. Swift Sequence also contains two split methods that split a Sequence into [Sequence.SubSequence]. They contain a parameter, omittingEmptySubsequences that prevents non-empty sub-sequences from being included in the resulting array.

    Splitting a non-empty collection, while omitting empty subsequences, should return a non-empty collection of non-empty collections. Define this version of split on NonEmpty.

  10. What are some challenges with conditionally-conforming NonEmpty to Equatable? Consider the following check: NonEmptySet(1, 2, 3) == NonEmptySet(3, 2, 1). How can these challenges be overcome?

  11. Define zip on non-empty arrays:

    func zip<A, B>(_ a: NonEmpty<[A]>, _ b: NonEmpty<[B]>) -> NonEmpty<[(A, B)]> {}
    

References

  • NonEmpty

    Brandon Williams & Stephen Celis • Wednesday Jul 25, 2018

    NonEmpty is one of our open source projects for expressing a type safe, compiler proven non-empty collection of values.

  • Validated

    Brandon Williams & Stephen Celis • Friday 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.

Chapters
Introduction
00:05
Recap
01:07
NonEmptyArray
04:17
NonEmptyCollection
11:53
Collection conformance
18:05
Conditional conformance
22:45
A setback
29:45
Type alias for inference
33:00
What’s the point?
35:06