How to implement `Optional.zip` using variadic generics?

Using Swift
1

One helper function I've found pretty useful is Optional.zip. Up until this point, I've had to have an overload for every arity, as such:

func zip<A, B>(_ a: A?, _ b: B?) -> (A, B)? {
  guard let a, let b else { return nil }
  return (a, b)
}

func zip<A, B, C>(_ a: A?, _ b: B?, _ c: C?) -> (A, B, C)? {
  guard let a, let b, let c else { return nil }
  return (a, b, c)
}

//...etc...

This seems like a perfect candidate for variadic generics. However, I'm having trouble finding a working implementation. I think I've got the right function signature...

func zip<each T>(_ val: repeat (each T)?) -> (repeat each T)? {
  return nil // TODO
}

...but I can't seem to get something that compiles that unwraps each element of the parameter pack. I wonder if anyone more familiar with this new feature might have ideas?

Thanks!

4 Likes
2

Welp, I got something working, but it's a little bit hacky. Would love to know if there's a more elegant way to do this currently, or if it's a limitation of what we've got so far. (It seems like there may not be a way to iterate over elements of the pack and "short-circuit" partway through, except for throwing an error?)

struct _UnwrapError: Error {}

func zip<each T>(_ pack: repeat (each T)?) -> (repeat each T)? {
  do {
    return (repeat try (each pack).orThrow())
  } catch {
    return nil
  }
}

extension Optional {
  func orThrow() throws -> Wrapped {
    guard let value = self else { throw _UnwrapError() }
    return value
  }
}
3 Likes
3

I’ve contrived it into working but I think really we’re just still very early in the evolution of pack values. In C++ you’d peel off a value at a time and recurse, but I suspect Swift will need something else because there’s no template instantiating. (Hopefully it’ll come out nicer too!)

(EDIT: ha, you beat me, but we had the same basic idea.)

2 Likes
4

For now your two solutions are as good as it gets, except that you might consider making the helper function into a local function.

We don't allow closure expressions to appear in the repeat pattern yet (this is doable but requires implementing a transform to convert the pack element reference into a capture, which we haven't got around to yet); this would simplify the code a little bit further.

The use of throw/catch feels awkward though, and I'm not sure what the best way to express a short-circuiting fold over a pack would be. There is still plenty of unexplored language design space with parameter packs!

3 Likes
5

It seems to me that your A and B should be required arguments, no? As it is right now, you can do

zip()

Have you come up with an example working required arguments into the mix? I'm not going to bother trying for now, given what you've demonstrated as the current state of the feature. :dotted_line_face:

(Also, I didn't find this thread because I didn't think what we're doing is zipping. Is it zipping? I thought zipping was combining a number of elements together in tuples.)

6

A required argument is easy, you just define a non-pack type parameter:

func foo<T, each U>(_: T, _: repeat each U)

Think of an optional as a sequence of zero or one elements.

1 Like
7

There are many types other than sequences/collections that can have zip defined. See PointFree's Episode #23: The Many Faces of Zip: Part 1. (It's paywalled, but they are very much worth subscribing to!)

9

It’s more like if zip() took the length of the shortest sequence. Since nil is “empty” and .some has “length 1”, zip(nil, .some(1)) is like zip(, [1]).

10

zip is a function that inverts the relationship between tuples and some generic container:

  • Sequence.zip turns two or more sequences into a sequence of tuples.
  • Optional.zip turns two or more optionals into an optional tuple.
  • Promise.zip turns two or more promises into a Promise<(A, B)>
  • Foo.zip turns the tuple (Foo<A>, Foo<B>) into Foo<(A, B)>

You can think of it the same way map changes the generic type of a container, and works with both Sequence, Optional, Result, Publisher, and more. It's not just for converting every element of some sequence into another sequence, but to unwrap-transform-rewrap any kind of container, not just sequences.

In the same way, .zip isn't about sequences, but about generic containers, and turning a bunch of them into a single one.

3 Likes
12

The 1-tuple is a generic container, and its zip is a proper zip, but it's not a particularly useful one. It's essentially equivalent, in other contexts, to the "identity functor", that is, something like this

struct Identity<T> {
  var value: T
}

thus, a "container" that just "contains" something, without managing any kind of effect.

But suppose that we defined the following type:

enum Container<T> {
  case foo
  case bar
  case baz(T)
}

can we implement a zip for it? I'm sure it wouldn't be hard to come up with some implementation, but how do we know it's correct, and behaves as expected, for example when composed with other transformations, or when using zip multiple times on several groups of values?

To understand if a generic container can have a "proper" zip, we need to define some laws that, if followed, would guarantee that it works as expected for that generic container. In other words, if the generic container behaves in a certain way, and we can prove it, we can also prove that the zip works as intended.

A possible approach is to define zip in terms of something else that already has a laws defined. In particular, zip can be defined for an applicative functor (or simply "applicative").

To illustrate this, let's consider Optional. An applicative is also a functor, that must declare a map function (and Optional does). To make Optional also an applicative we need to define 2 functions for it:

  • pure, which is a function that, given a value, wraps it into the container;
  • ap, which is a function that "merges" a container that contains a function and a container that contains a value into a container that contains the value obtained when applying the function to the initial value.

The applicative definition of Optional is as follows:

extension Optional {
  static func pure(_ value: Wrapped) -> Self {
    .init(value)
  }

  func ap<A, B>(_ other: A?) -> B? where Wrapped == (A) -> B {
    switch (self, other) {
    case (let transform?, let value?):
      return transform(value)

    default:
      return nil
    }
  }
}

Given the above, zip can be defined like this:

func zip<A, B>(_ a: A?, _ b: B?) -> (A, B)? {
  Optional.pure { a in { b in (a, b) } }.ap(a).ap(b)
}

If we can prove that Optional is a "proper" applicative, we can also prove that zip for Optional works as intended (in fact, we can define zip for any applicative exactly in the same way, given that the implementation only uses pure and ap).

We essentially need to show that the "applicative laws" work for Optional. To do that, I'll use some utilities, as follows:

infix operator ==!

func ==! <A>(lhs: A, rhs: A) where A: Equatable {
  assert(lhs == rhs)
}

let x = 42

let f: (Int) -> Int = { $0 * 2 }
let g: (Int) -> Int = { $0 + 2 }

let a = Optional { $0 - 1 }
let b = Optional { $0 - 10 }
let c = Optional(42)

First, we need to prove that Optional is a proper functor, which means that it must follow the functor laws:

// Functor laws
// for any c, f, g

// identity

c.map { $0 } ==! c

// composition

c.map { f(g($0)) } ==! ({ $0.map(f) })(({ $0.map(g) })(c))

then we need to show that it follows the applicative laws:

// Applicative laws
// for any c, x, f, a, b

typealias SUT<T> = Optional<T>

// identity

SUT.pure { $0 }.ap(c) ==! c

// homomorphism

SUT.pure(f).ap(SUT.pure(x)) ==! SUT.pure(f(x))

// interchange

a.ap(SUT.pure(x)) ==! SUT.pure { $0(x) }.ap(a)

// composition

SUT.pure { a in { b in { b(a($0)) } } }.ap(a).ap(b).ap(c) ==! a.ap(b.ap(c))

:warning: to actually "prove" these we would need property-based testing, in order to actually express the concept of for any x, f, g, a, b, c, but a bunch of sufficiently exhaustive cases should be fine.

Going back to original example:

enum Container<T> {
  case foo
  case bar
  case baz(T)
}

If we provide an applicative implementation for it, we could easily define zip like this:

func zip<A, B>(_ a: Container <A>, _ b: Container <B>) -> Container<(A, B)> {
  Container.pure { a in { b in (a, b) } }.ap(a).ap(b)
}

Now, pure is obvious:

extension Container {
  static func pure(_ value: T) -> Self {
    .baz(value)
  }
}

But what about ap? It's not actually obvious how to do it properly, but using the laws we could prove that a certain implementation would guarantee a proper behavior of the zip.

3 Likes
13

If Swift could support higher kinder types, could we have protocols for Functor, Applicative, Monad etc, and define all map, zip, flatMap, reduce, scan, and a bunch of other functions as protocol extensions on those protocols, and remove a whole lot of duplicated conformances?

It would be nice to have e.g flatMap fall out of every mappable type by default.

14

We could: the implementation of zip via the functions of the applicative is an example. But should we? Languages without an effect system, like Haskell, can rely on monads to represent effects, but this leads to extremely complex code related to the composition of such effects (and the approaches tend to split communities in large branches that support one specific approach and use specific libraries and tooling).

Swift has moved towards a different approach, that is, some effects are managed and embedded in the language, and as such the embedded system constitutes the preferable choice for expressing them, that is, essentially, optionality, error handling and asynchronous code. The talks about about reasync and rethrowing protocols is related to this approach. After having dealt with monads for years (which was very useful to get a better understanding of the tradeoffs) I realized that I find the embedded approach better.

The main issue is lack of generality: only some specific effects are embedded in the language, in a non-extensible way: you can do all sorts of effects in Swift code, of course, like mutating a global variable in a function, but those are side effects, and are not managed. Some experimental languages like Eff and Unison make use of algebraic effects (that Unison calls Abilities) to provide a general and extensible managed effect handling system (I should also include Roc, but it seems to be in a stage that's too early to get a sense of how the effects are actually managed). I think I'd rather see Swift move towards this idea than implementing higher-kinded types for the sole reason of being able to represent effects with constructions lifted from category theory.

It's not possible to get flatMap from map in the general case, but it is possible to do the opposite, that is, given flatMap (and a "wrapper" constructor, like pure) implement map.

1 Like