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))
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.
