使用取决于元素类型的递归 property/method 扩展 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 }
        }
    }
}

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

所以我想使元素类型更明确，像这样：

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) { [=12=] + .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) { [=13=] + .flatCount }
    }
}

现在编译 -- 耶！ -- 但调度已关闭：.flatCount 不绑定到第二个递归版本，但始终绑定到第一个普通版本。也就是说，flatCount只计算第一层嵌套。

有没有办法兼顾类型 and/or 调度以表达此功能？还是我要以一种完全迂回的方式（或两种）来解决这个问题？

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

self.reduce(0) { [=14=] + 1 }

因为那不编译；这里，[=17=] 是两个匿名参数的对！我认为这是不必要的令人惊讶的行为，并将 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
        //  .flatCount is ambiguous)
        return self.reduce(0) { [=10=] + .flatCount }
    }
}

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

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

但是，目前专业化只是一种优化（因为它有可能在不使用内联来抵消这种额外成本的情况下大幅增加代码大小）——因此无法保证静态分派会适用于所有情况。

即使 .flatCount 能够被动态调度，例如通过 protocol witness table (see this great WWDC talk 在它们上），基于扩展类型约束的重载解析也需要在运行时进行（以确定呼叫哪个分机）。但是，Swift 不会在运行时解决重载（这会很昂贵）。相反，重载本身在编译时被解析，然后动态分派允许该重载的实现相对于它被调用的值是多态的（即它可以分派到该重载的 own 实现）。

不幸的是，我认为您最接近的可能是为 Array 编写扩展并使用条件 type-casting 以遍历嵌套数组：

extension Array {
    var flatCount: Int {

        var iterator = makeIterator()

        if let first = iterator.next() as? [Any] {
            // must be an array of arrays – otherwise  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) { [=11=] + ( as! [Any]).flatCount }
        } else {
            return count
        }
    }
}

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

print(arr.flatCount) // 9

尽管注意如 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 )，使得上述实现不是特别有效。

一个可能的解决方案是使用 'dummy 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) { [=12=] + ( as! _Array).flatCount }
        } else {
            return count
        }
    }
}

这避免了从 concrete-typed 元素数组到 abstract-typed 元素的 O(n) 转换（相反，只为给定数组创建一个框）。

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

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

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

Answer 2

这感觉很接近：

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

fileprivate class CollectionHelper {
    func flatCountH<C: Collection>(_ c: C) -> Int where C.Iterator.Element: Collection {
        typealias E = C.Iterator.Element
        return c.reduce(0) { (res: Int, elem: E) -> Int in
            res + self.flatCountH(elem)
        }
    }

    func flatCountH<C: Collection>(_ c: C) -> Int {
        return c.reduce(0) { (count, _) in count + 1 }
    }
}

不幸的是，Swift 仍然会在此处静态调度。 table 调度忽略了 C.Iterator.Element 上的类型约束。并且不可能声明辅助函数dynamic，因为它们有类型限制——太糟糕了。

使用取决于元素类型的递归 property/method 扩展 Collection

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

generics

collections

recursion

swift

swift-extensions