Differencebetween Sequencetype and Collectiontype in Swift

What is the difference between SequenceType and CollectionType in swift?

GeneratorType (IteratorProtocol in Swift 3): Generators is something that can give the next element of some sequence, if there is no element it returns nil. Generators encapsulates iteration state and interfaces for iteration over a sequence.

A generator works by providing a single method, namely – next(), which simply returns the next value from the underlying sequence.

Following classes Adopt GeneratorType Protocol:

DictionaryGenerator, EmptyGenerator, more here.

---

SequenceType (Sequence in Swift 3): A Sequence represent a series of values. Sequence is a type that can be iterated with a for...in loop.

Essentially a sequence is a generator factory; something that knows how to make generators for a sequence.

Following classes Adopt SequenceType Protocol:

NSArray, NSDictionary, NSSet and more.

---

CollectionType (Collection in Swift 3): Collection is a SequenceType that can be accessed via subscript and defines a startIndex and endIndex. Collection is a step beyond a sequence; individual elements of a collection can be accessed multiple times.

CollectionType inherits from SequenceType

Following classes Adopt CollectionType Protocol:

Array, Dictionary, Set, Range and more.

---

Form more information you can see this, this, and this

CollectionType Index Tracks Corresponding SequenceType Generator

The answer is 'yes'. The comment in the Swift code defining CollectionType is:

/// The sequence view of the elements is identical to the collection
/// view.  In other words, the following code binds the same series of
/// values to `x` as does `for x in self {}`::
///
///   for i in startIndex..<endIndex {
///     let x = self[i]
///   }

Since for x in self invokes the GeneratorType interface, the orders generated through the two interfaces must be identical. Implementors of new CollectionTypes are, at best it seems, to use this as guidance.

CollectionType Index Behavior

The answer is, from the Apple forums, summarizing: The observed behavior:

• is not a requirement
• should not be relied upon
• for value types, it may be difficult to throw an exception

Why isn't a Swift tuple considered a collection type?

I don't have inside knowledge of the motivations, but I can hopefully present some deeper understanding.

Type Safety

One of the primary goals of Swift is to enforce programming best practices to minimize human mistakes. One of these best practices is to ensure we always use specific types when we know them. In Swift, variables and constants always have explicit types and collections prefer to hold, say Strings, than AnyObjects if you know that it will be storing Strings.

Notably, every collection type in Swift may only hold one type of element. This includes Array, Dictionary, and Set.

Tuples are Compound Types

In Swift, there are two types of types: Named Types and Compound Types. Most types, including collection types, are named. Compound types, on the other hand, contain multiple named types in unique combinations. There are only two Compound Types: Function Types and Tuple Types. Tuple Types are different from collections in that:

• Multiple Named Types can be bundled together in a Tuple Type without using AnyObject.
• Each position can be given a textual label.
• We can always anticipate how many values a tuple will be holding because we declared each position.

For more information, see the Types chapter of The Swift Programming Language.

Tuples Represent Objects

We typically don't think of a collection type as an object in itself. Instead, we think of it as a collection of objects. A tuple's labeled positions and multi-type functionality enable it to function more like an object than any collection. (Almost like a primitive Struct)

For example, you might consider an HTTP error to be a tuple with an error code (Int) and a description (String).

Tuples are often used as primitive approaches to temporary objects, such as returning multiple values from a function. They can be quickly dissected without indexing.

Additionally, each Tuple type has its own explicit type. For example, (Int, Int) is an entirely different type from (Int, Int, Int), which is an entirely different type from (Double, Double, Double).

For more on this, see "Tuples" in the The Basics chapter of The Swift Programming Language.

Tuples are Used in Fundamental Language Syntax

When we think of collection types, we think again of collections. Tuples, however, are used in fundamental places in the language that make Compound Type a more fitting title for them. For example, the Function Type is a Compound Tye that is used anytime you specify a function or closure. It is simply a tuple of parameters and a tuple of return values. Even Void is just a typealias for (), an empty tuple.

Additionally, tuples are in language syntax to temporarily bind values. For example, in a for-in loop you might use a tuple to iterate over a dictionary:

let dict = [1: "A", 2: "B", 3: "C"]

for (_, letter) in dict {

    doSomething()

}

Here we use a tuple to iterate over only the values of the dictionary and ignore the keys.

We can do the same in Switch statements (excerpt from The Swift Programming Language):

let somePoint = (1, 1)
switch somePoint {
case (0, 0):
    print("(0, 0) is at the origin")
case (_, 0):
    print("(\(somePoint.0), 0) is on the x-axis")
case (0, _):
    print("(0, \(somePoint.1)) is on the y-axis")
case (-2...2, -2...2):
    print("(\(somePoint.0), \(somePoint.1)) is inside the box")
default:
    print("(\(somePoint.0), \(somePoint.1)) is outside of the box")
}
// prints "(1, 1) is inside the box”

Because tuples are used in such fundamental places in language syntax, it wouldn't feel right for them to be bundled together with collection types.

SequenceType & CollectionType

One last thing to note is that a fundamental feature of CollectionType, which inherits much of this from SequenceType, is the ability to provide a safe Generator for iteration. For example, a for-in loop is possible because collections define a way to get the next item. Because tuples do not consist of the same types, and have a guaranteed number of items (after declaration), using them on the right of a for-in loop (instead of a traditional collection) would be less than intuitive.

If using it in a for-in loop, something designed to thrive with collections, seems less-than-intuitive for a tuple, than a tuple may deserve a different category.

For details on CollectionType, check out SwiftDoc.org. Note that a Generator providing iteration is required. Iterating a tuple would not be type safe and impose many unnecessary complexities, but making a tuple a collection is an interesting concept. It just might be too fundamental for that.

Circular dependencies between generic types (CollectionType and its Index/Generator, e.g.)

While Airspeed Velocity's answer applies to the most common cases, my question was asking specifically about the special case of generalizing CollectionType indexing in order to be able to share a single Index implementation for all thinkable kinds of binary trees (whose recursive nature makes it necessary to make use of a stack for index-based traversals (at least for trees without a parent pointer)), which requires the Index to be specialized on the actual BinaryTree, not the Element.

The way I solved this problem was to rename MyCollection to MyCollectionStorage, revoke its CollectionType conformity and wrap it with a struct that now takes its place as MyCollection and deals with conforming to CollectionType.

To make things a bit more "real" I will refer to:

• MyCollection<E> as SortedSet<E>
• MyCollectionStorage<E> as BinaryTree<E>
• MyIndex<T> as BinaryTreeIndex<T>

So without further ado:

struct SortedSet<Element>: CollectionType {
    typealias Tree = BinaryTree<Element>
    typealias Index = BinaryTreeIndex<Tree>

    subscript(i: Index) -> Element { … }

    func generate() -> IndexingGenerator<SortedSet> {
        return IndexingGenerator(self)
    }
}

struct BinaryTree<Element>: BinaryTreeType {

}

struct BinaryTreeIndex<BinaryTree: BinaryTreeType>: BidirectionalIndexType {
    func predecessor() -> BinaryTreeIndex { … }
    func successor() -> BinaryTreeIndex { … }
}

This way the dependency graph turns from a directed cyclic graph into a directed acyclic graph.

In Swift, what is a 'progression'?

The first mention I see of "progression" besides the for-in documentation is in the comments of the swift framework where the stride methods are defined.

func stride<T : Strideable>(from start: T, to end: T, by stride: T.Stride) -> StrideTo<T>

Return the sequence of values (start, start + stride, start + stride + stride, ... last) where last is the last value in the progression that is less than end.

func stride<T : Strideable>(from start: T, through end: T, by stride: T.Stride) -> StrideThrough<T>

Return the sequence of values (start, start + stride, start + stride + stride, ... last) where last is the last value in the progression less than or equal to end. Note:: There is no guarantee that end is an element of the sequence.

So in short, "progression" refers to the Strideable protocol similar to how "collection" refers to the CollectionType protocol and the classes and structs that conform to it.

Numeric types (Int, Double, Float, UnsafePointer, Bit, etc...) tend to conform to this protocol so they may be incremented/decremented for for in loops. Full inheritance graph for the Strideable protocol found here.

How to convert code to Swift 4 because of undeclared types?

The thing here is that I wanted Weak Reference Set. But I found another solution. If anyone needs it here it is:

class WeakObject<T: AnyObject>: Equatable, Hashable {
    weak var object: T?
    init(object: T) {
        self.object = object
    }

    var hashValue: Int {
        if var object = object { return UnsafeMutablePointer<T>(&object).hashValue }
        return 0
    }

    static func == (lhs: WeakObject<T>, rhs: WeakObject<T>) -> Bool {
        return lhs.object === rhs.object
    }
}

class WeakObjectSet<T: AnyObject> {
    var objects: Set<WeakObject<T>>

    init() {
        self.objects = Set<WeakObject<T>>([])
    }

    init(objects: [T]) {
        self.objects = Set<WeakObject<T>>(objects.map { WeakObject(object: $0) })
    }

    var allObjects: [T] {
        return objects.compactMap { $0.object }
    }

    func contains(_ object: T) -> Bool {
        return self.objects.contains(WeakObject(object: object))
    }

    func addObject(_ object: T) {
        self.objects.formUnion([WeakObject(object: object)])
    }

    func addObjects(_ objects: [T]) {
        self.objects.formUnion(objects.map { WeakObject(object: $0) })
    }
}

Define a Swift protocol which requires a specific type of sequence

There are two sides to this problem:

• Accepting an arbitrary sequence of ints

• Returning or storing an arbitrary sequence of ints

In the first case, the answer is to use generics. For example:

func iterateOverInts<SeqInt: SequenceType where SeqInt.Generator.Element == Int>(xs: SeqInt) {
    for x in xs {
        print(x)
    }
}

In the second case, you need a type-eraser. A type-eraser is a wrapper that hides the actual type of some underlying implementation and presents only the interface. Swift has several of them in stdlib, mostly prefixed with the word Any. In this case you want AnySequence.

func doubles(xs: [Int]) -> AnySequence<Int> {
    return AnySequence( xs.lazy.map { $0 * 2 } )
}

For more on AnySequence and type-erasers in general, see A Little Respect for AnySequence.

If you need it in protocol form (usually you don't; you just need to use a generic as in iterateOverInts), the type eraser is also the tool there:

protocol HasSequenceOfInts {
    var seq : AnySequence<Int> { get }
}

But seq must return AnySequence<Int>. It can't return [Int].

There is one more layer deeper you can take this, but sometimes it creates more trouble than it solves. You could define:

protocol HasSequenceOfInts {
    typealias SeqInt : IntegerType
    var seq: SeqInt { get }
}

But now HasSequenceOfInts has a typealias with all the limitations that implies. SeqInt could be any kind of IntegerType (not just Int), so looks just like a constrained SequenceType, and will generally need its own type eraser. So occasionally this technique is useful, but in your specific case it just gets you basically back where you started. You can't constrain SeqInt to Int here. It has to be to a protocol (of course you could invent a protocol and make Int the only conforming type, but that doesn't change much).

BTW, regarding type-erasers, as you can probably see they're very mechanical. They're just a box that forwards to something else. That suggests that in the future the compiler will be able to auto-generate these type-erasers for us. The compiler has fixed other boxing problems for us over time. For instance, you used to have to create a Box class to hold enums that had generic associated values. Now that's done semi-automatically with indirect. We could imagine a similar mechanism being added to automatically create AnySequence when it's required by the compiler. So I don't think this is a deep "Swift's design doesn't allow it." I think it's just "the Swift compiler doesn't handle it yet."

---

Related Topics