如何在Swift中使用头/头和休息/尾巴？

Question

为了在功能性风格来使用斯威夫特，我们应该如何处理head和tail列表第？Arrays和ArraySlices 是否合适（似乎很像，因为an ArraySlice是获得子列表的有效机制）？是一个转换权机制Array到ArraySlice和使用.first!，并.dropFirst()作为等价物head和tail？

作为添加数字列表的示例：

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

Answer 1

Array具有一个初始化（init(_:)），可以产生Array从任何Sequence，例如ArraySlice。但是，使用它会强制复制数组数据，这使像这样的简单求和算法实际上具有O(nums.count^2)性能，即使它看起来只扫描数组一次也是如此。

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)

为了解决这个问题，一个更好的实现将只对ArraySlices进行操作，允许进行无副本切片，但这需要Array先将输入转换为ArraySlice。幸运的是，内部函数可以使此过程对公共API透明，但确实会使代码更长。

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))
}

但实际上，正如马特所说，不要这样做。头/尾编程方法在某种语言中很有意义，该语言可以通过模式匹配，良好的编译器优化，尾部调用优化等很好地促进编程。Swift的设计鼓励使用reduce。它不仅更短，更易读，而且性能更高。

为了进行比较，以下是典型的Swift方法：

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

• 它更简单，更短。
• 它是多态的，因此可以与any一起使用Sequence，而不仅限于Array

• 它对任何Integer类型都是通用的，而不仅仅是Int。因此，所有这些工作：

  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())
  

但是，如果您坚持采用这种“头/尾”方法，则可以尝试以下两种方法之一：

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)))

这段代码摘录了如何将列表分为头尾的详细信息，让您sum只担心为您提供的head和即可编写tail。