如何将 first/head 和 rest/tail 与 Swift 一起使用？

Question

为了以函数式风格使用 Swift，我们应该如何处理 head 和 tail 列表？ Arrays 和 ArraySlices 是否合适（似乎是因为 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

您的示例的问题在于您不会使用head 和tail 添加数字列表。你会打电话给 reduce:

let nums = [1,2,3,4,5]
let sum = nums.reduce(0,+)

所以，虽然我和下一个人一样喜欢 LISP / Scheme，但您需要一个更有说服力的案例来说明我们何时需要 head 和tail，假设我们有 map、filter 和 reduce（依此类推）。

Answer 2

Array has an initializer (init(_:)) that can produce an Array from any Sequence, such as an 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)

为了解决这个问题，更好的实现方式是只对 ArraySlice 进行操作，允许无副本切片，但这需要输入 Array 首先转换为 ArraySlice.幸运的是，内部函数可以帮助使这对 public 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))
}

但真的，正如 matt 所说，不要这样做。 head/tail 编程方法在通过模式匹配、良好的编译器优化、尾调用优化等促进编程的语言中是有意义的。Swift 的设计鼓励使用 reduce。它不仅更短、更易读，而且性能更高。

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

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

它更简单、更短。
它是多态的，所以它适用于任何 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())

但是，如果您坚持采用这种 head/tail 方法，您可以尝试以下两种技术之一：

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

此代码抽象出列表如何拆分为头部和尾部的细节，让您只需担心提供的 head 和 tail 即可编写 sum给你。

如何将 first/head 和 rest/tail 与 Swift 一起使用？

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

recursion

functional-programming

tail

swift

swift3