Is it possible to create a cartesian product function with parameter packs?

Using Swift
,
1

The shape of the function would be

func variableCartesianProduct<each T>(input: repeat [each T]) -> [(repeat each T)]

The use case here is as input for parameterized tests. I'd like to take lists of possible inputs and produce all combinations of those lists. I've made a few attempts, but I think there are some missing pieces. You could build up recursive tuples, but I can't figure out a way to flatten them. ie you can't do a transformation of an arbitrary tuple shaped like ((String, Int), Float) to a tuple shaped like (String, Int, Float). You could track a list of indices to combine, but there's no way to do something like

// Should produce a tuple
(repeat each input).enumerate().map { index, list in list[indices[index]] }

as far as I can tell. In other words, you can't alter the function call based on the parameter pack index.

I'd love some help on this if it's possible! Thanks!

3 Likes
3

This is a nice brain challenge.

I think there must be more elegant solutions, but at least you can use type erasure:

func cartesian(_ columns: [[Any]]) -> [[Any]] {
    // implement core logic here,
    // it should not be hard when we don't care the elements' static types
    fatalError("await to be implemented")
}

// the routine to re-inflate with static type info
func transform<each T>(_ array: [Any], as: repeat (each T).Type) -> (repeat each T) {
    var index = 0
    func extract<R>(_ type: R.Type) -> R {
        defer {
            index += 1
        }
        return array[index] as! R
    }

    return (repeat extract((each T).self))
}

func variableCartesianProduct<each T>(_ input: repeat [each T]) -> [(repeat each T)] {
    var allColumns: [[Any]] = []
    for column in repeat each input {
        allColumns.append(column)
    }

    let result = cartesian(allColumns)
    return result.map {
        transform($0, as: repeat (each T).self)
    }
}
1 Like
4

I believe it's possible using overloads — RegexComponentBuilder does this for tuples with up to 10 elements, using 100 overloads of buildPartialBlock.

1 Like
5

Interesting! In the proposal doc they even call out variadic generics for a future improvement of this, so maybe that had a plan that would allow flattening.

Before Swift supports variadic generics, buildPartialBlock(accumulated:next:) must be overloaded to support concatenating regexes of supported capture quantities (arities). It is overloaded up to arity^2 times to account for all possible pairs of regexes that make up 10 captures.

In the initial version of the DSL, we plan to support regexes with up to 10 captures, as 10 captures are sufficient for most use cases. These overloads can be superseded by variadic versions of buildPartialBlock(first:) and buildPartialBlock(accumulated:next:) in a future release.

6

There might be some clues in here how this might be possible:

1 Like
7

Wait you can totally flatten.

public func flatten<each T, U>(_ left: (repeat each T), _ right: U) -> (repeat each T, U) {
    return (repeat each left, right)
}
8

Oh cool you had the exact same use case too. Thanks for the pointer!

1 Like
9

Found a compiler crash. I'll have to come back to this later.

10
2 Likes
11

Gave it a try as well.

func cartesianProduct<each T>(_ input: repeat [each T]) -> [(repeat each T)] {
  for array in repeat each input {
    guard !array.isEmpty else {
      return []
    }
  }
  var size = 1
  func makeRepeated<A>(_ array: [A]) -> RepeatEachElementSequence<[A]> {
    defer {
      size *= array.count
    }
    return RepeatEachElementSequence(base: array, count: size)
  }
  var iters = (repeat makeRepeated(each input).makeIterator())
  func nonMutatingNext<I: IteratorProtocol>(_ iter: I) -> (element: I.Element?, copy: I) {
    var copy = iter
    return (copy.next(), copy)
  }
  let res = (0..<size).map { _ in
    let x = (repeat nonMutatingNext(each iters))
    iters = (repeat (each x).copy)
    return (repeat (each x).element!)
  }
  return res
}

struct RepeatEachElementSequence<Base: Sequence>: Sequence {
  struct Iterator: IteratorProtocol {
    var base: Base
    var count: Int
    private var baseIterator: Base.Iterator
    private var i = 0
    private var currentElement: Base.Element?

    init(base: Base, count: Int) {
      self.base = base
      self.count = count
      baseIterator = base.makeIterator()
    }

    mutating func next() -> Base.Element? {
      if i % count == 0 {
        currentElement = baseIterator.next()
      }
      if currentElement == nil {
        baseIterator = base.makeIterator()
        currentElement = baseIterator.next()
      }
      i += 1
      return currentElement
    }
  }

  var base: Base
  var count: Int

  init(base: Base, count: Int) {
    self.base = base
    self.count = count
  }

  func makeIterator() -> Iterator {
    Iterator(base: base, count: count)
  }
}
5 Likes
12

This and @Danny 's solutions worked perfectly. Thanks!

1 Like
13

Do you mind if I add this to swift/validation-test at main · swiftlang/swift · GitHub? :slight_smile:

4 Likes
14

If anyone is unblocked to add some unit tests and header documentation I think this would make a great diff to ship on swift-algorithms.

BTW… it looks like there is an open TODO to also add variadic generic cartesian products to swift-testing.

15

Sure :slight_smile:

16

I was asking myself that exact question a long while ago. More than half a year ago I had come up with the following solution (trying to avoid type-erasure)

17

Actually, when I was solving this problem for myself I also encountered this. Here is an issue opened a loong while ago

18

Eh, don't read too much into that. There are ways to implement higher-arity Cartesian products, but we found as we were building Swift Testing that the combinatoric complexity was problematic. For instance, this test function would need to run 4 billion times:

@Test(arguments: 0 ..< 256, 0 ..< 256, 0 ..< 256, 0 ..< 256)
func kablammo(i: Int, j: Int, x: Int, y: Int) { /* ... */ }