Implementing Foldable, Map and FlatMap

Thanks to Lukas for the illustration

I have been spending a good portion of my time studying SICP. SICP avoids focusing on the terms such as Functor (Map) and Monad (FlatMap) and instead focuses solely on their implementations and the power they provide us.

You can find all the code below in the following playground:

The implementations are surprisingly simple. Look at the implementation of Optional’s Map in Swift’s very own source code.

public func map<U>(
_ transform: (Wrapped) throws -> U) rethrows -> U? {
switch self {
case .some(let y):
return .some(try transform(y))
case .none:
return .none
}
}

Most developers I know make heavy use of Map and FlatMap. I do think it is of utmost importance to understand their implementations in order to understand how they actually work across different Types. As an exercise try code Array’s implementation of Map and FlatMap before reading further.

In order to implement FlatMap, we will use two functions as building blocks, reduce (sometimes referred to as Accumulate or FoldRight) and Map. So let’s implement reduce first.

func reduce<A, B>(
_ fn: (A, B) -> B, _ initial: B, _ list: [A]) -> B {
guard let value = list.first else {
return initial
}

return fn(value, reduce(fn, initial, Array(list.dropFirst(1))))
}

The above function is recursive. It executes in the following way:

let sum: (Int, Int) -> Int = { a, b in a + b }
reduce(sum, 0, [1, 2, 3])
// return fn(value, reduce(fn, initial, Array(list.dropFirst(1))))
// fn(1, fn(2, fn(3, 0)))
// fn(1, fn(2, 3))
// fn(1, 5)
// 6

Now you can see why it is sometimes referred to as FoldRight. It executes from right to left. If we want to write an implementation for FoldLeft, we can write the same function iteratively.

func foldLeft<A, B>(
_ fn: (A, B) -> B, _ initial: B, _ list: [A]) -> B {

func iter(_ fn: (A, B) -> B, _ result: B, _ list: [A]) -> B {
guard let value = list.first else {
return result
}
return iter(fn, fn(value, result), Array(list.dropFirst(1)))
}

return iter(fn, initial, list)
}

Now let’s implement Map.

func map<A, B>(_ fn: (A) -> B, _ list: [A]) -> [B] {
guard let value = list.first else {
return []
}

return [fn(value)] + map(fn, dropFirst(list))
}

Pretty simple. Do you see the correlation between Optional’s implementation and the Array’s implementation? Both unwrap the value and pass it to the function, take the result produced by the function, and finally wrap the altered value back up in its corresponding type: .some(fn(value)) & [fn(value)]. If you look at any other Type’s implementation of Map, you will find the exact same thing SomeType(fn(value)).

Now let’s implement the final function, FlatMap. The simplest of the three, but the most dense.

func flatMap<A, B>(_ fn: (A) -> [B], _ list: [A]) -> [B] {
return foldRight(+, [], map(fn, list))
}
let square: (Int) -> [Int] = { x in [x * x] } map(square, [1, 2, 3]) // [[1], [4], [9]]
flatMap(square, [1, 2, 3]) // [1, 4, 9]

Spend time thinking about how the above using both FoldRight (the reduce method we implemented in the beginning) and Map produces the correct result.

The above is exactly why functional programming, to me, is so powerful. The combination of FoldRight and Map to produce FlatMap is pure elegance.

FlatMap just takes the value and unlike Map, does not re-wrap the value in its corresponding type. That’s it. So if you have a nested type you solve it with the following use of FlatMap:

let value = Optional.some(Optional.some(5))
print(value.flatMap { $0 }) // Optional.some(5)

The main inspiration for the article came from the following problem introduced to me in SICP, and is a fitting conclusion:

We can solve the problem using only FlatMap and Map (no loops or assignment). Something that took me quite some time to wrap my head around and I hope that it inspires you the same way it did me.

func remove<A: Equatable>(_ a: A, _ arr: [A]) -> [A] {
return arr.filter { x in a != x }
}
func permutations(_ list: [Int]) -> [[Int]] {
if list.isEmpty {
return [[]]
}
return flatMap({ x in
return map({ y in
[x] + y
}, permutations(remove(x, list)))
}, list)
}
permutations([1, 2, 3])
// [
// [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]
// ]

If you enjoyed this article, please get in touch with me below:

All the code above can be found here:

Flawless iOS

🍏 Community around iOS development, mobile design, and…

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store