Recursion over a Swift Sliceable

Question

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?

Answer 1

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

Answer 2

Actually ArraySlice is Sliceable, so you can recurse on 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
}

with a wrapper function which is called only once at the top level:

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

---

I don't have a solution for your second more general problem. The API docs for Sliceable state that SubSlice should be Sliceable itself (which is the case for all known Sliceable types).

I have therefore the feeling that it should be possible by requesting that T.SubSlice is itself sliceable with the identical SubSlice type, however this does not compile:

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
}

The compiler accepts that dropFirst(list) can be cast to T.SubSlice, but refuses to call recurseSeq() on that value, which I do not understand.

---

Alternatively, you can recurse on a 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
}

with a wrapper that takes a SequenceType:

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

Arrays and array slices all conform to SequenceType, so that should work in all your cases.