How do you contstrain types within tuples?

Question

Created Jun ’15

Replies 4

Boosts 0

Participants 3

With Swift 2, you can write permute() as a method on Dictionary (assume that all keys and values are unique):

extension Dictionary where Value: Hashable {
    func permute() -> [Value: Key] {
        var permuted = [Value: Key]()
        for (key, value) in self {
            permuted[value] = key
        }
        return permuted
    }
}

By "permute", I mean specifically that keys become the values and vice versa.

But what if you wanted to write this more generically so that any sequence of (key, value) tuples in which the values were hashable could be converted to a permuted dictionary. Is it possible?

I'm thinking something like:

extension SequenceType where Generator.Element: (Any, Hashable) {
    func permute() -> [Generator.Element.1: Generator.Element.0] {
        ...
    }
}

Or perhaps:

extension SequenceType<Key, Value: Hashable> where Generator.Element == (Key, Value) {
    func permute() -> [Value: Key] {
        ...
    }
}

But these are both nonstarters. In the first version, it's not clear what "Generator.Element: (Any, Hashable)" would mean, and the compiler doesn't accept it anyway. It also doesn't understand the notation Generator.Element.1, so apparently it's not possible to look inside tuple types in the way that you can with actual tuples.

In the second version, the compiler complains "expected '>' to complete generic argument list", by which I think it means, "hey, you can't treat Sequence as a generic type to be specialized, since it isn't generic to begin with". (It doesn't matter if you move the > to the end.)

Can generics and tuples interact?

Boost

Answer 1

Jens OP

Jun ’15

Have a look at eg EnumerateGenerator in the standard library:

/// The `GeneratorType` for `EnumerateSequence`.  `EnumerateGenerator`
/// wraps a `Base` `GeneratorType` and yields successive `Int` values,
/// starting at zero, along with the elements of the underlying
/// `Base`:
///
///     var g = EnumerateGenerator(["foo", "bar"].generate())
///     g.next() // (0, "foo")
///     g.next() // (1, "bar")
///     g.next() // nil
///
/// - Note: Idiomatic usage is to call `enumerate` instead of
///   constructing an `EnumerateGenerator` directly.
struct EnumerateGenerator<Base : GeneratorType> : GeneratorType, SequenceType {

    /// The type of element returned by `next()`.
    typealias Element = (index: Int, element: Base.Element)

    /// Construct from a `Base` generator.
    init(_ base: Base)

    /// Advance to the next element and return it, or `nil` if no next
    /// element exists.
    ///
    /// - Requires: No preceding call to `self.next()` has returned `nil`.
    mutating func next() -> (index: Int, element: Base.Element)?

    /// A type whose instances can produce the elements of this
    /// sequence, in order.
    typealias Generator = EnumerateGenerator<Base>

    /// `EnumerateGenerator` is also a `SequenceType`, so it
    /// `generate`s a copy of itself.
    func generate() -> EnumerateGenerator<Base>
}

Perhaps you can do something similar but a PermuteGenerator (or perhaps PairvertGenerator would be a better name (pairs, inverted, pairvert ...) ehrm).

And then I'm not sure if something like this (but working) would make it possible to use that Generator of yours:

struct PairvertSequence<T, U, Base : SequenceType where Base.Generator.Element == (T, U)> : SequenceType {
    typealias First = T
    typealias Second = U
    private let base: Base
    init(_ base: Base) { self.base = base }
    func generate() -> PairvertGenerator<Base.Generator> {
        return PairvertGenerator(base.generate())
    }
}

extension SequenceType {
    func pairvert<T: Hashable, U: Hashable where Generator.Element == (T, U)>() -> PairvertSequence<T, U, Self> {
        return PairvertSequence.init(self)
    }
}

But probably this is only moving the problem to not being able to constrain the Element associated type of the base SequenceType to being pairs of Hashable ...

0

Answer 2

ObjectHub OP

Jun ’15

In general, tuples can interact with generics, but in a protocol extension, we would either need a protocol they implement that could be used as a type constraint, or we would have to be able to introduce new type variables. AFAIK, none of the two options will currently work. So, this is still a case where you need to use generic functions instead:

func invert<K,V: Hashable,S: SequenceType where S.Generator.Element == (K, V)>(seq: S) -> [V : K] {
  var inverted = [V : K]()
  for (key, value) in seq {
    inverted[value] = key
  }
  return inverted
}

0

Answer 3

GSnyder OP

Jun ’15

Yeah, "pairverted" is a pretty good description of my code... :-)

Moving the constraints to the method signature seems promising. I'm not sure I understand the function of the custom sequence and generator, though - are they there just to ensure that the types are actually used in the signature?

This seems like it should work on its own:

extension SequenceType {
    func pairvert<Key, Value: Hashable where Generator.Element == (Key, Value)>() -> [Value: Key] {
        var pairverted = [Value: Key]()
        for (key, value) in self {   // Error: 'Self.Generator.Element' is not convertible to '(Self, Self)'
            pairverted[value] = key
        }
        return pairverted
    }
}

And it mostly seems to, except for the indicated error, which I don't understand. Hard to say for sure, though, since Swift still seems to have error shadowing issues.

The version below with an explicit cast just crashes the compiler. I filed a bug.

// Crashes compiler
extension SequenceType {
    func pairvert<Key, Value: Hashable where Generator.Element == (Key, Value)>() -> [Value: Key] {
        var pairverted = [Value: Key]()
        for item in self {
            let (key, value) = item as! (Key, Value)
            pairverted[value] = key
        }
        return pairverted
    }
}

0

Answer 4

GSnyder OP

Jun ’15

Is it definitely the case that new type variables can't be introduced in an extension clause? That provides some clarity.

0