A blog exploring functional programming and Swift.

Thursday Aug 16, 2018

Last week we concluded our 3-part introductory series to the `zip`

function. In the
third episode we finally answered the question: “what’s
the point?” It ultimately led us to the realization that with `zip`

we could unify many wildly different
ways of creating instances of types under the umbrella of one single concept. And that allowed us to
write code that worked across arrays, optionals, results, validations, lazy values and even async
values in an identical manner.

At the end of the episode we provided some exercises to help viewers dive a little deeper into these ideas, and this week we solve most of those problems!

In this series of episodes on

`zip`

we have described zipping types as a kind of way to swap the order of nested containers when one of those containers is a tuple, e.g. we can transform a tuple of arrays to an array of tuples`([A], [B]) -> [(A, B)]`

. There’s a more general concept that aims to flip containers of any type. Implement the following to the best of your ability, and describe in words what they represent:

`sequence: ([A?]) -> [A]?`

One attempt at implementation this function may to simply discard all `nil`

values from the array, much like
what `compactMap`

does. However, why then would we return an optional array `[A]?`

? Seems like that’s not
quite the semantics that this function signature is implying.

Maybe instead what we want to do is return an array of non-optional values in the case that all the values
are present, and otherwise return `nil`

. This is a nice way to force that every optional value in an array
is present:

```
func sequence<A>(_ xs: [A?]) -> [A]? {
var result: [A] = []
for x in xs {
guard let x = x else { return nil }
result.append(x)
}
return result
}
```

`sequence: ([Result<A, E>]) -> Result<[A], E>`

Here we are trying to transform an array of results into a result of an array. One way would be to just discard all the failures from the array, and bundle all the successful values into its own array. However, much like the previous exercise, why would we return a result value if we have just take all the successful values? The semantics are all wrong again.

Instead, it might be more true to this function’s signature to require *all* the result values in the array
to be successful, in which case bundle them into an array, and otherwise return an array, say the first
error. This is straightforward to implement:

```
func sequence<A, E>(_ results: [Result<A, E>]) -> Result<[A], E> {
var successValues: [A] = []
for result in results {
switch result {
case let .success(value):
successValues.append(value)
case let .failure(error):
return .failure(error)
}
}
return .success(successValues)
}
```

`sequence: ([Validated<A, E>]) -> Validated<[A], E>`

This one seems very similar to the previous exercise, but we can now take advantage of some key characteristics of `Validated`

. Instead of bailing on the first error we come across, we can accumulate *all* of the errors that we encounter.

This is a bit tricky! We use `NonEmpty`

to guarantee that at least one error exists in any invalid state. It might seem tough to accumulate a `NonEmpty`

array from nothing, but we can use `Optional`

as our nothing and safely wrap and unwrap along the way.

```
func sequence<A, E>(_ results: [Validated<A, E>]) -> Validated<[A], E> {
var validValues: [A] = []
var invalidErrors: NonEmptyArray<E>?
for result in results {
switch result {
case let .valid(value):
validValues.append(value)
case let .invalid(errors):
if invalidErrors == nil {
invalidErrors = errors
} else {
invalidErrors?.append(contentsOf: errors)
}
}
}
if let invalidErrors = invalidErrors {
return .invalid(invalidErrors)
} else {
return .valid(validValues)
}
}
```

This solution requires a bit of a dance to make work in an imperative style.

We can use `reduce`

and `zip`

and shorten things. If we start with the knowledge that sequencing an empty array of validated results should return a valid, empty array, we can pass `reduce`

this initial value and accumulate either an array of results or a non-empty array of errors by zipping each current accumulation with an array of the next value.

```
func sequence<A, E>(_ results: [Validated<A, E>]) -> Validated<[A], E> {
return results.reduce(.valid([])) { vs, v in
zip2(vs, v.map { [$0] }).map { $0 + $1 }
}
}
```

`sequence: ([Parallel<A>]) -> Parallel<[A]>`

This is a fun one. Here we are trying to transform an array of parallel values into a parallel value of
an array. We could try running all of the parallel values in the array concurrently, and then once they
are all done collect the values into a single array. One way to accomplish this is to allocate an array
the size of the array of parallel values, but filled with `nil`

s. Then run all the parallels concurrently,
and as they finish stick their values into the allocated array. And when the last one finishes, invoke
the callback:

```
func sequence<A>(_ values: [Parallel<A>]) -> Parallel<[A]> {
return Parallel<[A]> { callback in
var results = [A?](repeating: nil, count: Int(values.count))
var completed = 0
zip(values.indices, values).forEach { idx, value in
value.run { a in
results[idx] = a
completed++
if completed == values.count {
callback(results.compactMap { $0 })
}
}
}
}
}
```

Now this implementation has a lot of threading problems, so its not yet production ready. However, a fun bonus exercise might be to find ways to make this thread safe.

`sequence: (Result<A?, E>) -> Result<A, E>?`

Now we are trying to move the optional `?`

from inside the result to outside. All we gotta do is reach into
the `.success`

case, see if it exists, and if it does, promote it to a non-optional. We’ll also allow
errors to pass through:

```
func sequence<A>(_ result: Result<A?, E>) -> Result<A, E>?` {
switch result {
case let .success(value):
return value.map(Result.success)
case let .failure(error):
return .failure(error)
}
}
```

`sequence: (Validated<A?, E>) -> Validated<A, E>?`

This implementation is almost identical to that of `Result`

:

```
func sequence<A>(_ result: Validated<A?, E>) -> Validated<A, E>?`
switch result {
case let .valid(value):
return value.map(Validated.value)
case let .invalid(error):
return .invalid(error)
}
}
```

Note that all of these functions also represent the flipping of containers, e.g. an array of optionals transforms into an optional array, an array of results transforms into a result of an array, or a validated optional transforms into an optional validation, etc.

Do the implementations of these functions have anything in common, or do they seem mostly distinct from each other?

Looking at all the implementations of `sequence`

above, it is very difficult to find any commonality.
Each implementation seems to have used some intimate knowledge of the container types being used. This
is in contrast to what we discovered when zipping two nested zippable containers of the same type. In
that case we found that we could define `zip`

on the nesting in a very natural way, and it was always
the same implementation no matter container type we chose.

And even though there isn’t a single thing in common for *all* of the implementations, there are *some*
things in common for the implementations having a common “outer” container type, such as array. Can
you formalize this relationship?

This is a very powerful idea, and we are only just grasping at it right now. We will have more information on this soon!

There is a function closely related to

`zip`

called`apply`

. It has the following shape:`apply: (F<(A) -> B>, F<A>) -> F<B>`

. Define`apply`

for`Array`

,`Optional`

,`Result`

,`Validated`

,`Func`

and`Parallel`

.

We can define `apply`

in terms of `zip`

:

```
func apply<A, B>(_ lhs: [(A) -> B], _ rhs: [A]) -> [B] {
return zip2(lhs, rhs).map { $0($1) }
}
func apply<A, B>(_ lhs: ((A) -> B)?, _ rhs: A?) -> B? {
return zip2(lhs, rhs).map { $0($1) }
}
func apply<A, B, E>(_ lhs: Result<(A) -> B, E>, _ rhs: Result<A, E>) -> Result<B, E> {
return zip2(lhs, rhs).map { $0($1) }
}
func apply<A, B, R>(_ lhs: Func<R, (A) -> B>, _ rhs: Func<R, A>) -> Func<R, B> {
return zip2(lhs, rhs).map { $0($1) }
}
func apply<A, B>(_ lhs: Parallel<(A) -> B>, _ rhs: Parallel<A>) -> Parallel<B> {
return zip2(lhs, rhs).map { $0($1) }
}
```

Every implementation is exactly the same. The `apply`

function can always be defined in terms of `zip`

and `map`

.

Another closely related function to

`zip`

is called`alt`

, and it has the following shape:`alt: (F<A>, F<A>) -> F<A>`

. Define`alt`

for`Array`

,`Optional`

,`Result`

,`Validated`

and`Parallel`

. Describe what this function semantically means for each of the types.

This function encapsulates how to combine two values of the same type in some context into just a single context of that type. For arrays, a natural way to do this would be simply array concatenation:

```
func alt<A>(_ lhs: [A], _ rhs: [A]) -> [A] {
return lhs + rhs
}
```

For optionals, let’s write down the signature and see what possible implementations there are:

```
func alt<A>(_ lhs: A?, _ rhs: A?) -> A? {
switch (lhs, rhs) {
case let (.none, .none):
fatalError()
case let (.some(lhs), .none):
fatalError()
case let (.none, .some(rhs)):
fatalError()
case let (.some(lhs), .some(rhs)):
fatalError()
}
}
```

We’ve filled in the first step, which is to simply to switch on the two optionals handed to us. In the first
case we have two `.none`

values, and so there’s nothing we could hope to do to return an `A`

value, so we’ll
just return `nil`

. In the next 2 cases we have a `.some`

value of type `A`

, and so let’s just return it.
The last case is the trickiest, in which we have two `.some`

values of type `A`

. We don’t know anything
about `A`

so we can’t combine those values in anyway reasonable way. Therefore we must just decide to
return one of them, so we’ll return the first one:
}

```
func alt<A>(_ lhs: A?, _ rhs: A?) -> A? {
switch (lhs, rhs) {
case let (.none, .none):
return nil
case let (.some(lhs), .none):
return lhs
case let (.none, .some(rhs)):
return rhs
case let (.some(lhs), .some(rhs)):
return lhs
}
}
```

This function should seem quite familiar to you. It’s precisely `??`

, Swift’s `nil`

coalescing operator.
This provides important semantic meaning to the `alt`

function, because in the case of optionals it means
“return the first non-`nil`

value, otherwise return `nil`

.” This is what allows you to chain many of these
functions together to express the idea of getting the first non-`nil`

value from a bunch of optionals.

Next we will consider `Result`

. How can we combine two `Result<A, E>`

‘s into just a single one? Let’s take
some inspiration from our comments on `Optional`

above, and think about this semantically. We will define
`alt`

on `Result`

to be the operation of returning the first `.success`

value if it exists, and otherwise
return the *last* `.failure`

. Here’s the implementation:

```
func alt<A, B, E>(_ a: Result<A, E>, _ b: Result<B, E>) -> Result<(A, B), E> {
switch (a, b) {
case let (.success(a), _):
return .success(a)
case let (.failure, .success(b)):
return .success(b)
case let (.failure, .failure(e)):
return .failure(e)
}
}
```

The implementation for `alt`

on `Validated`

is very similar.

Finally, we have the `Parallel`

type. How can we combine two `Parallel<A>`

‘s into just a single one? If
we were to run both parallel values at the same time, and then at a later time procure two values of type
`A`

from them, there still wouldn’t be anyway to combine both values into one since we know *nothing* about
the type `A`

. Seems like no matter what we have to discard information. Similar to what we’ve done with
`Result`

, maybe we should only take the first one that finishes? We can implement that like so:

```
func alt<A>(_ lhs: Parallel<A>, _ rhs: Parallel<A>) -> Parallel<A> {
return .init { f in
var finished = false
let callback: (A) -> () = {
guard !finished else { return }
finished = true
f($0)
}
lhs.run(callback)
rhs.run(callback)
}
}
```

Semantically this means that we are *racing* both parallels, and just picking the one that is fastest.

And that’s the solutions to the third part of our 3 part
introductory series to `zip`

! This is only the beginning of our journey with `zip`

, there is still a
lot more to come.

Until next time!

👋 Hey there! If you got this far, then you must have enjoyed this post. You may want to also check out Point-Free, a video series on functional programming and Swift.