How to use first/head and rest/tail with Swift?

Question

In order to use Swift in a functional style, how should we be dealing with head and tails of lists? Are Arrays and ArraySlices appropriate (seems like it since an ArraySlice is an efficient mechanism to get sublists)? Is the right mechanism to convert an Array to an ArraySlice and use .first! and .dropFirst() as equivalents for head and tail?

As an example of adding a list of numbers:

func add(_ nums: ArraySlice<Int>) -> Int {
    if nums.count == 0 {
        return 0
    } else {
        return nums.first! + add(nums.dropFirst())
    }
}

Answer 1

Array has an initializer (init(_:)) that can produce an Array from any Sequence, such as an ArraySlice. However, using it forces a copy of the array data, which makes a simple sum algorithm like this to actually have O(nums.count^2) performance, even though it looks like it's only scanning through the array once.

func sum(_ nums: [Int]) -> Int {
    guard let head = nums.first else { return 0 } //base case, empty list.
    return head + sum(Array(nums.dropFirst()))
}

let input = Array(1...10)
let output = sum(input)
print(output)

To get around this, a better implementation would instead just operate on ArraySlices, allowing copy-less slicing, but that requires the input Array first be converted into an ArraySlice. Luckily, an inner function can help make this transparent to the public API, but it does make the code longer.

func sum(_ nums: [Int]) -> Int {
    func sum(_ nums: ArraySlice<Int>) -> Int {
        guard let head = nums.first else { return 0 } //base case, empty list.
        return head + sum(nums.dropFirst())
    }
    return sum(ArraySlice(nums))
}

But really, as matt said, don't do this. The head/tail approach to programming makes sense in a language that facilitates it well with pattern matching, good compiler optimizations, tail call optimization, etc. Swift's design encourages using reduce. Not only is it shorter and much more readable, but it's also more performant.

For comparison, here's what a typical Swift approach would be to this:

extension Sequence where Iterator.Element: Integer {
    func sum() -> Iterator.Element {
        return self.reduce(0, +)
    }
}

• It's simpler and shorter.
• It's polymorphic, so it'll work with any Sequence, rather than just being limited to Array

• It's generic over any Integer type, not just Int. So these all work:

  print(Array<UInt  >(1...10).sum())
  print(Array<UInt8 >(1...10).sum())
  print(Array<UInt16>(1...10).sum())
  print(Array<UInt32>(1...10).sum())
  print(Array<UInt64>(1...10).sum())
  print(Array< Int  >(1...10).sum())
  print(Array< Int8 >(1...10).sum())
  print(Array< Int16>(1...10).sum())
  print(Array< Int32>(1...10).sum())
  print(Array< Int64>(1...10).sum())
  

However, if you insist on taking this head/tail approach, you can try one of these two techniques:

extension Collection {
    func headTail1<Head, Tail, ReturnType>(_ closure: (Head?, Tail) -> ReturnType) -> ReturnType 
        where Head == Self.Element, Tail == Self.SubSequence {
        return closure(self.first, self.dropFirst())
    }

    func headTail2<Head, Tail>() ->(Head?, Tail)
        where Head == Self.Element, Tail == Self.SubSequence {
        return (self.first, self.dropFirst())
    }
}

func sum1<C: Collection, I: Numeric>(_ nums: C) -> I
    where C.Element == I {
    return nums.headTail1 { head, tail in
        guard let head = head else { return 0 } //base case, empty list
        return head + sum(tail)
    }
}

func sum2<C: Collection, I: Numeric>(_ nums: C) -> I
    where C.Element == I {
    let (_head, tail) = nums.headTail2()
    guard let head = _head else { return 0 } //base case, empty list
    return head + sum(tail)
}

print(sum(Array(1...10)))

This code abstracts away the details of how the list is split into its head and tail, letting you write sum by only worrying about the head and tail that are provided for you.