Swift 可切片的递归

Question

我觉得我一定遗漏了一些明显的东西。将列表分解为头部和尾部，然后在尾部递归是一种标准的函数式编程技术，但我正在努力为 Swift 中的 Sliceable 类型执行此操作。

我有一个遵循这种模式的递归函数：

func recurseArray(arr: [Int]) -> [Int] {

    guard let first = arr.first else {
        return []
    }

    let rest = recurseArray(Array(dropFirst(arr)))
    let next = rest.first ?? 0

    return [first + next] + rest

}

显然，实际代码所做的不仅仅是将每个数字加到下一个数字。

注意对 Array(dropFirst(seq)) 的调用。需要转换为数组，因为 dropFirst 实际上 returns 是 ArraySlice，而 ArraySlice 不是 Sliceable，所以我不能将它传递给我的功能。

我不确定编译器在这里能够进行什么样的优化，但在我看来，从 SubSlice 不必要地创建一个新数组并不是最优的。有解决办法吗？

此外，我真正想做的是创建一个可以接受 any Sliceable类型：

func recurseSeq<T: Sliceable where T.Generator.Element == Int>(list: T) -> [Int] {

    guard let first = list.first else {
        return []
    }

    let rest = recurseSeq(dropFirst(list)) // <- Error - cannot invoke with argument type T.SubSlice
    let next = rest.first ?? 0

    return [first + next] + rest
}

这次我没有办法解决我有SubSlice的问题。我怎样才能实现我的目标？

Answer 1

在每次迭代中都创建一个数组似乎不是一个好主意。我不知道编译器是否以某种方式对其进行了优化，但您可能会找到不同的解决方案。

例如，在这种情况下，您可以放弃递归并使用 for 循环来代替修改数组。

func recurseArray2(var a: [Int]) -> [Int] {
    for var i = a.count-1; i > 0; i-- {
        a[i-1] += a[i]
    }
    return a
}

Answer 2

实际上ArraySlice是Sliceable，所以你可以递归 ArraySlice<Int>:

func recurseArray(arr: ArraySlice<Int>) -> [Int] {

    guard let first = arr.first else {
        return []
    }

    let rest = recurseArray(dropFirst(arr))
    let next = rest.first ?? 0

    return [first + next] + rest
}

使用在顶层只调用一次的包装函数：

func recurseArray(arr: [Int]) -> [Int] {
    return recurseArray(arr[arr.startIndex ..< arr.endIndex])
}

对于你的第二个更普遍的问题，我没有解决方案。 Sliceable 的 API 文档声明 SubSlice 应该 Sliceable 本身（所有已知的 Sliceable 都是这种情况类型）。

因此我觉得应该可以通过请求 T.SubSlice 本身可以用相同的 SubSlice 切片类型，但是这不会编译：

func recurseSeq<T: Sliceable where T.Generator.Element == Int,
    T.SubSlice : Sliceable,
    T.SubSlice.SubSlice == T.SubSlice>(list: T.SubSlice) -> [Int] {

        guard let first = list.first else {
            return []
        }
        let rest = recurseSeq(dropFirst(list) as T.SubSlice)
        // error: cannot invoke 'recurseSeq' with an argument list of type '(T.SubSlice)'

        let next = rest.first ?? 0

        return [first + next] + rest
}

编译器接受 dropFirst(list) 可以转换为 T.SubSlice，但拒绝调用 recurseSeq() 该值，我不这样做明白了。

或者，您可以递归 GeneratorType:

func recurseGen<G: GeneratorType where G.Element == Int>(inout gen: G) -> [Int] {

    guard let first = gen.next() else {
        return []
    }
    let rest = recurseGen(&gen)
    let next = rest.first ?? 0
    return [first + next] + rest
}

包装器采用 SequenceType:

func recurseSeq<T: SequenceType where T.Generator.Element == Int>(list: T) -> [Int] {
    var gen = list.generate()
    return recurseGen(&gen)
}

数组和数组切片都符合SequenceType，所以应该适用于您的所有情况。

Answer 3

原来是一个通用的解决方案。您需要添加这些通用要求：

<  
  S : Sliceable where S.SubSlice : Sliceable,  
  S.SubSlice.Generator.Element == S.Generator.Element,  
  S.SubSlice.SubSlice == S.SubSlice  
  >

对于发布的问题，这给出了：

func recurseSeq<
    S : Sliceable where S.SubSlice : Sliceable,
    S.SubSlice.Generator.Element == Int,
    S.SubSlice.SubSlice == S.SubSlice,
    S.Generator.Element == Int
    >(list: S) -> [Int] {

    guard let first = list.first else {
        return []
    }

    let rest = recurseSeq(dropFirst(list))
    let next = rest.first ?? 0

    return [first + next] + rest
}

这是对任何可切片的有用的通用 reduce：

extension Sliceable where  
  SubSlice : Sliceable,  
  SubSlice.Generator.Element == Generator.Element,  
  SubSlice.SubSlice == SubSlice {  

  func recReduce(combine: (Generator.Element, Generator.Element) -> Generator.Element) -> Generator.Element? {  

    return self.first.map {  
      head in  
      dropFirst(self)  
        .recReduce(combine)  
        .map {combine(head, [=12=])}  
        ?? head  
    }  
  }  
}  
[1, 2, 3].recReduce(+) // 6

我不能把这归功于此，解决方案是在 Apple 开发论坛上 posted。

令人遗憾的是，如此基本的操作涉及通用要求 - 很难直观！但我很高兴有一个解决方案...

Swift 可切片的递归

Recursion over a Swift Sliceable

functional-programming

swift