Оборачиваем последовательности в Swift

в 12:45, , рубрики: iOS, ios development, ios programming, iOS разработка, swift, Блог компании OTUS. Онлайн-образование, разработка под iOS

Всем привет. Сегодня хотим поделиться переводом подготовленным в преддверии запуска курса «iOS Разработчик. Продвинутый курс». Поехали!

Оборачиваем последовательности в Swift - 1

Одним из основных преимуществ протокольно-ориентированного дизайна Swift является то, что он позволяет нам писать общий код, который совместим с широким диапазоном типов, а не специально реализован для каждого. Особенно, если такой общий код предназначен для одного из протоколов, который можно найти в стандартной библиотеке, что позволит использовать его как со встроенными типами, так и с пользовательскими.

Примером такого протокола является Sequence (последовательность), который принят всеми типами стандартной библиотеки, которые могут быть итерированы, такими как Array, Dictionary, Set и многими другими. На этой неделе давайте рассмотрим, как мы можем обернуть Sequence в универсальные контейнеры, что позволит нам инкапсулировать различные алгоритмы в основе простых в использовании API.

Искусство быть ленивым

Довольно легко прийти к заблуждению, думая, что все последовательности похожи на Array, поскольку все элементы мгновенно загружаются в память при создании последовательности. Поскольку единственным требованием протокола Sequence является то, что приемники должны иметь возможность итерации, мы не можем делать какие-либо предположения о том, как элементы неизвестной последовательности загружаются или хранятся.
Например, как мы рассмотрели в «Последовательности Swift: искусство быть ленивым», последовательности могут иногда загружать свои элементы лениво — либо по соображениям производительности, либо потому, что не гарантируется, что вся последовательность может поместиться в памяти. Вот несколько примеров таких последовательностей:

//Последовательность записей базы данных, в которой страницы записей загружаются по ходу итерирования по ним, чтобы избежать загрузки всех результатов поиска в память для их перебора.

let records = database.records(matching: searchQuery)

//Последовательность подпапок в папке на диске, в которой каждая папка открывается только тогда, когда до нее дошла очередь итерации.

let folders = folder.subfolders

//Последовательность узлов в графе, которая  ленива в плане того, чтобы нам не нужно было оценивать весь граф в начале каждой итерации.
let nodes = node.children

Так как все вышеперечисленные последовательности по какой-либо причине являются ленивыми, мы не хотели бы принудительно вводить их в массив, например, вызывая Array(folder.subfolders). Но мы все еще можем захотеть модифицировать и работать с ними разными способами, поэтому давайте рассмотрим, как мы можем сделать это, создав тип обертки последовательности (sequence wrapper).

Создание основы

Давайте начнем с создания базового типа, который мы сможем использовать для создания всевозможных удобных API поверх любой последовательности. Мы назовем его WrappedSequence, и он будет универсальным типом, содержащим как тип последовательности, которую мы оборачиваем, так и тип элемента, который мы хотим, чтобы наша новая последовательность создавала.
Основной особенностью нашей обертки будет ее IteratorFunction, которая позволит нам взять под контроль перебор базовой последовательности — изменяя Iterator, используемый для каждой итерации:

struct WrappedSequence<Wrapped: Sequence, Element>: Sequence {
    typealias IteratorFunction = (inout Wrapped.Iterator) -> Element?

    private let wrapped: Wrapped
    private let iterator: IteratorFunction

    init(wrapping wrapped: Wrapped,
         iterator: @escaping IteratorFunction) {
        self.wrapped = wrapped
        self.iterator = iterator
    }

    func makeIterator() -> AnyIterator<Element> {
        var wrappedIterator = wrapped.makeIterator()
        return AnyIterator { self.iterator(&wrappedIterator) }
    }
}

Как вы можете видеть выше, Sequence использует паттерн фабрики чтобы каждая последовательность создала новый экземпляр итератора для каждой итерации — с помощью метода makeIterator().

Выше мы используем тип AnyIterator стандартной библиотеки, который является итератором стирания типа, который может использовать любую базовую реализацию IteratorProtocol для получения значений Element. В нашем случае мы создадим элемент, вызвав нашу IteratorFunction, передав в качестве аргумента собственный итератор обернутой последовательности, и, поскольку этот аргумент помечен как inout, мы можем изменить базовый итератор на месте внутри нашей функции.

Поскольку WrappedSequence также является последовательностью, мы можем использовать с ней все связанные с последовательностями функциональные возможности стандартной библиотеки, такие как итерация по ней или преобразование ее значений с помощью map:

let folderNames = WrappedSequence(wrapping: folders) { iterator in
    return iterator.next()?.name
}

for name in folderNames {
    ...
}

let uppercasedNames = folderNames.map { $0.uppercased() }

Теперь давайте начнем работу с нашей новой WrappedSequence!

Префиксы и суффиксы

При работе с последовательностями очень часто возникает желание вставить префикс или суффикс в последовательность, с которой мы работаем — но разве не было бы замечательно, если бы мы могли сделать это без изменения основной последовательности? Это может привести к повышению производительности и позволит нам добавлять префиксы и суффиксы в любую последовательность, а не только в общие типы, такие как Array.

Используя WrappedSequence, мы можем сделать это довольно легко. Все, что нам нужно сделать, это расширить Sequence с помощью метода, который создает обернутую последовательность из массива элементов для вставки в качестве префикса. Затем, когда мы выполняем итерацию, мы начинаем с итерации по всем префиксным элементам прежде, чем продолжить с базовой последовательностью — вот так:

extension Sequence {
    func prefixed(
        with prefixElements: Element...
    ) -> WrappedSequence<Self, Element> {
        var prefixIndex = 0

        return WrappedSequence(wrapping: self) { iterator in
// Если у нас все еще есть префиксные элементы, которые нужно обслуживать, то возвращаем следующий, увеличивая наш индекс:
            guard prefixIndex >= prefixElements.count else {
                let element = prefixElements[prefixIndex]
                prefixIndex += 1
                return element
            }

            // В противном случае возвращаем элемент из собственного итератора нашей базовой последовательности:
            return iterator.next()
        }
    }
}

Выше мы используем параметр с переменным количеством аргументов (добавляя… к его типу), чтобы разрешить передачу одного или нескольких элементов одному и тому же методу.
Точно так же мы можем создать метод, который добавляет заданный набор суффиксов в конец последовательности — сначала выполняя собственную итерацию базовой последовательности, а затем итерируя по суффиксированным элементам:

extension Sequence {
    func suffixed(
        with suffixElements: Element...
    ) -> WrappedSequence<Self, Element> {
        var suffixIndex = 0

        return WrappedSequence(wrapping: self) { iterator in
            guard let next = iterator.next() else {
                // Это наше условие выхода, в котором мы возвращаем nil после завершения основной и суффиксной итерации:
                guard suffixIndex < suffixElements.count else {
                    return nil
                }

                let element = suffixElements[suffixIndex]
                suffixIndex += 1
                return element
            }

            return next
        }
    }
}

Имея два вышеупомянутых метода, мы можем теперь добавлять префиксы и суффиксы к любой последовательности, к которой мы хотим. Вот несколько примеров того, как могут использоваться наши новые API:

// Включение родительской папки в итерацию подпапки:
let allFolders = rootFolder.subfolders.prefixed(with: rootFolder)

//Добавление черновика в качестве суффикса к последовательности сообщений:
let messages = inbox.messages.suffixed(with: composer.message)

//Заключение строки в скобки перед итерацией по ней, без необходимости создавать новые экземпляры строк:
let characters = code.prefixed(with: "{").suffixed(with: "}")

Хотя все вышеприведенные примеры могут быть реализованы с использованием конкретных типов (таких как Array и String), преимущество использования нашего типа WrappedSequence заключается в том, что все можно сделать лениво — мы не выполняем никаких мутаций и не оцениваем какие-либо последовательности, чтобы добавить наши префиксы или суффиксы — что может быть действительно полезно в ситуациях, критичных к производительности, или при работе с большими наборами данных.

Cегментация

Далее, давайте рассмотрим, как мы можем обернуть последовательности, чтобы создать их сегментированные версии. В определенных итерациях недостаточно знать, что представляет собой текущий элемент — нам также может понадобиться информация о следующем и предыдущем элементах.
При работе с индексированными последовательностями мы часто можем достичь этого, используя API enumerated(), который также использует обертку последовательности, чтобы предоставить нам доступ как к текущему элементу, так и к его индексу:

for (index, current) in list.items.enumerated() {
    let previous = (index > 0) ? list.items[index - 1] : nil
    let next = (index < list.items.count - 1) ? list.items[index + 1] : nil
    ...
}

Тем не менее, вышеупомянутая методика не только довольно многословна с точки зрения вызова, она также снова полагается на использование массивов — или, по крайней мере, некоторую форму последовательности, которая дает нам произвольный доступ к его элементам, — что многие последовательности, особенно ленивые, не приветствуют.
Вместо этого давайте еще раз используем наш WrappedSequence — чтобы создать обертку последовательности, которая лениво предоставляет сегментированные представления в свою базовую последовательность, отслеживая предыдущие и текущие элементы и обновляя их по мере продолжения перебора:

extension Sequence {
    typealias Segment = (
        previous: Element?,
        current: Element,
        next: Element?
    )

    var segmented: WrappedSequence<Self, Segment> {
        var previous: Element?
        var current: Element?
        var endReached = false

        return WrappedSequence(wrapping: self) { iterator in
            // Здесь наше условие выхода состоит либо в том, что мы достигли конца базовой последовательности, либо в том, что первый текущий элемент не может быть создан, потому что последовательность была пустой.
            guard !endReached,
                  let element = current ?? iterator.next() else {
                return nil
            }

            let next = iterator.next()
            let segment = (previous, element, next)

// Прежде чем вернуть новый сегмент, мы обновляем состояние итерации, чтобы быть готовыми к следующему элементу:
            previous = element
            current = next
            endReached = (next == nil)

            return segment
        }
    }
}

Теперь мы можем использовать приведенный выше API для создания сегментированной версии любой последовательности всякий раз, когда нам нужно либо смотреть вперед, либо назад при выполнении перебора. Например, вот как мы можем использовать сегментацию, чтобы можно было легко определить, когда мы достигли конца списка:

for segment in list.items.segmented {
    addTopBorder()
    addView(for: segment.current)

    if segment.next == nil {
// Мы достигли конца, время добавить нижнюю границу
        addBottomBorder()
    }
}
```swift
Сегментированные последовательности также отлично подходят для визуализации карт, путей или графиков. Здесь мы используем сегменты, чтобы иметь возможность вычислять и отображать направления входа и выхода для каждого узла в пути:
```swift
for segment in path.nodes.segmented {
    let directions = (
        enter: segment.previous?.direction(to: segment.current),
        exit: segment.next.map(segment.current.direction)
    )

    let nodeView = NodeView(directions: directions)
    nodeView.center = segment.current.position.cgPoint
    view.addSubview(nodeView)
}

Теперь мы начинаем видеть истинную силу оборачивания последовательностей — в том, что они позволяют нам скрывать все более сложные алгоритмы за действительно простым API. Все, что нужно вызывающей стороне для сегментирования последовательности, — это доступ к свойству segmented в любой Sequence, а наша базовая реализация позаботится об остальном.

Рекурсия

Наконец, давайте рассмотрим, как даже рекурсивные итерации могут быть смоделированы с помощью оберток последовательностей. Допустим, мы хотели предоставить простой способ рекурсивной итерации по иерархии значений, в которой каждый элемент в иерархии содержит последовательность дочерних элементов. Это может быть довольно сложно сделать правильно, поэтому было бы здорово, если бы мы могли использовать одну реализацию для выполнения всех таких итераций в нашей кодовой базе.
Используя WrappedSequence, мы можем добиться этого, расширив Sequence методом, который использует такое же ограничение универсального типа, чтобы гарантировать, что каждый элемент может предоставить вложенную последовательность, которая имеет тот же тип итератора, что и наш исходный. Чтобы иметь возможность динамического доступа к каждой вложенной последовательности, мы также попросим вызывающую сторону указать KeyPath для свойства, которое следует использовать для рекурсии, что даст нам реализацию, которая выглядит следующим образом:

extension Sequence {
    func recursive<S: Sequence>(
        for keyPath: KeyPath<Element, S>
    ) -> WrappedSequence<Self, Element> where S.Iterator == Iterator {
        var parentIterators = [Iterator]()

        func moveUp() -> (iterator: Iterator, element: Element)? {
            guard !parentIterators.isEmpty else {
                return nil
            }

            var iterator = parentIterators.removeLast()

            guard let element = iterator.next() else {
                // Мы будем продолжать продвигать нашу цепочку родителей до тех пор, пока не найдем того, кого можно продвинуть до следующего элемента:
                return moveUp()
            }

            return (iterator, element)
        }

        return WrappedSequence(wrapping: self) { iterator in
            // Мы либо используем следующий элемент текущего итератора, либо перемещаемся по цепочке родительских итераторов, чтобы получить следующий элемент в последовательности:
            let element = iterator.next() ?? {
                return moveUp().map {
                    iterator = $0
                    return $1
                }
            }()

// Наша рекурсия выполняется с приоритетом в глубину, что означает, что мы будем погружаться как можно глубже в последовательности, прежде чем перейти к следующему элементу на уровне выше.
            if let nested = element?[keyPath: keyPath].makeIterator() {
                let parent = iterator
                parentIterators.append(parent)
                iterator = nested
            }

            return element
        }
    }
}

Используя вышенаписанное, мы теперь можем рекурсивно выполнять итерацию по любой последовательности, независимо от того, как она построена внутри, и без необходимости загружать всю иерархию заранее. Например, вот как мы могли бы использовать этот новый API для рекурсивной итерации по иерархии папок:

let allFolders = folder.subfolders.recursive(for: .subfolders)

for folder in allFolders {
    try loadContent(from: folder)
}

Мы также можем использовать его для итерации по всем узлам дерева или для рекурсивного обхода набора записей базы данных — например, для перечисления всех групп пользователей в организации:

let allNodes = tree.recursive(for: .children)
let allGroups = database.groups.recusive(for: .subgroups)

Одна вещь, с которой мы должны быть осторожны, когда дело доходит до рекурсивных итераций, это не допускать циклические ссылки — когда определенный путь возвращает нас к элементу, с которым мы уже столкнулись — что приведет нас к бесконечному циклу.
Один из способов исправить это — отслеживать все встречающиеся элементы (но это может быть проблематично с точки зрения памяти), гарантировать отсутствие циклических ссылок в нашем наборе данных или обрабатывать такие случаи каждый раз со стороны вызова (с помощью break, continue или return для завершения любых циклических итераций).

Заключение

Sequence — это один из самых простых протоколов в стандартной библиотеке — он требует только один метод — но он по-прежнему один из самых мощных, особенно когда речь идет о том, сколько функциональности мы можем создать на его основе. Так же, как стандартная библиотека содержит последовательности оберток для таких вещей, как перечисления, мы также можем создавать свои собственные обертки — которые позволяют нам скрывать расширенные функциональные возможности за действительно простыми API.

Хотя абстракции всегда имеют свою цену, и важно учитывать, когда стоит (и, возможно, более важно — когда не стоит) вводить их, если мы можем построить наши абстракции прямо поверх того, что обеспечивает стандартная библиотека — используя те же соглашения — тогда эти абстракции обычно имеют больше шансов выдержать испытание временем.

Автор: nmonax

Источник


* - обязательные к заполнению поля