Functions for Hire

The higher-order functions in Swift (map(), flatMap(), reduce(), filter()) can allow you to write functional, powerful, and beautiful code. They can also allow you to write very bad code. It can be unreadable (“I’m not golfing, I swear, it’s just more functional“) and slow (using reduce() to build an array is O(n²)). For me in particular, they can encourage bad practices, like long, var-less closures: the kinds that produce the error in the picture above. (Xcode’s limitation on expression complexity is definitely more of a help than a hinderance, though: I see that error as a gentle suggestion that my code is golfy, rubbish, and too clever for its own good)

(to be clear, I’m probably blaming the wrong thing: functional programming doesn’t necessitate long closures, golfy code, or arrays from reduce(). But for me, they often go hand in hand.)

Nonetheless, sometimes it’s fun to abuse and overuse map(). And, as an intellectual exercise, maybe it’ll even help me learn some new things! With that in mind, I decided to think of the expression complexity limit as more of an expression complexity target, get out my programming S&M gear, and abuse some higher functions.

Problem 5 got thinking about permutations. For the problem, I had to write a function that would return permutations of a given array of objects. Being as concerned with accuracy as I am, I had done a quick check to see if I was using the word “permutations” correctly (checking, of course, that bastion of accuracy: Wikipedia). Turns out, I wasn’t. I was talking about n-tuples (permutations with repetition), which are slightly different. With nothing but a vague memory of high school math to guide me, I proceeded down the Wikipedia rabbit-hole, and emerged with three new definitions: permutations, n-tuples, and combinations.

Seeing as I had already implemented a functional way to get my n-tuples, I decided that combinations and permutations were as good a place as any to get all 50 shades with some higher functions. I started with my old function for n-tuples:

func addPermWithRep<T>(objects: [T], prevPerms: [[T]]) -> [[T]] {

  return prevPerms.flatMap() {

    perm in objects.map() {

      object in perm + [object]

    }
  }
}

func permsWithRepOfLength<T>(objects: [T], length: Int) -> [[T]] {

  return [Int](1..<length)
    .reduce( objects.map() {[$0]}) {

      (prevPerms, _) in

      addPermWithRep(objects, prevPerms)

    }
}

n tuples cropped
So the first function here takes previous permutations, and an array of objects, and returns new permutations, each permutation being one of the previous permutations plus one of the objects. The second function takes objects, and repeats the first function a given number of times until the desired length of permutation is reached.

Actual permutations don’t have repetitions – no object appears twice in any given permutation. The previous function is easily adaptable to this – since it already layers on new permutations from a given list of objects, just give it a list of objects that only contains objects not already used. Well, easily adaptable with some catches.

First of all, the old function uses the same list of objects for every previous permutation. Obviously, the array of objects used already with be different for every permutation, so that won’t work. I decided that my new function was not going to take a list of permutations; it would instead take one permutation, and a list of objects not included in that permutation. So:

addPerm<T>(objects: [T], prevPerm: [T])...

Instead of:

addPermWithRep<T>(objects: [T], prevPerms: [[T]])...

Obviously, this hands a little more work off to the handler function. Next issue was what it would return: it couldn’t just give back its generated permutations, as we also need to know what objects are left. I decided an array of tuples was the way to do this:

func addPerm<T>
  (objects: [T], prevPerm: [T]) ->
  [(objectsRemaining: [T], prevPerm: [T])]...

I figured the handler function could slough off the remaining objects in the tuple, for when it was returning its nice, clean permutations:

return permTuples
  .map() { $0.1 }

And so I was all set. I knew what it was going to do, now I needed to know how it did it. My first try modelled it off of the old function, map()ing through the objects, but this time, removing the current object from the objects array in each tuple. Like this:

func addPerm
  <T: Equatable>(var objectsRemaining: [T], prevPerm: [T])
  -> [(objectsRemaining: [T], prevPerm: [T])] {

  return map(objectsRemaining) {

    object in

    objectsRemaining.removeAtIndex(find(objectsRemaining, object)!)

    return (

      objectsRemaining: objectsRemaining,

      prevPerm: prevPerm + [object]

    )
  }
}

Again, removing items from an array as you iterate over it? Asking for trouble. Every sequential objectsRemaining would be missing not just one object, but every object that had been removed before it (that’s assuming it even runs). I could duplicate the array:

func addPerm
  <T: Equatable>(objectsRemaining: [T], prevPerm: [T]) ->
  [(objectsRemaining: [T],prevPerm: [T])] {

  return map(objectsRemaining) {

    object in

    var withoutObject = objectsRemaining

    withoutObject.removeAtIndex(find(withoutObject, object)!)

    return (

      objectsRemaining: withoutObject,

      prevPerm: prevPerm + [object]

    )
  }
}

I didn’t like it, though. find() every time? Well, I should know what index I’m looking for, since I’m iterating through the array I’m removing from. enumerate() should do the trick:

func addPerm
  <T>(objectsRemaining: [T], prevPerm: [T]) ->
  [(objectsRemaining: [T], prevPerm: [T])] {

  return map(enumerate(objectsRemaining)) {

    (index, object) in

    var withoutObject = objectsRemaining

    withoutObject.removeAtIndex(index)

    return (

      objectsRemaining: withoutObject,

      prevPerm: prevPerm + [object]

    )
  }
}

And it did!

removeAtIndex() returns an object, though, which I’m just throwing away. Bit wasteful, really. I could use it in the return statement, and I’d lose a line. In fact, since all I’m using is the indices, then, I can just iterate through those, so no messy map(enumerate()). Let’s try it:

func addPerm
  <T>(prevCombo: [T], objectsRemaining: [T]) ->
  [(prevCombo: [T], objectsRemaining: [T])] {

  return (0..<objectsRemaining.count)
    .map() {

      var withoutObject = objectsRemaining

      return (

        prevCombo: prevCombo + [withoutObject.removeAtIndex($0)],

        objectsRemaining: withoutObject

      )
    }
}

Ooh, much nicer. (I had to swap the return tuple around, though, bear in mind)

Now, to get rid of the duplicate array. Easiest way I saw was to just split up the objectsRemaining list: into a slice up to but not including the index, and a slice beyond the index to the end. A little bit like this. Modify my function to return an ArraySlice, not an Array, and here it is:

func addPerm<T>
  (prevPerm: [T], objects: ArraySlice<T>) ->
  [(prevPerm: [T], objects: ArraySlice<T>)] {

  return map(enumerate(objects)) {

    (index, object) in

    return (

      prevPerm: prevPerm + [object],

      objects: (objects[0..<index] + objects[(index+1)..<objects.count])

    )
  }
}

Brilliant. There’s a problem, though. I think I might have stretched a little too far in my functional pursuit: this new function is less clear, has a line that’s way too long, and is slower. I felt I had reached a point where I would have to decide between what is cool, and what is right. (assuming I hadn’t crossed that line already…) So I decided to leave it the old way, happy knowing that it could be done differently.

The rest of it was pretty much the same as the old function, reduce()ing over a range given by the length argument. Here are both of the functions together, handler and addPerm:

func addPerm
  <T>(prevCombo: [T], objectsRemaining: [T]) ->
  [(prevCombo: [T], objectsRemaining: [T])] {

    return (0..<objectsRemaining.count)
      .map() {

        var withoutObject = objectsRemaining

        return (

          prevCombo: prevCombo + [withoutObject.removeAtIndex($0)],

          objectsRemaining: withoutObject

        )
      }
}

func permsOfLength
  <T>(objects: [T], length: Int)
  -> [[T]] {

  return [Int](1...length)
    .reduce([(prevCombo: [T](), objectsRemaining: objects)]) {

      (accum, _) in

      accum.flatMap() {

        addPerm($0, $1)

      }
    }.map() { $0.0 }
}

permsOfLength([1, 2, 3], 3)
//[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

The next job was the last, and the hardest: combinations.

Combinations

Not only do combinations not repeat objects within each array, they also don’t repeat arrays. But, neither did our past function: how is this different? Well, a combination function ignores order within arrays. So it would see [1, 2] as the same as [2, 1], making our past function full of repetitions. Now, I could just add a function to my previous function: something to go through its permutations and remove duplicates, ignoring order. But we both know that’s not what happened.

I started with that diagram above, and tried to figure out how to write that as a function. I could see I would have to walk along my list of objects, and pair each with every other object it hadn’t been paired with. So I would first iterate through my objects:

for pivotObject in objects {...

Where pivotObject is the blue circle with a yellow dot in it in the animation.

Also, it was clear that the number of new pairings for each pivotObject was one less than the previous pivotObject. More than that, the list of objects each new pivotObject would pair from was always the same as the list of objects for the previous pivotObject, minus the previous pivotObject. Something like this might work:

var objectList = objects

var pairList = [[T]]()

for pivotObject in objects {

  objectList.removeAtIndex(find(objectList, pivotObject)!)

  for objectToPair in objectList {

    pairList.append([pivotObject, objectToPair])
  }
}

We can change line 7, since we know we’re going in order:

objectList.removeAtIndex(0)

Hmm… removing the first element each time? That’s O(objectList.count). We’ll iterate through it backwards, so, with removeLast(). That feels more like a while loop to me, with the condition being !objectList.isEmpty. And, to top it all off, let’s do extend() and map(), instead of a for loop with append. Our function sundae, then, is:

let objects = [1, 2, 3, 4]

var objectList = objects

var pairList = [[Int]]()

while !objectList.isEmpty {

  let pivotObject = objectList.removeLast()

  pairList.extend(objectList.map() {[pivotObject, $0]})

}

//[[4, 1], [4, 2], [4, 3], [3, 1], [3, 2], [2, 1]]

But that’s the easy part. The real question is: how do we do it for combinations longer than two?

I ended up understanding it like this: the function would take a single combination, and a single array of objects. The function would then return an array of tuples (combinations, pivotLists), which could be map()ed, flatMap()ed, etc. Crucially, the second element in each of those tuples, the pivotList, would be one element smaller than its predecessor. Some code might make it clearer:

func addCombo
  <T>(prevCombo: [T], var pivotList: [T]) -> [([T], [T])] {

  var toReturn = [([T], [T])]()

  while !pivotList.isEmpty {

    toReturn.append((

      prevCombo + [pivotList.removeLast()],

      pivotList

    ))
  }

  return toReturn
}

If you give this function ([1, 2, 3], [4, 5, 6]), it’ll give you back:

[
  ([1, 2, 3, 6], [4, 5]),
  ([1, 2, 3, 5], [4]),
  ([1, 2, 3, 4], [])
]

The first tuple elements being the combinations, the second being the objects you’re allowed to pivot from.

The handler function, again, is pretty much the same as always:

func combosOfLength<T>(objects: [T], length: Int) -> [[T]] {

  return [Int](1...length)
    .reduce([([T](), objects)]) {

      (accum, _) in

      accum.flatMap() {addCombo($0, $1)}

    }.map() {$0.0}
}

combosOfLength([1, 2, 3, 4], 3)
//[[4, 3, 2], [4, 3, 1], [4, 2, 1], [3, 2, 1]]

Perfect. There is, of course, one more thing: there’s a toReturn. It’s gotta go. We can just replicate the behaviour of the while loop, by map()ing over a range given by pivotList.count:


func addCombo<T>(prevCombo: [T], var pivotList: [T]) -> [([T], [T])] {

  return (0..<pivotList.count)
    .map() {

      _ -> ([T], [T]) in (

        prevCombo + [pivotList.removeLast()],

        pivotList
      )
  }
}

And we’re good to go. It consumes pivotList as it goes, just like the while loop, so the parameter needs to be var. Other than that, it’s pretty clean. (in fact, it’s the same as our addPerm function, except that where before, we wanted to avoid consuming the pivotList as we went, here, it’s essential) Here’s the whole thing together:

func addCombo<T>(prevCombo: [T], var pivotList: [T]) -> [([T], [T])] {

  return (0..<pivotList.count)
    .map() {

      _ -> ([T], [T]) in (

        prevCombo + [pivotList.removeLast()],

        pivotList

      )
  }
}
func combosOfLength<T>(objects: [T], length: Int) -> [[T]] {

  return [Int](1...length)
    .reduce([([T](), objects)]) {

      (accum, _) in

      accum.flatMap() {addCombo($0, $1)}

    }.map() {$0.0}
}

combosOfLength([1, 2, 3, 4], 3)
//[[4, 3, 2], [4, 3, 1], [4, 2, 1], [3, 2, 1]]

Lovely.

by the way, if you’re wondering about the code at the beginning, here it is:

let N = {
  d, n in
  reduce([Int](0..<(n*n)), (""), {
    a, b in
    a + ((d(b, n) || d(b, n+1)) ? "N" : (d(b + 1, n) ? "N\n" : " "))
  })
}({$0%$1 == 0}, 5)

and a version that will run without the error:

let d = {$0%$1 == 0}
let N = {
  n in
  reduce([Int](0..<(n*n)), (""), {
    a, b in
    a + ((d(b, n) || d(b, n+1)) ? "N" : (d(b + 1, n) ? "N\n" : " "))
  })
}(5)
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s