Calculate the number of dimensions of a multi-dimensional array in Swift

Question

Suppose I have some function that I want to populate my data structure using a multi-dimensional array (e.g. a Tensor class):

class Tensor {
   init<A>(array:A) { /* ... */ }
}

while I could add in a shape parameter, I would prefer to automatically calculate the dimensions from the array itself. If you know apriori the dimensions, it's trivial to read it off:

let d1 = array.count
let d2 = array[0].count

However, it's less clear how to do it for an N-dimensional array. I was thinking there might be a way to do it by extending the Array class:

extension Int {
   func numberOfDims() -> Int {
      return 0
   }
}

extension Array {
   func numberOfDims() -> Int {
     return 1+Element.self.numberOfDims()
   }
}

Unfortunately, this won't (rightfully so) compile, as numberOfDims isn't defined for most types. However, I'm don't see any way of constraining Element, as Arrays-of-Arrays make things complicated.

I was hoping someone else might have some insight into how to solve this problem (or explain why this is impossible).

Answer 1

If you're looking to get the depth of a nested array (Swift's standard library doesn't technically provide you with multi-dimensional arrays, only jagged arrays) – then, as shown in this Q&A, you can use a 'dummy protocol' and typecasting.

protocol _Array {
    var nestingDepth: Int { get }
}

extension Array : _Array {
    var nestingDepth: Int {
        return 1 + ((first as? _Array)?.nestingDepth ?? 0)
    }
}

let a = [1, 2, 3]
print(a.nestingDepth) // 1

let b = [[1], [2, 3], [4]]
print(b.nestingDepth) // 2

let c = [[[1], [2]], [[3]], [[4], [5]]]
print(c.nestingDepth) // 3

^{(I believe this approach would've still worked when you had originally posted the question)}

In Swift 3, this can also be achieved without a dummy protocol, but instead by casting to [Any]. However, as noted in the linked Q&A, this is inefficient as it requires traversing the entire array in order to box each element in an existential container.

Also note that this implementation assumes that you're calling it on a homogenous nested array. As Paul notes, it won't give a correct answer for [[[1], 2], 3].

If this needs to be accounted for, you could write a recursive method which will iterate through each of the nested arrays and returning the minimum depth of the nesting.

protocol _Array {
    func _nestingDepth(minimumDepth: Int?, currentDepth: Int) -> Int
}

extension Array : _Array {

    func _nestingDepth(minimumDepth: Int?, currentDepth: Int) -> Int {

        // for an empty array, the minimum depth is the current depth, as we know
        // that _nestingDepth is called where currentDepth <= minimumDepth.
        guard !isEmpty else { return currentDepth }

        var minimumDepth = minimumDepth

        for element in self {

            // if current depth has exceeded minimum depth, then return the minimum.
            // this allows for the short-circuiting of the function.
            if let minimumDepth = minimumDepth, currentDepth >= minimumDepth {
                return minimumDepth
            }

            // if element isn't an array, then return the current depth as the new minimum,
            // given that currentDepth < minimumDepth.
            guard let element = element as? _Array else { return currentDepth }

            // get the new minimum depth from the next nesting,
            // and incrementing the current depth.
            minimumDepth = element._nestingDepth(minimumDepth: minimumDepth,
                                                 currentDepth: currentDepth + 1)
        }

        // the force unwrap is safe, as we know array is non-empty, therefore minimumDepth 
        // has been assigned at least once.
        return minimumDepth!
    }

    var nestingDepth: Int {
        return _nestingDepth(minimumDepth: nil, currentDepth: 1)
    }
}

let a = [1, 2, 3]
print(a.nestingDepth) // 1

let b = [[1], [2], [3]]
print(b.nestingDepth) // 2

let c = [[[1], [2]], [[3]], [[5], [6]]]
print(c.nestingDepth) // 3

let d: [Any] = [ [[1], [2], [[3]] ], [[4]], [5] ]
print(d.nestingDepth) // 2 (the minimum depth is at element [5])

Answer 2

Great question that sent me off on a goose chase!

To be clear: I’m talking below about the approach of using the outermost array’s generic type parameter to compute the number of dimensions. As Tyrelidrel shows, you can recursively examine the runtime type of the first element — although this approach gives nonsensical answers for heterogenous arrays like [[[1], 2], 3].

Type-based dispatch can’t work

As you note, your code as written doesn’t work because numberOfDims is not defined for all types. But is there a workaround? Does this direction lead somewhere?

No, it’s a dead end. The reason is that extension methods are statically dispatched for non-class types, as the following snippet demonstrates:

extension CollectionType {
  func identify() {
    print("I am a collection of some kind")
  }

  func greetAndIdentify() {
    print("Hello!")
    identify()
  }
}

extension Array {
  func identify() {
    print("I am an array")
  }
}

[1,2,3].identify()         // prints "I am an array"
[1,2,3].greetAndIdentify() // prints "Hello!" and "I am a collection of some kind"

Even if Swift allowed you to extend Any (and it doesn’t), Element.self.numberOfDims() would always call the Any implementation of numberOfDims() even if the runtime type of Element.self were an Array.

This crushing static dispatch limitation means that even this promising-looking approach fails (it compiles, but always returns 1):

extension CollectionType {
  var numberOfDims: Int {
    return self.dynamicType.numberOfDims
  }

  static var numberOfDims: Int {
    return 1
  }
}

extension CollectionType where Generator.Element: CollectionType {
  static var numberOfDims: Int {
    return 1 + Generator.Element.numberOfDims
  }
}

[[1],[2],[3]].numberOfDims   // return 1 ... boooo!

This same constraint also applies to function overloading.

Type inspection can’t work

If there’s a way to make it work, it would be something along these lines, which uses a conditional instead of type-based method dispatch to traverse the nested array types:

extension Array {
  var numberOfDims: Int {
    return self.dynamicType.numberOfDims
  }

  static var numberOfDims: Int {
    if let nestedArrayType = Generator.Element.self as? Array.Type {
        return 1 + nestedArrayType.numberOfDims
    } else {
        return 1
    }
  }
}

[[1,2],[2],[3]].numberOfDims

The code above compiles — quite confusingly — because Swift takes Array.Type to be a shortcut for Array<Element>.Type. That completely defeats the attempt to unwrap.

What’s the workaround? There isn’t one. This approach can’t work because we need to say “if Element is some kind of Array,” but as far as I know, there’s no way in Swift to say “array of anything,” or “just the Array type regardless of Element.”

Everywhere you mention the Array type, its generic type parameter must be materialized to a concrete type or a protocol at compile time.

Cheating can work

What about reflection, then? There is a way. Not a nice way, but there is a way. Swift’s Mirror is currently not powerful enough to tell us what the element type is, but there is another reflection method that is powerful enough: converting the type to a string.

private let arrayPat = try! NSRegularExpression(pattern: "Array<", options: [])

extension Array {
  var numberOfDims: Int {
    let typeName = "\(self.dynamicType)"
    return arrayPat.numberOfMatchesInString(
        typeName, options: [], range: NSMakeRange(0, typeName.characters.count))
  }
}

Horrid, evil, brittle, probably not legal in all countries — but it works!

Answer 3

Unfortunately I was not able to do this with a Swift array but you can easily convert a swift array to an NSArray.

extension NSArray {
    func numberOfDims() -> Int {
        var count = 0
        if let x = self.firstObject as? NSArray {
            count += x.numberOfDims() + 1
        } else {
            return 1
        }
        return count
    }
}