使用依赖于元素类型的递归属性/方法扩展集合 [英] Extending Collection with a recursive property/method that depends on the element type
问题描述
在这个问题的上下文中，我想如何可以实现一个属性或方法来计算所有集合中的嵌套级别.
In the context of this question, I though about how one could implement a property or method that counts across all nesting levels in collections.
直觉上，这应该是可行的:
Intuitively, something this should work:
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 }
}
}
}
但是，我们不允许将值转换为具有关联类型的协议类型.
However, we are not allowed to cast values to protocol types that have associated types.
所以我想让 Element 类型更明确，就像这样:
So I thought to make the Element type more explicit, like so:
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
}
}
但这显然对类型推断器要求过高.
But this is apparently asking too much of the type inferrer.
现在我退后了一步，决定不再试图将所有内容都集中在一个扩展中:
Now I took a step back and decided to stop trying to wrench everything into one extension:
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 只计算第一层嵌套.
Now this compiles -- yay! -- but the dispatching is off: $1.flatCount does not bind to the second, recursive version, but always to the first, plain version. That is, flatCount only counts the first nesting level.
有没有办法以一种表达此功能的方式来处理类型和/或调度?还是我会以一种完全迂回的方式(或两种方式)进行处理?
Is there a way to juggle types and/or dispatching in a way to express this function? Or am I going about it in a completely roundabout way (or two)?
旁注:在最后一个例子和第一个函数中，我没有使用
Side note: in the last example and in the first function, I don't use
self.reduce(0) { $0 + 1 }
因为不能编译；这里，$0 是两个匿名参数的pair！我认为这是不必要的令人惊讶的行为，并向 Swift 错误跟踪器发布了更改请求.
because that does not compile; here, $0 is the pair of both anonymous parameters! I think that this is needlessly surprising behaviour and posted a change request to the Swift bugtracker.
推荐答案
我认为目前不可能编写这样的递归扩展，其中基本情况由静态类型的一致性决定.
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.
>
尽管请注意 Collection 确实有 count 属性要求，但它只是类型 IndexDistance(关联类型)，而不是 Int.因此，如果这 可能，您可以将其表示为:
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 }
}
}
然而，这会产生一个编译器错误(尽管为什么当 flatCount 是一个 Int 时它不会，我不知道——它们要么一致地编译，要么不编译).问题是 Swift 想要静态分派 $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).
静态调度在这里工作的唯一方法是，如果实现是专门针对它们被调用的每种具体类型的 Collection.在这种情况下，歧义将被解决，因为编译器将知道实现中的具体类型，从而知道是否Iterator.Element.Iterator.Element : Collection，以及相应地派遣.
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.
即使 $1.flatCount 能够动态调度，例如通过 协议见证表(参见 这个伟大的 WWDC 谈话)，基于扩展的类型约束的重载解析需要在运行时发生(以确定要调用的扩展).但是，Swift 不会在运行时解决重载(这会很昂贵).相反，重载本身在编译时解析，然后动态分派允许该重载的实现相对于它被调用的值是多态的(即它可以分派到该值的 em>自己实现该重载).
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).
不幸的是，我认为您可能最接近的是为 Array 编写扩展并使用条件类型转换以遍历嵌套数组:
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
尽管请注意 @MartinR 在下面的评论中指出，转换 as(?/!) [Any] 在大多数情况下会创建一个新数组(由于 Swift 存储具体数据的方式不同)类型化和抽象类型化值——参见这个问答)，上面的实现不是特别有效.
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.
对此的一个潜在解决方案是使用虚拟协议"来声明 flatCount 属性:
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
}
}
}
这避免了从具体类型元素数组到抽象类型元素的 O(n) 转换(相反，只为给定数组创建一个框).
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).
如果我们对数组的两个实现(在 MacBook Pro 上的 Release 版本中)进行粗略的快速基准测试:
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)
对于 flatCount 的 10 次重复调用，第一个扩展的时间为 31.7 秒.应用于第二个实现的相同基准产生 0.93 秒.
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.
这篇关于使用依赖于元素类型的递归属性/方法扩展集合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
