使用取决于元素类型的递归属性/方法扩展Collection

Question

在这个问题的上下文中，我将探讨如何实现一种属性或方法，该属性或方法将遍历集合中 所有 嵌套级别。

直观地，这应该起作用：

extension Collection { 
    var flatCount: Int {
        if self.count == 0 {
            return 0
        } else if self.first is Collection { // .Iterator.Element: Collection
            return self.reduce(0) { (res, elem) -> Int in
                res + (elem as! Collection).flatCount // ERROR
            }
        } else {
            return self.reduce(0) { (res,_) in res + 1 }
        }
    }
}

但是，我们不允许将值强制转换为具有关联类型的协议类型。

所以我想使Element类型更明确，例如：

extension Collection {
    var flatCount: Int {
        return Self.flatCountH(self)
    }

    private static final func 
        flatCountH<C: Collection, D>(_ c: C) -> Int 
            where Iterator.Element == D, D: Collection {
        return c.reduce(0) { (res: Int, elem: D) -> Int in 
            (res + elem.flatCount) as Int // Ambiguous type 
        }
    }

    private static final func flatCountH<C: Collection>(_ c: C) -> Int {
        return c.reduce(0) { $0 + $1.flatCount } // Unable to infer closure type
    }
}

但这显然要求过多的类型推断器。

现在，我退后一步，决定停止尝试将所有内容合并为一个扩展：

extension Collection {
    var flatCount: Int {
        // There's no count on Collection, so...
        return self.reduce(0) { (res,_) in res + 1 }
    }
}

extension Collection where Iterator.Element: Collection {
    var flatCount: Int {
        return self.reduce(0) { $0 + $1.flatCount }
    }
}

现在可以 编译了
-是的！-但调度已关闭：$1.flatCount不会绑定到第二个递归版本，但总是绑定到第一个纯版本。也就是说，flatCount仅计算第一个嵌套级别。

是否有一种方法可以处理类型和/或调度以表达此功能？还是我要以一种完全绕行的方式（或两种）进行处理？

旁注：在上一个示例和第一个函数中，我不使用

self.reduce(0) { $0 + 1 }

因为那不能编译；这里，$0是 对 匿名参数！我认为这是不必要的令人惊讶的行为，并向Swift Bugtracker
发布了更改请求。

Answer 1

我不认为目前有可能编写这样的递归扩展，其中基本情况由静态类型的一致性决定。

尽管注意Collection确实有一个count属性要求，但它只是类型IndexDistance（关联类型），而不是Int。因此，如果这
是 可能的，你可以将它表示为：

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 }
    }
}

但是，这会产生一个编译器错误（尽管为什么它不适用于when flatCountis an Int，我也不知道-
它们应该一致地编译还是不编译）。问题是Swift想要静态分配$1.flatCount-因此意味着它只能选择要调用的扩展 之一
（在这种情况下，编译器认为这两个都是同等有效的）。

静态分派在这里起作用的唯一方法是，如果实现是针对Collection调用它们的每种具体类型而专门设计的。在那种情况下，由于编译器会 知道
实现内部的具体类型，从而知道是否Iterator.Element.Iterator.Element : Collection，并相应地进行调度，因此可以解决歧义。

但是，当前的专业化只是一种优化（由于它有可能在不使用内联来抵消这笔额外费用的情况下极大地膨胀代码大小）–因此，不可能保证静态分派在所有情况下都有效。

即使$1.flatCount能够通过例如协议见证表（请参阅有关WWDC的精彩演讲）进行动态调度，基于扩展的类型约束的重载解析也需要在运行时进行（以确定哪个扩展致电）。但是，Swift无法在运行时解决重载（这很昂贵）。相反，重载本身是在编译时解决的，然后动态调度使该重载的
实现 相对于其所调用的值是多态的（即，可以将其调度为该重载的值 自己的 实现）。

不幸的是，我认为可能最接近的方法是为其编写扩展，Array并使用条件类型转换来遍历嵌套数组：

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

尽管注意@MartinR在下面的注释中指出，但as(?/!) [Any]在大多数情况下，转换将创建一个新的数组（由于Swift存储具体类型值和抽象类型值的方式有所不同–请参阅此Q＆A，因此上述实现并非特别如此高效。

一种可能的解决方案是使用“虚拟协议”来声明flatCount属性：

// 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
        }
    }
}

这样避免了O（n）从具体类型元素的数组到抽象类型元素的O（n）转换（相反，给定数组只创建了一个框）。

如果我们对使用阵列的两个实现（在MacBook Pro上的Release版本中）进行粗略的快速基准测试：

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

对于10次重复呼叫flatCount，第一个分机给31.7秒的时间。应用于第二个实施方案的基准相同，产生0.93秒。