Generic array flattening function

Question

With help from the codereview community, I've written a function to flatten a generic nested array. I have it written several ways but want to focus on the following implementation:

func flatten (input: [Any]) -> [Any] {


    var outputArray = [Any] ()

    for i in 0..<input.count {
        let data = input[i];
        (data is [Any]) ? outputArray += flatten(input: data as! [Any]) : outputArray.append(data)

    }

    return outputArray

}

Is there a more "swifty" way to write this without using higher order functions?

Additionally, I've been reading about tail call optimization and wonder how I can make this tail call optimized?

Answer 1

A caveat & context: I'm writing this answer because I think it's an interesting question, however I'm drawing from CS lectures from 15 years ago and some hasty Googling, so rather than aiming for a correct answer, I'm hoping this will prompt some responses from smarter people.

flatten1:

First of all, an iteration of your original function. The only thing that stood out was that the ternary operation was a bit hard to read on a single line.

I don't like using white-space for formatting, but in this case I'd probably put each expression on it's own line:

(data is [Any]) 
  ? outputArray += flatten(input: data as! [Any]) 
  : outputArray.append(data)

But in this case I prefer to use avoid the short hand format, and use the longer conditional assignment, which I prefer because then you can avoid the forced cast to [Any]:

func flatten1(input: [Any]) -> [Any] {

    var flattened = [Any] ()

    for index in 0..<input.count {
        let element = input[index]

        if let array = element as? [Any] {
            flattened.append(contentsOf: flatten1(input: array))
        }
        else {
            flattened.append(element)
        }
    }

    return flattened
}

flatten2:

The second iteration was that I moved the loop into the recursion. As far as I know (and it is likely that I misunderstand this), compliers can't perform a tail call optimization unless you pass through an accumulator that collects up the value as the recursive calls are made (otherwise the runtime needs to increase memory to keep track of the incremental values, then perform some operation - in this case concatinating arrays, as it works itself back to the first recursive call).

func flatten2(input: [Any]) -> [Any] {

    guard let head = input.first else { return [] }

    if let headArray = head as? [Any] {
        return flatten2(input: headArray) + flatten2(input: Array(input.dropFirst()))
    }
    else {
        return [head] + flatten2(input: Array(input.dropFirst()))
    }
}

flatten3:

With that in mind, here's a third iteration using an accumulator:

func flatten3(input: [Any], accumulated: [Any] = []) -> [Any] {

    guard let head = input.first else { return accumulated }

    if let headArray = head as? [Any] {
        return
            flatten3(input: Array(input.dropFirst()),
                     accumulated: flatten3(input: headArray, accumulated: accumulated))
    }
    else {
        var _accumulated = accumulated
        _accumulated.append(head)

        return flatten3(input: Array(input.dropFirst()),
                        accumulated: _accumulated)
    }
}

Comparisons

I made an attempt at profiling these to compare performance with each other. I can into a bit of a stumbling block here when I tried to manually write in a deeply nested array where Xcode gave an Expression was too complex to be solved in reasonable time error. I ended up creating the nested array for testing like this:

var input: [Any] = []

override func setUp() {

    let test: [Any] = [1, [2], [3, [4]], [5, [6]], 7, [8], [[[[9, [10]]], [11, [12], 13]], 14, [15, [16]], [17, [18]], 19], 20, [21, 22], [23, 24, 25]]

    let level1 = [test, test, test, test, test]
    let level2 = [level1, level1, level1, level1]
    let level3 = [level2, level2, level2, level2]
    let level4 = [level3, level3, level3, level3]
    input = [level4, level4, level4, level4]
}

So now for testing (MBP late 2016, using -O3 flag for optimization):

flatten1    0.089s  6% STDEV
flatten2    0.599s  4% STDEV
flatten3    3.297s  3% STDEV
flatMap     0.000s  175% STDEV (actual time ranged 0.000016s to 0.000251s)

So flatten3 is actually a lot slower than the original loop approach, but with the benefit (if tail-call optimization is performed) of using a constant amount of memory.

But the standout is how fast flatMap performs. The post asks for ways to write the function more swifty, but unless you're planning the fucntion to have some sort of additional side effects as the intermediary steps are performed, then the simple input.flatmap{ $0 } is the best case on all fronts!

Edit: As @MartinR points out, flatMap only flattens the first level. I feel a bit silly for not actually checking the output. I've also realized that I don't understand flatMap as shown by this snippet...

print([[1, 2], [3, 4]].flatMap{ $0 })
// -> [1, 2, 3, 4] (expected output)

print([1, [2, 3, 4]].flatMap{ $0 })
// -> [1, [2, 3, 4]] (I didn't expect this!)

Here's a gist if anyone wants to use this as a starting point of their own -- like I started the post, it would be great to see someone more experienced chime in with thoughts or corrections :)