Iterate parameter pack in reverse

Using Swift
1

There's this well know trick to reduce parameter packs, sometimes using a function to simplify things.

func countAll<each C>(_ collections: repeat each C) where C: Collection {
    var count = 0
    for c in repeat each collections {
        count += c.count
    }
    return count
}

I however need to accumulate this state from last to first, meaning iterate the parameter pack in reverse. How would I do that?

func add<each I: FixedWidthInteger>(lhs: repeat each I, rhs: repeat each I) -> (repeat each I) {
	var carry = false
	func add<T: FixedWidthInteger>(lhs: T, rhs: T) -> T {
		let r1 = lhs.addingReportingOverflow(rhs)
		let r2 = r1.partialValue.addingReportingOverflow(carry ? 1 : 0)
		carry = r1.overflow || r2.overflow
		return r2.partialValue
	}
	// need to iterate in reverse!
	return (repeat add(lhs: each lhs, rhs: each rhs))
}
2

A clunky option is to stack up closures:

var op: (callback: (C) -> Void) -> Void = { _ in }
for c in repeat each collections {
  op = { callback in
    callback(c)
    op(callback)
  }
}
op { print($0) }

But this only works with Copyable & Escapable types, and has at least a bit of a perf impact (though since packs usually don't get that long, you probably don't need to worry about it that much).

1 Like
3

Thanks, I'll use that for now! Parameter packs don't support ~Copyable or ~Escapable as far as I'm aware so that shouldn't be an issue.

4

Pack expansion only ever runs forward, from left to right, per SE-0393. Your inner add(lhs:rhs:) mutates carry as a side effect, so the carry propagates in the order the expansion evaluates. There's no way to make the expansion itself run the other direction, so the reverse part can't be a pack expansion at all.

The trick is to not use a pack for the reverse step. Walk the packs forward once to capture each limb's work into a plain array of closures, then run that array in reverse with ordinary reversed() iteration. Packs only come back when you rebuild the result tuple, which is forward:

func add<each T: FixedWidthInteger>(
    lhs : repeat each T,
    rhs : repeat each T
) -> (repeat each T)
{
    /// Forward: one typed closure per limb. Each captures its own 
    /// lhs/rhs at full concrete type and, given a carry-in, returns its 
    /// sum and carry-out. The sum is boxed as `Any` because each limb's 
    /// type is independent; there is no common element type.
    var limbs: [(Bool) -> (sum: Any, carry: Bool)] = []

    for (l, r) in repeat (each lhs, each rhs)
    {
        limbs.append
        {
            (carryIn: Bool) in

            let r1  = l.addingReportingOverflow(r)
            let r2  = r1.partialValue.addingReportingOverflow(carryIn ? 1 : 0)

            return (
                r2.partialValue,
                r1.overflow || r2.overflow
            )
        }
    }

    /// Reverse: thread the carry from the last limb to the first, 
    /// storing each sum at its original index.
    var sums    : [Any?]    = .init(repeating: nil, count: limbs.count)
    var carry   : Bool      = false

    for index in limbs.indices.reversed()
    {
        let (sum, carryOut): (Any, Bool) = limbs[index](carry)

        sums[index]     = sum
        carry           = carryOut
    }

    /// Forward reconstruction.
    let index = PackIndex()

    return (repeat sums[index.next()]! as! each T)
}

The reconstruction rebuilds (repeat each T) forward. The only wrinkle is mapping array index to pack position, which needs a sequential counter. I use a simple class called PackIndex to do this when rebuilding heterogeneous tuples.

Two things to keep in mind:

  • This implementation assumes the tuple is most-significant-limb-first, so the carry flows from the last limb toward the first. For the other orientation, just don't call reversed() when looping.
  • The closures box their sums as Any and the reconstruction force-casts back. That's safe only because the value of position k has type k. Only iteration can be reversed, not reconstruction. If reconstruction were reversed, you'd be casting sums[N-1-k] to the type at position k, which traps if the limbs are heterogeneous.
5

Do you really need a pack here? In other words, are you actually calling this function with a heterogenous list of types that all conform to FixedWidthInteger? Personally I would avoid the whole kerfuffle and simply pass down an Array<Int>, which can then be transformed with standard collection operations. If the example was simplified from what you actually have going on, some more context would be helpful.

3 Likes