How to write this generic dotProduct function in Swift?

Say I'd like to write a generic function dotProduct, something like:


func dotProduct<T: FixedSizeArrayType where T.Element: BasicArithmeticType>(a: T, b: T) -> T.Element {
    var sum = T(0)
    for i in 0 ..< T.Count { sum = sum + a[i] * b[i] }
    return sum
}

This is just some haphazard pseudo code meant to illustrate the requirements for the function:


  1. It takes as arguments two "fixed size" arrays of equal length and element type and returns the dot product of the two arguments (the type of the return value is of course the same as the element type of the two arguments). It's also ok to make it as a method, with self replacing the first arg.
  2. I want compile time errors if I try to call it with arguments of different size/count/length or element type, and if I try to receive a return value of some other type than the element type of the two arguments.
  3. And as can be seen, The T.Element type should conform to an imaginary BasicArithmeticType protocol. This protocol is possible to write yourself, but currently the Swift standard library only has IntegerArithmeticType. Anyway, conforming to it would simply imply things like being able to perform the multiplication, addition and initialization from an integer literal (0 in this case).
  4. Also, if the values of the arguments are knowable at compile time I want Swift to "run it at compile time" similar to what it can do thanks to the Swift standrad library type StaticString, as demonstrated by Airspeed Velocity at around 5:40 into this Swift Summit talk entitled Zero-Cost Abstractions (link omitted, see why below). Also, as already mentioned, the compiler should be able to know about the number of elements in the arguments so that they can be "true" value types (containing no references) and optimized as such.


After watching the WWDC 2015 video Protocol Oriented Programming in Swift (link omitted, see why below), I wouldn't be surprised if there is a really elegant way to achive this but I can't figure out how. I find it especially hard to come up with something nice for the fixed size "staticly knowable" array type(s). Using ordinary arrays and checking their length dynamically is both much slower than using eg structs with let x, y, z: T (for the 3 element type). Also, using regular arrays will not give me a compile time error when calling the function with arguments of different length/counts.


It is possible to achieve all this using a lot of duplicated code for "fixed size array" structs of length 1, 2, 3, etc, but it feels like fighting the type system, doing the job of the compiler and repeating yourself.


So, does anyone know "the proper way" to write this function/method (including any scaffolding)?


And if there is a nice solution to this, I would also like to see a similar function/method crossProduct (which would of course return a T instead of a T.Element).


(About the omitted links:

Apparently, including them makes this forum software condemn this post to an eternity in Drafts along with the warning message: "Please note: your content was added successfully, but a moderator needs to approve it before it can be posted." So until this forum bug is fixed, you'll have manually search for the videos.)

Edit: Turns out "there is a really elegant way to achive this":

Accepted Reply

Here's a little prototype I whipped up in Swift 2; HTH:


/// Abstraction of numeric types that approximate real numbers
protocol ApproximateRealType {
  init() // zero
  func * (Self,Self) -> Self
  func + (Self,Self) -> Self
  func / (Self,Self) -> Self
  func - (Self,Self) -> Self
  prefix func + (Self) -> Self
  prefix func - (Self) -> Self
}


extension Double : ApproximateRealType {}
extension Float : ApproximateRealType {}


// Abstraction of a mathematical vector
protocol VectorType {
  typealias Scalar : ApproximateRealType
  func dotProduct(Self) -> Scalar

  // Parts not essential for answering the question
  init()
  var count: Int {get}
  subscript(Int) -> Scalar {get set}

  func + (Self,Self) -> Self
  func - (Self,Self) -> Self
  prefix func + (Self) -> Self
  prefix func - (Self) -> Self
  func * (Self, Scalar) -> Self
  func / (Self, Scalar) -> Self
}


struct EmptyVector<T: ApproximateRealType> : VectorType {
  init() {}
  typealias Scalar = T
  func dotProduct(other: EmptyVector) -> Scalar {
    return Scalar() // zero
  }
  var count: Int { return 0 }

  subscript(i: Int) -> Scalar {
    get { fatalError("subscript out-of-range") }
    set { fatalError("subscript out-of-range") }
  }
}


struct Vector<Tail: VectorType> : VectorType {
  typealias Scalar = Tail.Scalar

  init(_ scalar: Scalar, tail: Tail = Tail()) {
    self.scalar = scalar
    self.tail = tail
  }

  init() {
    self.scalar = Scalar()
    self.tail = Tail()
  }

  func dotProduct(other: Vector) -> Scalar {
    return scalar * other.scalar + tail.dotProduct(other.tail)
  }

  var count: Int { return tail.count + 1 }
  var scalar: Scalar
  var tail: Tail

  subscript(i: Int) -> Scalar {
    get { return i == 0 ? scalar : tail[i - 1] }
    set { if i == 0 { scalar = newValue } else { tail[i - 1] = newValue } }
  }
}


//===--- A nice operator for composing vectors ----------------------------===//
//===--- there's probably a more appropriate symbol -----------------------===//
infix operator ⋮ {
associativity right
precedence 1 // unsure of the best precedence here
}


func ⋮ <T: ApproximateRealType> (lhs: T, rhs: T) -> Vector<Vector<EmptyVector<T> > > {
  return Vector(lhs, tail: Vector(rhs))
}
func ⋮ <T: ApproximateRealType, U where U.Scalar == T> (lhs: T, rhs: Vector<U>) -> Vector<Vector<U> > {
  return Vector(lhs, tail: rhs)
}


extension Vector : CustomDebugStringConvertible {
  var debugDescription: String {
    if count == 1 {
      return "Vector(\(String(reflecting: scalar)), tail: EmptyVector())"
    }
    return "\(String(reflecting: scalar)) ⋮ " + (count == 2 ? String(reflecting: self[1]) : String(reflecting: tail))
  }
}


//===--- additive arithmetic ---------------------------------------------===//
func + <T> (EmptyVector<T>,EmptyVector<T>) -> EmptyVector<T> {
  return EmptyVector()
}
func - <T> (EmptyVector<T>,EmptyVector<T>) -> EmptyVector<T> {
  return EmptyVector()
}
prefix func + <T> (EmptyVector<T>) -> EmptyVector<T> {
  return EmptyVector()
}
prefix func - <T> (EmptyVector<T>) -> EmptyVector<T> {
  return EmptyVector()
}


func + <T> (lhs: Vector<T>, rhs: Vector<T>) -> Vector<T> {
  return Vector(lhs[0] + rhs[0], tail: lhs.tail + rhs.tail)
}
func - <T> (lhs: Vector<T>, rhs: Vector<T>) -> Vector<T> {
  return Vector(lhs[0] - rhs[0], tail: lhs.tail - rhs.tail)
}
prefix func + <T> (lhs: Vector<T>) -> Vector<T> {
  return lhs
}
prefix func - <T> (lhs: Vector<T>) -> Vector<T> {
  return Vector(-lhs[0], tail: -lhs.tail)
}


//===--- vector-scalar arithmetic -----------------------------------------===//
func * <V: VectorType> (lhs: V.Scalar, rhs: V) -> V {
  return rhs * lhs
}




func * <T> (EmptyVector<T>, T) -> EmptyVector<T> {
  return EmptyVector()
}


func / <T> (EmptyVector<T>, T) -> EmptyVector<T> {
  return EmptyVector()
}


func * <T> (lhs: Vector<T>, rhs: T.Scalar) -> Vector<T> {
  return Vector(lhs[0] * rhs, tail: lhs.tail * rhs)
}


func / <T> (lhs: Vector<T>, rhs: T.Scalar) -> Vector<T> {
  return Vector(lhs[0] / rhs, tail: lhs.tail / rhs)
}




//===--- CollectionType conformance ---------------------------------------===//
extension Vector : CollectionType {
  var startIndex: Int { return 0 }
  var endIndex: Int { return count }
}


//===--- Test -------------------------------------------------------------===//
print(Vector(3.0, tail: EmptyVector()))
print(3.0 ⋮ 4.0 ⋮ 5.0)
print( (3.0 ⋮ 4.0 ⋮ 5.0).dotProduct(6.0 ⋮ 7.0 ⋮ 8.0) ) // 86.0
print((3.0 ⋮ 4.0 ⋮ 5.0) + (6.0 ⋮ 7.0 ⋮ 8.0))
print(2 * (3.0 ⋮ 4.0 ⋮ 5.0))
print((3.0 ⋮ 4.0 ⋮ 5.0) / 2)

Replies

I don't believe there is any way to represent this in the current type system. Just thinking about the fixed-length issue alone, the only way to constrain types like this is to check for the equality or inequality of an associated type. So to emulate this currently requires a bunch of of dummy types to represent various lengths, that could be matched in a where clause, or similar.


protocol FixedLengthArray {
    typealias Length
}

struct FLA<T>: FixedLengthArray {
    typealias Length = T
}

struct Length1 { }
struct Length2 { }
struct Length3 { }
// …

func compatible<FLA0: FixedLengthArray, FLA1: FixedLengthArray where FLA0.Length == FLA1.Length>
               (fla0: FLA0, _ fla1: FLA1) { }

compatible(FLA<Length2>(), FLA<Length2>())


You would need generic types with integer parameters or similar to start implementing that part of your specification.

Thanks, I ended up with the same kind of representation, but I was thinking that maybe there was some other better way ...

I guess this (the lack of integer placeholders in Swift's generics) might be (part of) the reason for why Swift doesn't have anything like fixed length / static arrays?


AFAIK when importing a C struct that contains a static array of N bytes for example, the resulting stored property will be a tuple of N UInt8s, so if N is 10, it's type will be (UInt8, UInt8, UInt8, UInt8, UInt8, UInt8, UInt8, UInt8, UInt8, UInt8), and when N is 1024 it will make a very long line.


I'd like to understand why we shouldn't be able to eg define a generic struct type with a stored property of some number of elements C of some type T, where C and T are generic placeholders. It seems like such a reasonable / useful / normal thing, yet it's impossible.


It would be like a heterogeneous tuple with subscript and (fixed) count. And I guess each (element type, count)-pair would make a different type, but they would all conform to a FixedLengthArrayType protocol (that has an Element typealias and a static/"constexpr" Count Int).


Also, as it actually is possible to implement this in current Swift (by brute force or using some preprocessor, treating each different count/length as special case), it seems like it should be possible to add some syntax to the language in order to support it.


Is there something in the philosophy of the language that prevents it and offers a better alternative?

Or perhaps fixed length arrays was something that had to be sacrificed in order to gain other (more important) advantages?

I would guess, and I think there was some discussion in the old developer forums that you could refer back to, that there's not a philosophical objection to some similar feature, but it just hasn't been a priority so far.

Ok, thanks, I revived the question about fixed-length arrays in the new forums here.

Here's a little prototype I whipped up in Swift 2; HTH:


/// Abstraction of numeric types that approximate real numbers
protocol ApproximateRealType {
  init() // zero
  func * (Self,Self) -> Self
  func + (Self,Self) -> Self
  func / (Self,Self) -> Self
  func - (Self,Self) -> Self
  prefix func + (Self) -> Self
  prefix func - (Self) -> Self
}


extension Double : ApproximateRealType {}
extension Float : ApproximateRealType {}


// Abstraction of a mathematical vector
protocol VectorType {
  typealias Scalar : ApproximateRealType
  func dotProduct(Self) -> Scalar

  // Parts not essential for answering the question
  init()
  var count: Int {get}
  subscript(Int) -> Scalar {get set}

  func + (Self,Self) -> Self
  func - (Self,Self) -> Self
  prefix func + (Self) -> Self
  prefix func - (Self) -> Self
  func * (Self, Scalar) -> Self
  func / (Self, Scalar) -> Self
}


struct EmptyVector<T: ApproximateRealType> : VectorType {
  init() {}
  typealias Scalar = T
  func dotProduct(other: EmptyVector) -> Scalar {
    return Scalar() // zero
  }
  var count: Int { return 0 }

  subscript(i: Int) -> Scalar {
    get { fatalError("subscript out-of-range") }
    set { fatalError("subscript out-of-range") }
  }
}


struct Vector<Tail: VectorType> : VectorType {
  typealias Scalar = Tail.Scalar

  init(_ scalar: Scalar, tail: Tail = Tail()) {
    self.scalar = scalar
    self.tail = tail
  }

  init() {
    self.scalar = Scalar()
    self.tail = Tail()
  }

  func dotProduct(other: Vector) -> Scalar {
    return scalar * other.scalar + tail.dotProduct(other.tail)
  }

  var count: Int { return tail.count + 1 }
  var scalar: Scalar
  var tail: Tail

  subscript(i: Int) -> Scalar {
    get { return i == 0 ? scalar : tail[i - 1] }
    set { if i == 0 { scalar = newValue } else { tail[i - 1] = newValue } }
  }
}


//===--- A nice operator for composing vectors ----------------------------===//
//===--- there's probably a more appropriate symbol -----------------------===//
infix operator ⋮ {
associativity right
precedence 1 // unsure of the best precedence here
}


func ⋮ <T: ApproximateRealType> (lhs: T, rhs: T) -> Vector<Vector<EmptyVector<T> > > {
  return Vector(lhs, tail: Vector(rhs))
}
func ⋮ <T: ApproximateRealType, U where U.Scalar == T> (lhs: T, rhs: Vector<U>) -> Vector<Vector<U> > {
  return Vector(lhs, tail: rhs)
}


extension Vector : CustomDebugStringConvertible {
  var debugDescription: String {
    if count == 1 {
      return "Vector(\(String(reflecting: scalar)), tail: EmptyVector())"
    }
    return "\(String(reflecting: scalar)) ⋮ " + (count == 2 ? String(reflecting: self[1]) : String(reflecting: tail))
  }
}


//===--- additive arithmetic ---------------------------------------------===//
func + <T> (EmptyVector<T>,EmptyVector<T>) -> EmptyVector<T> {
  return EmptyVector()
}
func - <T> (EmptyVector<T>,EmptyVector<T>) -> EmptyVector<T> {
  return EmptyVector()
}
prefix func + <T> (EmptyVector<T>) -> EmptyVector<T> {
  return EmptyVector()
}
prefix func - <T> (EmptyVector<T>) -> EmptyVector<T> {
  return EmptyVector()
}


func + <T> (lhs: Vector<T>, rhs: Vector<T>) -> Vector<T> {
  return Vector(lhs[0] + rhs[0], tail: lhs.tail + rhs.tail)
}
func - <T> (lhs: Vector<T>, rhs: Vector<T>) -> Vector<T> {
  return Vector(lhs[0] - rhs[0], tail: lhs.tail - rhs.tail)
}
prefix func + <T> (lhs: Vector<T>) -> Vector<T> {
  return lhs
}
prefix func - <T> (lhs: Vector<T>) -> Vector<T> {
  return Vector(-lhs[0], tail: -lhs.tail)
}


//===--- vector-scalar arithmetic -----------------------------------------===//
func * <V: VectorType> (lhs: V.Scalar, rhs: V) -> V {
  return rhs * lhs
}




func * <T> (EmptyVector<T>, T) -> EmptyVector<T> {
  return EmptyVector()
}


func / <T> (EmptyVector<T>, T) -> EmptyVector<T> {
  return EmptyVector()
}


func * <T> (lhs: Vector<T>, rhs: T.Scalar) -> Vector<T> {
  return Vector(lhs[0] * rhs, tail: lhs.tail * rhs)
}


func / <T> (lhs: Vector<T>, rhs: T.Scalar) -> Vector<T> {
  return Vector(lhs[0] / rhs, tail: lhs.tail / rhs)
}




//===--- CollectionType conformance ---------------------------------------===//
extension Vector : CollectionType {
  var startIndex: Int { return 0 }
  var endIndex: Int { return count }
}


//===--- Test -------------------------------------------------------------===//
print(Vector(3.0, tail: EmptyVector()))
print(3.0 ⋮ 4.0 ⋮ 5.0)
print( (3.0 ⋮ 4.0 ⋮ 5.0).dotProduct(6.0 ⋮ 7.0 ⋮ 8.0) ) // 86.0
print((3.0 ⋮ 4.0 ⋮ 5.0) + (6.0 ⋮ 7.0 ⋮ 8.0))
print(2 * (3.0 ⋮ 4.0 ⋮ 5.0))
print((3.0 ⋮ 4.0 ⋮ 5.0) / 2)

Wow, that is probably the most informative enlightening piece of Swift I've seen so far. I wish I had thought of that, ie this:

struct EmptyVector<T> : VectorType { … }
struct Vector<Tail: VectorType> : VectorType{ … }

Ah, of course. Great example.

Wow.


This took me ages to fully understand this code. In particular this statement had me confused for ages:


func ⋮ <T: ApproximateRealType> (lhs: T, rhs: T) -> Vector<Vector<EmptyVector<T> > > {
  return Vector(lhs, tail: Vector(rhs))
}


I couln't see how you could call Vector(rhs). When I typed it into the playground it returns the obvious error message:


Cannot find initializer for type 'Vector<Tail>' that accepts an argument of type '(Double)'


Of course what's actually happening is far more subtle. When using the function above to compose 2 ApproximateRealTypes, the return type of the function is giving the compiler all it needs to know to infer that the tail is an EmptyVector.