Maybe a List
July 22, 2018
Last time we started to look at why we might want to use an Optional type. In this and the following posts, we'll look at ways of implementing it.
Many speakers will say in passing that you don't need an Optional type, you can just use a List that has one or no members.
I've always nodded my head at this but never thought too much about it.
In this post, I'll experiment with one way of implementing Optional using List. I'm not making an Optional a List as (even if I used classes not structs) it really isn't a subtype. An Optional can't just be substituted for a List.
Instead, I'll use composition and take advantage of List capabilities including map() and flatMap().
Today's code comes from this sample code and here's the Playground it comes from.
To begin, here's my start on an optional type which I'll call Opt.
struct Opt<Wrapped> {
private let backingList: List<Wrapped>
}
We think of an optional as being either nil or wrapping a value. I've put List.swift in the page's sources.
Here are inits for creating these. Note that I've put these in an extension so the default init is still created.
extension Opt {
init(_ value: Wrapped) {
self.init(backingList: List(value))
}
init() {
self.init(backingList: List())
}
}
We can create instances of Opt like this. Note that we have to help the compiler to know which nil-valued Opt we're creating.
Opt(5)
Opt<Int>()
Let's add convenience methods for extracting the optional's value, determining whether it is nil, and printing it.
extension Opt {
init(_ value: Wrapped) {
self.init(backingList: List(value))
}
init() {
self.init(backingList: List())
}
var value: Wrapped {
return backingList.head
}
var isNil: Bool {
return backingList.isEmpty
}
}
extension Opt: CustomStringConvertible
where Wrapped: CustomStringConvertible {
var description: String {
if isNil {return "nil"}
else {return "Opt(" + backingList.head.description + ")"}
}
}
So here's a version of our echo function that returns an even input and returns an Opt if we submit an odd input.
func echoEvenOrNil(_ input: Int) -> Opt<Int> {
guard input.isEven else { return Opt()}
return Opt(input)
}
We can use it as before.
echoEvenOrNil(2)
echoEvenOrNil(3)
We see Opt(1) and nil as the feedback.
OK, now is when we start getting serious. Create a function from (Int) -> Int.
func halve(_ input: Int) -> Int {
return input/2
}
How do we compose echoEvenOrNil and halve? After all, the output of the first doesn't match the input of the second - it's that input wrapped in an Opt.
Functional people are probably getting ahead of me and see that we need a map. For now, let's start by creating a function that bridges the gap.
Soon we won't need to do the following:
func halveEvenOrNil(_ input: Opt<Int>) -> Opt<Int> {
if input.isNil {return Opt()}
else {
return Opt(halve(input.value))}
}
We can take the output of echoEvenOrNil which is an Opt<Int> and pass it to halve if it's not nil by checking and unwrapping.
The results of calling
halveEvenOrNil(echoEvenOrNil(2))
halveEvenOrNil(echoEvenOrNil(3))
are Opt(1) and nil.
I've defined |> in the page sources so that a |> f is f(a).
This allows us to rewrite the call above to
2 |> echoEvenOrNil |> halveEvenOrNil
3 |> echoEvenOrNil |> halveEvenOrNil
The results are, of course, the same.
Now if you have a function (Int) -> Opt<Int> and another from (Int) -> Int, we can combine them easily if we define map() on Opt.
So let's do so.
Because we've defined Opt from List we can define one map in terms of the other. I've also added a custom operator implementation.
extension Opt {
func map<Output>(_ f: @escaping (Wrapped) -> Output)
-> Opt<Output> {
return Opt<Output>(backingList: backingList.map(f))
}
}
func <^>;<A, B>(a: Opt<A>,
f: @escaping (A) -> B) -> Opt<B> {
return a.map(f)
}
Now we can stream from echoEvenOrNil to halve using map().
echoEvenOrNil(2).map(halve)
echoEvenOrNil(3).map(halve)
2 |> echoEvenOrNil <^> halve
3 |> echoEvenOrNil <^> halve
You should see Opt(1) and nil for the results.
That's map(). What about flatMap()?.
To set that up, here's a dictionary and a function that returns values for keys. Note the function takes Ints and returns Opt<String>s.
let numberDictionary = [1: "one", 2: "two", 3: "three"]
func valueInNumberDictionary(for key: Int) -> Opt<String> {
guard numberDictionary.keys.contains(key) else {return Opt()}
return Opt(numberDictionary[key]!)
}
Use the function on its own like this.
valueInNumberDictionary(for: 2)
valueInNumberDictionary(for: 3)
valueInNumberDictionary(for: 4)
The results are Opt(2), Opt(3), and nil.
So why can't we just use map() to pipe echoEvenOrNil into valueInNumberDictionary?
The types don't match. The first function takes (Int) -> Opt<Int> and the second takes (Int) -> Opt<String>. If we use map() we double wrap the results.
echoEvenOrNil(2).map(valueInNumberDictionary)
echoEvenOrNil(3).map(valueInNumberDictionary)
echoEvenOrNil(4).map(valueInNumberDictionary)
The results are Opt(Opt(two)), nil, and Opt(nil).
The types point us to needing a flatMap() instead. Here's how we implement it using the List implementation to help.
extension Opt {
public func flatMap<Output>(_ f: @escaping (Wrapped)
-> Opt<Output> )
-> Opt<Output> {
return Opt<Output>(backingList: backingList.flatMap{x in
f(x).backingList
})
}
}
func >=><A, B>(a: Opt<A>,
f: @escaping (A) -> Opt<B>) -> Opt<B> {
return a.flatMap(f)
}
Use flatMap() like this.
echoEvenOrNil(2).flatMap(valueInNumberDictionary)
echoEvenOrNil(3).flatMap(valueInNumberDictionary)
echoEvenOrNil(4).flatMap(valueInNumberDictionary)
2 |> echoEvenOrNil >=> valueInNumberDictionary
3 |> echoEvenOrNil >=> valueInNumberDictionary
4 |> echoEvenOrNil >=> valueInNumberDictionary
The results are Opt(two), nil, and nil.
There are other ways to base an optional type on a list type but this was a fun excursion.
In the next post we'll implement the optional type in a more traditional way.