Nondeterministic Computation with Arrays

List Comprehension.swift

// In languages like Python and Haskell, we can write list comprehension syntax like
// super simply to generate complex lists. Below, for example, we find all numbers that are
// the product of two sides of a triangle.
//   [a * b | a <- [1..10], b <- [1..10], c <- [1..10], a * a + b * b == c * c]

// Why is this called nondeterministic computation? Because we essentially try ALL possible combinations
// of these values (a,b) and--you can imagine--run them all simultanously and get the result that matches the predicate.
// Now, obviously, this doesn't all happen at the same time, but that's the idea behind the nondeterminism.

// Let's examine how we can get a similiar result in Swift! We'll start super simple and work
// up to more complicated solution using a magical function called flatMap by the end of this Gist :)

// The first thing to note is that something very simple like
//   [a * a | a <- [1..10]]
// can be accomplished very simply with Swift's map.

let squares = Array(1...10).map { a in a * a }
println(squares) // -> [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

// Cool! But you already knew that. This method doesn't allow us to specify complex dependencies
// between multiple variables or even combine multiple variables together. Let's first tackle that
// second part using a function called zip:

// Zip takes two sequences, like [1,2,3] and [7,8,9], and forms a new sequence by "zipping" them
// together!

let zipped = Array(zip([1,2,3],[7,8,9]))
println(zipped) // -> [(1, 7), (2, 8), (3, 9)]

// So, what if we want to add together the values in those two lists now
// a la [a + b | a <- [1,2,3], b <- [7,8,9]]? Well, we just apply a map just like before!

let summed = Array(zip([1,2,3],[7,8,9])).map { (a,b) in a + b }
println(summed) // -> [8, 10, 12]

// But wait, this isn't example what the list comprehension result gives...
// In list comprehension, we will get ALL possible combinations of a + b, that is
// [1 + 7, 1 + 8, 1 + 9, 2 + 7, 2 + 8, 2 + 9]

// It seems that zip only allows us to directly map two lists on each other rather than
// each element on each other element. What we're looking to do is get all the **combinations**
// of elements from the two lists.

// Hmmm, well, we could write a combination function and use that for all of our code, but that
// sounds kinda gross. There's got to be a better built-in way... Well, obviously that's the point
// of this Gist, there is!! Let me show it to you first, and then explain it.

let allSummed = [1,2,3].flatMap /* --> */ { (a: Int) in
                [7,8,9].flatMap /* --> */ { (b: Int) in
                return [a + b] }}

println(allSummed) // -> [8, 9, 10, 9, 10, 11, 10, 11, 12]

// And there we have it! How does that disgusting contraption work though?!
// Yeah, I admit its not pretty. In fact, its best to improperly indent it as
// it then looks more like a linear computation instead of a bunch of closures.

// First, let's get some intuition for what's happening before we dive into the dirty details.
// Just like a <- [1..3] in our list comprehension, we are binding 'a' to a value from the
// first array and 'b' to a value from the second one. You could imagine that this code happens
// for every possible combination of (a, b) bindings and combines the results.

// This isn't too far from the truth either. I think that the easiest way to understand this is
// to change "flatMap" to "map" and examine the results.

let learningA = [1,2,3].map /* --> */ { (a: Int) in
                [7,8,9].map /* --> */ { (b: Int) in
                return [a + b] }}

println(learningA) // -> [[[8], [9], [10]], [[9], [10], [11]], [[10], [11], [12]]]

// Weird! We have an array of arrays of arrays! The most inner arrays are just due to use
// returning [a + b] instead of a + b. We could change our return value, but, for symmetry,
// we decide to return this and flatten it instead. Let's apply that flatten.

let learningB = [1,2,3].map     /* --> */ { (a: Int) in
                [7,8,9].flatMap /* --> */ { (b: Int) in
                return [a + b] }}

println(learningB) // -> [[8, 9, 10], [9, 10, 11], [10, 11, 12]]

// Ah, now that's a bit more simple. We see that we have an array with our results for
// each value of 'a'. That is, [8, 9, 10]   for a = 1 and b <- [7, 8, 9]
//                             [9, 10, 11]  for a = 2 and b <- [7, 8, 9]
//                             [10, 11, 12] for a = 2 and b <- [7, 8, 9]

// Oh, and if we change the top "map" to "flatMap", it'll just combine our results! All into
// a single array! Makes sense, right?!

// Cool, so now that we understand the magic of flatMap, let's try to tackle our triangle example.
// The main difference is we have a filter, a * a + b * b == c * c, applied to our results.
// Now, we can't just generate an arary of tuples and then use the "filter" function because we
// want to return a * b. If we want to be able to access (a, b, c) together, we'd have to make
// an array of tuples using flatMap, filter that, and then map it to our result.

// There's a better way.

let triangles = Array(1...10).flatMap /* --------> */ { (a: Int) in
                Array(1...10).flatMap /* --------> */ { (b: Int) in
                Array(1...10).flatMap /* --------> */ { (c: Int) in
                return a * a + b * b == c * c ? [a * b] : [] }}}
println(triangles) // -> [12, 12, 48, 48]

// We return the product [a * b] only when it satisfies our condition! When it doesn't, we
// return the empty array which will dissappear when we flatten it.

// This is also why we returned an array before instead of just a single value. This way,
// we can return any number of results for every combination: 0, 1, or more!

// We can clean this up even more by defining a function named "guard" that will take in
// a condition, like a * a + b * b == c * c, and block any false conditions from getting
// any further in the computation. Observe:

func guard(condition: Bool) -> [()] {
    return condition ? [()] : []
}

// What's this type signature though!? An array of empty tuples, huh!?! We'll first use it
// in an example and then I'll explain it.

let betterTriangles = Array(1...10).flatMap /* --------> */ { (a: Int) in
                      Array(1...10).flatMap /* --------> */ { (b: Int) in
                      Array(1...10).flatMap /* --------> */ { (c: Int) in
                      guard(a * a + b * b == c * c).flatMap {
                      return [a * b] }}}}

println(betterTriangles) // -> [12, 12, 48, 48]

// We got the same result again, it worked! But huh, how? Let's get rid of the fla

let huhTriangles = Array(1...10).map /* --------> */ { (a: Int) in
                   Array(1...10).map /* --------> */ { (b: Int) in
                   Array(1...10).map /* --------> */ { (c: Int) in
                   guard(a * a + b * b == c * c).map {
                   return [a * b] }}}}

// I hope you're ready to scroll.......

println(huhTriangles) // -> [[[[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []]], [[[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []]], [[[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [[12]], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []]], [[[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [[12]], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []]], [[[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []]], [[[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], [[48]]], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []]], [[[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []]], [[[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], [[48]]], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []]], [[[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []]], [[[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []], [[], [], [], [], [], [], [], [], [], []]]]

// Wat

// Let me explain. Just like before, we have an array for a, each with an array for b, each with
// an array for c. This c array though, contains an array itself, the guard array, either [()] or [].

// Imagine the result of guard is [()]. Well, when we map over it, we map each element (), and well
// there is one, to the result. Thus, whenever guard returns [()], the result passes through.

let trueGuard: [()] = [()]
println(trueGuard.map { _ /* we ignore the () input */ in "Hello world!" }) // -> [Hello world!]

// Imagine the result of guard is []. When we map over it, there are no elements in it, so no matter
// what we're mapping, the result will still be the empty array.

let falseGuard: [()] = []
println(falseGuard.map { _ /* we ignore the () input */ in "Hello world!" }) // -> []

// And, as always, we flatten everything so all those empty arrays just dissapear. Nifty!

// Now that we understand this, let's try another example!

let triangleDimensions = Array(1...10).flatMap /* --------> */ { (a: Int) in
                         Array(1...10).flatMap /* --------> */ { (b: Int) in
                         Array(1...10).flatMap /* --------> */ { (c: Int) in
                         guard(a * a + b * b == c * c).flatMap {
                         return [(a,b,c)] }}}}

// Here are the triangles we we're looking at earlier!
println(triangleDimensions) // [(3, 4, 5), (4, 3, 5), (6, 8, 10), (8, 6, 10)]
// Looks like our filter worked! 9 + 16 == 25 and 64 + 36 == 100
// And our map worked too! 3 * 4 = 4 * 3 == 12 and 6 * 8 == 8 * 6 == 48

// Can we talk about something other than triangles please!? Sure, how about rectangeles :P
// Let's say we have an array of CGRects and we want to know which ones intersect.

import Foundation // need this

// Here's our array:
var rects = [CGRect]()
rects.append(CGRect(x: 0, y: 0, width: 10, height: 10))
rects.append(CGRect(x: 20, y: 0, width: 10, height: 10))
rects.append(CGRect(x: 0, y: 5, width: 10, height: 10))
rects.append(CGRect(x: 15, y: 5, width: 10, height: 10))


// Now for the fun code:
let intersection = rects.flatMap /* ------------------------------------------------> */ { (a: CGRect) in
                   rects.flatMap /* ------------------------------------------------> */ { (b: CGRect) in
                   guard(CGRectIntersectsRect(a, b) && !CGRectEqualToRect(a, b)).flatMap {
                   return [(a,b)] }}}

println(intersection) // -> [((0.0, 0.0, 10.0, 10.0), (0.0, 5.0, 10.0, 10.0)), ((20.0, 0.0, 10.0, 10.0), (15.0, 5.0, 10.0, 10.0)), ((0.0, 5.0, 10.0, 10.0), (0.0, 0.0, 10.0, 10.0)), ((15.0, 5.0, 10.0, 10.0), (20.0, 0.0, 10.0, 10.0))]

// One more example. Let's fine all numbers (a, b) where a is a mulplie of b and both a and b are greater than or equal to
// 30 and less than or equal to 100.

let multiples = Array(30...100).flatMap /* -------------> */ { (a: Int) in
                Array(30...100).flatMap /* -------------> */ { (b: Int) in
                guard(a % b == 0 && a != b && a > b).flatMap {
                return [(a,b)]}}}

println(multiples) // -> [(60, 30), (62, 31), (64, 32), (66, 33), (68, 34), (70, 35), (72, 36), (74, 37), (76, 38), (78, 39), (80, 40), (82, 41), (84, 42), (86, 43), (88, 44), (90, 30), (90, 45), (92, 46), (93, 31), (94, 47), (96, 32), (96, 48), (98, 49), (99, 33), (100, 50)]

// Tadah! Guess what? I just tricked you into learning about the list monad! 
// http://en.wikibooks.org/wiki/Haskell/Understanding_monads/List#List_comprehensions