Extending Collection with a Recursive Property/Method That Depends on the Element Type

Extending Collection with a recursive property/method that depends on the element type

I don't believe that it's currently possible to write a recursive extension like this, where the base case is determined by the conformance of a static type.

Although note that Collection does have a count property requirement, it's just of type IndexDistance (an associated type), rather than Int. Therefore if this were possible, you could express it as:

extension Collection {
    var flatCount: IndexDistance {
        return count
    }
}

extension Collection where Iterator.Element: Collection {
    var flatCount: IndexDistance {
        // compiler error: unable to infer closure type in the current context
        // (if you expand it out, it will tell you that it's because
        //  $1.flatCount is ambiguous)
        return self.reduce(0) { $0 + $1.flatCount }
    }
}

However, this yields a compiler error (although why it doesn't for when flatCount is an Int, I have no idea – they should both either consistently compile or not compile). The problem is that Swift wants to statically dispatch $1.flatCount – therefore meaning that it can only pick one of the extensions to call (and in this case, the compiler thinks both are equally valid).

The only way static dispatch could work here is if the implementations were specialised for each concrete type of Collection that they're called on. In that case, the ambiguity would be resolved as the compiler would know the concrete type inside the implementation, and thus know whether Iterator.Element.Iterator.Element : Collection, and dispatch accordingly.

However, currently specialisation is only an optimisation (due to the fact that it has the potential to drastically bloat code size without the use of inlining to counteract this additional cost) – therefore it's not possible to guarantee that static dispatch would work for all cases.

Even if $1.flatCount was able to be dynamically dispatched, through for example a protocol witness table (see this great WWDC talk on them), overload resolution based on the type constraints of the extensions would need to take place at runtime (in order to determine which extension to call). However, Swift doesn't resolve overloads at runtime (it would be expensive). Instead, the overload itself is resolved at compile time, and dynamic dispatch then allows the implementation of that overload to be polymorphic with respect to the value that it's called on (i.e it can dispatch to a the value's own implementation of that overload).

Unfortunately, I think probably the closest you'll be able to get is to write an extension for Array and use conditional type-casting in order to iterate through nested arrays:

extension Array {
    var flatCount: Int {

        var iterator = makeIterator()

        if let first = iterator.next() as? [Any] {
            // must be an array of arrays – otherwise $1 as! [Any] will crash.
            // feel free to add error handling or adding support for heterogeneous arrays
            // by doing an O(n) walk.
            return iterator.reduce(first.flatCount) { $0 + ($1 as! [Any]).flatCount }
        } else {
            return count
        }
    }
}

let arr = [[[[2, 3, 4]], [3, 4, 5, 6]], [57, 89]]

print(arr.flatCount) // 9

Although note that as @MartinR points out in the comments below, the conversion as(?/!) [Any] will create a new array in most cases (due to the difference in how Swift stores concrete typed and abstract typed values – see this Q&A), making the above implementation not particularly efficient.

One potential solution to this is to use a 'dummy protocol' in order to declare the flatCount property:

// dummy protocol to prevent conversions of arrays with concrete-typed elements to [Any].
protocol _Array {
    var flatCount: Int { get }
}

extension Array : _Array {
    var flatCount: Int {

        var iterator = makeIterator()

        if let first = iterator.next() as? _Array {
            // same comment as above, can crash for heterogeneous arrays.
            return iterator.reduce(first.flatCount) { $0 + ($1 as! _Array).flatCount }
        } else {
            return count
        }
    }
}

This avoids the O(n) conversion from an array of concrete-typed elements to abstract-typed elements (instead, only a single box is created for a given array).

If we do a rough quick benchmark of the two implementations (in a Release build on a MacBook Pro) with the array:

let arr = Array(repeating: Array(repeating: Array(repeating: 1, count: 100), count: 100), count: 1000)

For 10 repeated calls to flatCount, the first extension gives a time of 31.7 seconds. The same benchmark applied to the second implementation yields 0.93 seconds.

Wrong specialized generic function gets called in Swift 3 from an indirect call

This is indeed correct behaviour as overload resolution takes place at compile time (it would be a pretty expensive operation to take place at runtime). Therefore from within test(value:), the only thing the compiler knows about value is that it's of some type that conforms to DispatchType – thus the only overload it can dispatch to is func doBar<D : DispatchType>(value: D).

Things would be different if generic functions were always specialised by the compiler, because then a specialised implementation of test(value:) would know the concrete type of value and thus be able to pick the appropriate overload. However, specialisation of generic functions is currently only an optimisation (as without inlining, it can add significant bloat to your code), so this doesn't change the observed behaviour.

One solution in order to allow for polymorphism is to leverage the protocol witness table (see this great WWDC talk on them) by adding doBar() as a protocol requirement, and implementing the specialised implementations of it in the respective classes that conform to the protocol, with the general implementation being a part of the protocol extension.

This will allow for the dynamic dispatch of doBar(), thus allowing it to be called from test(value:) and having the correct implementation called.

protocol DispatchType {
    func doBar()
}

extension DispatchType {
    func doBar() {
        print("general function called")
    }
}

class DispatchType1: DispatchType {
    func doBar() {
        print("DispatchType1 called")
    }
}

class DispatchType2: DispatchType {
    func doBar() {
        print("DispatchType2 called")
    }
}

func test<D : DispatchType>(value: D) {
    value.doBar()
}

let d1 = DispatchType1()
let d2 = DispatchType2()

test(value: d1)    // "DispatchType1 called"
test(value: d2)    // "DispatchType2 called"

Type conversion when using protocol in Swift

Code Different's answer is right, but it's also important to understand why you can't just reinterpret the data without something doing an O(n) conversion to walk though and wrap each element in a box.

[A] is an array with elements the size of A. So, more or less, A[1] is at memory location A[0] + sizeof(A) (this isn't exactly true, but pretend it is; it'll make things simpler).

[Test] has to be able to hold anything that conforms to the protocol. It might be the size of A, it might be the size of B, which is larger. To achieve that, it creates a box that holds "something that conforms to Test". The box is of a known size, and it may have to heap-allocate the thing it points to (or maybe not; depends), but it ain't going to be the same size as both A and B, so the layout of [Test] in memory has to be different than the layout of [A] or [B].

Now as [Test] could do that O(n) walk for you and force a copy right then. Or it delay the copy until the first time you modified something, but it would be much more complicated and it would bury an O(n) (possibly expensive, possibly memory allocating) event inside an as which feels like it should be O(1) and allocate no memory. So there's reasons not to do that.

Some day they may do it anyway to make things simpler on the caller, but there's a cost in both performance and complexity, and so it doesn't do it today and you need to do the map yourself.

If you want a much deeper dive into this stuff, with more details on how this box works (and less "pretend it's simpler than it is"), see Understanding Swift Performance from WWDC 2016.

Swift function taking generic array

To start, you're using the ternary operator (?:) in quite a complex situation. If you first modify your code to use an if statement instead, the compiler error that was appearing in the call to outputArray.append(data) - Generic parameter 'Element' could not be inferred - appears in a much more sensible place (namely, the line of the if statement).

That error is relatively easy to solve - simply replace Array with Array<Any>, giving us this:

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

    for i in 0..<input.count {
        let data = input[i]
        if data is Array<Any> {
            outputArray += flatten(input: [data])
        } else {
            outputArray.append(data)
        }
    }

    return outputArray
}

At this point, the original problem still occurs, because the value that's passed in to flatten(input:) is [data]. We know, due to the fact that the if condition was true, that data is really of type Array<Any>, and so the value [data] must be an Array<Array<Any>>. Instead, we want to pass in data, which is already an array.

You say that the reason you wrote [data] is because the argument has to be an array, and so you were "forced to" by the compiler. In fact, the only thing the compiler is forcing you to do is pass in an argument whose type is declared as Array<Any>. We've made sure that data is an array using the if statement, but data is still declared as an Any (because it was an element of input, which is an Array<Any>), so the compiler has no idea that it's really an array.

The solution is - instead of using if data is Array<Any> to determine momentarily whether data is an array but immediately throw that information away - to convert data to an Array<Any>.

The new if statement becomes if let dataArray = data as? Array<Any>. The statement data as? Array<Any> attempts to convert data to an array, returning a value of type Array<Any> if successful or nil otherwise. Then the if let dataArray = ... statement stores the value in dataArray and returns true if given a non-nil value, or returns false if given a nil value (this is called conditional binding).

By doing that, in the true case of the if statement we have access to a value dataArray that is of type Array<Any> - unlike data, which is only declared as Any. Then dataArray can be passed in to flatten(input:), and won't be nested inside another Array.

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

    for i in 0..<input.count {
        let data = input[i]
        if let dataArray = data as? Array<Any> {
            outputArray += flatten(input: dataArray)
        } else {
            outputArray.append(data)
        }
    }

    return outputArray
}

A couple of other notes:

Array<Any> is of course equivalent to [Any], so the if statement could be written with that (generally preferred) syntax, like so:

if let dataArray = data as? [Any] {
    outputArray += flatten(input: dataArray)
}

Also, there's no need to go through the whole for i in 0..<input.count { let data = input[i] ... ordeal if you just iterate over the array instead, like so:

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

    for data in input {
        if let dataArray = data as? [Any] {
            outputArray += flatten(input: dataArray)
        } else {
            outputArray.append(data)
        }
    }

    return outputArray
}

Search recursively for value in object by property name

You could use Object.keys and iterate with Array#some.

function findVal(object, key) {    var value;    Object.keys(object).some(function(k) {        if (k === key) {            value = object[k];            return true;        }        if (object[k] && typeof object[k] === 'object') {            value = findVal(object[k], key);            return value !== undefined;        }    });    return value;}
var object =  { photo: { progress: 20 }};console.log(findVal(object, 'progress'));

type AllPathsObject2 = Paths<typeof object2>;
// type AllPathsObject2 = ["nestedObject"] | ["nestedObject", "someProperty"] | 
//  ["anotherProperty"]

type LeavesObject2 = Leaves<typeof object2>;
// type LeavesObject2 = ["nestedObject", "someProperty"] | ["anotherProperty"]

let propertyPath1: Paths<typeof object1>;
propertyPath1 = ["someProperty"]; // works
propertyPath1 = ["doesntExist"]; // error!
//               ~~~~~~~~~~~~~~

let propertyPath2: Paths<typeof object2>;
propertyPath2 = ["nestedObject", "someProperty"]; // works
propertyPath2 = ["nestedObject", "doesntExist"]; // error!
//                               ~~~~~~~~~~~~~
propertyPath2 = ["doesntExist"]; // error!
//               ~~~~~~~~~~~~~

let count = compoundArray.joined().count

let count = compoundArray.flatMap({$0}).count

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

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])