我觉得我必须遗漏一些明显的东西.将列表分解为头部和尾部,然后通过尾部递归是一种标准的函数式编程技术,但我正在努力为
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实际上返回一个ArraySlice,而ArraySlice不是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的事实.我怎样才能实现目标？
事实证明,有一个通用的解决方案.您需要添加这些通用要求：
< 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
我不能相信这一点,Apple开发论坛上的解决方案是posted.
令人遗憾的是,通用要求如此涉及到这样一个基本操作 – 它几乎不直观！但我很高兴有一个解决方案……