Расширение 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.

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 хочет статически отправить $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 хранит конкретные типизированные и абстрактно-типизированные значения - см. этот раздел вопросов и ответов), что делает приведенную выше реализацию не особенно эффективной.

Одним из возможных решений этой проблемы является использование "фиктивного протокола" для объявления 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) с массивом:

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

За 10 повторных звонков flatCount первое расширение дает время 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 все равно будет отправлять статически здесь, соответственно. отправка таблицы игнорирует ограничение типа на C.Iterator.Element, И это не возможно объявить вспомогательные функции dynamic потому что у них есть ограничения типа - тоже плохо.