通过Swift Sliceable进行递归 [英] Recursion over a Swift Sliceable
问题描述
我觉得我一定会错过一些明显的东西。将头文件分解成头部和尾部，然后在尾部递归是一种标准的函数式编程技术，但我很努力为Swift中的 Sliceable 类型执行此操作。 p>
我有一个递归函数，它遵循以下模式：
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 code>不是 Sliceable ，所以我不能将它传递给我的函数。
我不确定编译器在这里能做什么样的优化，但在我看来，从 SubSlice 创建一个新数组是不必要的。有没有解决这个问题的方法？
此外，我真正想要做的是创建一个可以接受 Sliceable 类型：
func recurseSeq< T：Sliceable，其中T.Generator.Element == Int>（list：T） - > [int] {
guard let first = list.first else {
return []
}
let rest = recurseSeq（dropFirst（list） ）//< - 错误 - 无法用参数类型T.SubSlice调用
let next = rest.first ?? 0
return [first + next] + rest
}
这一次我没有解决方案，我有一个 SubSlice 的事实。我怎样才能实现我的目标？
事实证明，是的通用解决方案。您需要添加这些通用要求：
<
S：Sliceable其中S.SubSlice：Sliceable，
S.SubSlice.Generator.Element == S.Generator.Element，
S.SubSlice.SubSlice == S.SubSlice
>
对于发布的问题，这给出：
func recurseSeq<
S：Sliceable其中S.SubSlice：Sliceable，
S.SubSlice.Generator.Element == Int，
S.SubSlice.SubSlice == S.SubSlice，
。 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
}
这是一个有用的通用减少任何分片：
扩展Sliceable其中
SubSlice：Sliceable，
SubSlice .Generator.Element == Generator.Element，
SubSlice.SubSlice == SubSlice {
func recReduce（combine：（Generator.Element，Generator.Element） - > Generator.Element） - > Generator.Element？ {
返回self.first.map {
在
中的头部dropFirst（self）
.recReduce（combine）
.map {combine（head， $ 0）}
??头部
[1，2，3] .recReduce（+）// 6
我不能赞扬这个，解决方案是张贴在苹果开发论坛上。
这是一个遗憾，通用的需求是如此涉及这样一个基本的操作 - 这很难直观！但我很高兴能有一个解决方案......
I feel that I must be missing something obvious. Decomposing a list into the head and tail and then recursing over the tail is a standard functional programming technique, yet I'm struggling to do this for Sliceable types in Swift.
I have a recursive function that follows this pattern:
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
}
Obviously the real code does a lot more than add each number to the next.
Note the call to Array(dropFirst(seq)). Converting to an Array is required since dropFirst actually returns an ArraySlice, and an ArraySlice isn't a Sliceable, so I can't pass it to my function.
I'm not sure what sort of optimization the compiler is capable of here, but it seems to me that creating a new array from a SubSlice unnecessarily won't be optimal. Is there a solution to this?
Furthermore, what I'd really like to do is create a version of this function that can take any Sliceable type:
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
}
This time I don't have a solution to the fact that I have a SubSlice. How can I achieve my goal?
It turns out that there is a generic solution. You need to add these generic requirements:
<
S : Sliceable where S.SubSlice : Sliceable,
S.SubSlice.Generator.Element == S.Generator.Element,
S.SubSlice.SubSlice == S.SubSlice
>
For the question posted, this gives:
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
}
Here's a useful generic reduce on any sliceable:
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
I can't take credit for this, the solution was posted on the Apple Development Forums.
It's a shame that the generic requirements are so involved for such a a basic operation - it's hardly intuitive! But I'm glad to have a solution...
这篇关于通过Swift Sliceable进行递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
