Swift Sliceable上的递归

Question

我觉得我必须遗漏一些明显的东西.将列表分解为头部和尾部,然后通过尾部递归是一种标准的函数式编程技术,但我正在努力为SliceableSwift中的类型执行此操作.

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

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实际返回a ArraySlice,而a ArraySlice不是a Sliceable,因此我无法将其传递给我的函数.

我不确定编译器在这里能做什么样的优化,但在我看来,从SubSlice不必要的方式创建一个新的数组将不是最佳的.这个问题有方法解决吗？

此外,我真正想要做的是创建一个可以采用任何 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

事实证明，有一个通用的解决方案。您需要添加这些通用要求：

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

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

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, $0)}  
        ?? head  
    }  
  }  
}  
[1, 2, 3].recReduce(+) // 6  

我不能将此归功于此，该解决方案已发布在苹果开发论坛上。

遗憾的是，对于这样一个基本操作来说，通用要求是如此复杂 - 这很难直观！但我很高兴有一个解决方案......