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

Question

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

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

所以我想使 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 不绑定(bind)到第二个递归版本，但始终绑定(bind)到第一个普通版本。也就是说，flatCount 只计算第一个嵌套级别。

有没有一种方法可以兼顾类型和/或以表达此功能的方式进行调度？还是我要以一种(或两种)完全迂回的方式来解决这个问题？

---

旁注:在最后一个例子和第一个函数中，我没有使用

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

因为那不编译；在这里，$0 是两个匿名参数的对!我认为这是不必要的令人惊讶的行为并发布了 a change request到 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 }
    }
}

然而，这会产生一个编译器错误(尽管为什么当 flatCount 是一个 Int 时它不会，我不知道——它们应该一致地编译或不编译)。问题是 Swift 想要静态分派(dispatch) $1.flatCount——因此意味着它只能选择 一个 的扩展来调用(在这种情况下，编译器认为两者都同样有效)。

静态分派(dispatch)在这里起作用的唯一方法是，如果实现是专门针对调用它们的每种具体类型的Collection。在那种情况下，歧义将得到解决，因为编译器将知道实现中的具体类型，从而知道 Iterator.Element.Iterator.Element : Collection 和相应地调度。

然而，目前特化只是一种优化(由于它有可能在不使用内联来抵消这种额外成本的情况下极大地膨胀代码大小)——因此无法保证静态分派(dispatch)适用于所有情况。

即使 $1.flatCount 能够被动态调度，例如通过 protocol witness table(请参阅上面的 this great WWDC talk)，基于扩展类型约束的重载解析也需要发生在运行时(以确定调用哪个扩展)。但是，Swift 不会在运行时解决重载(这会很昂贵)。相反，重载本身在编译时被解析，然后动态调度允许该重载的实现相对于它被调用的值是多态的(即它可以调度到一个值的< em>拥有 该重载的实现)。

---

不幸的是，我认为您最接近的可能是为 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

虽然请注意下面注释中的 as @MartinR points out，转换 as(?/!) [Any] 在大多数情况下会创建一个新数组(由于 Swift 存储具体类型的方式不同)和抽象类型值——参见 this Q&A )，使得上述实现不是特别有效。

一个可能的解决方案是使用“虚拟协议(protocol)”来声明 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) 转换(相反，只为给定数组创建一个框)。

如果我们对阵列的两种实现(在 MacBook Pro 上的 Release 版本中)进行粗略的快速基准测试:

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

对于 flatCount 的 10 次重复调用，第一个扩展给出的时间为 31.7 秒。应用于第二个实现的相同基准产生 0.93 秒。