Recursion over a Sliceable

Question

Hi,

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 Sliceble types in Swift.

To start with a simple case using an Array, 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 `Sliceable`, so I can't pass it to my function.

I'm not sure what sort of optimisation the compiler is capable of here, but it seems to me that creating a new array from a slice 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?

Thanks,

Tim

Swift

935

Posted by

Tim Armes

Reply

Add a Comment

Answer 1

You can manage it with these generic requirements:

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

For instance, this sums a sliceable Collection:

func recSum<
  S : Sliceable where S.SubSlice : Sliceable,
  S.SubSlice.Generator.Element == Int,
  S.SubSlice.SubSlice == S.SubSlice,
  S.Generator.Element == Int
  >(list: S) -> Int {
    return list.first.map { $0 + recSum(dropFirst(list)) } ?? 0
}
recSum([1, 2, 3]) // 6

And if you wanted a more generic example, here's a kind of reduce1 with recursion:

func recReduce<
  T, S : Sliceable where S.SubSlice : Sliceable,
  S.Generator.Element == T,
  S.SubSlice.Generator.Element == T,
  S.SubSlice.SubSlice == S.SubSlice
  >(list: S, combine: (T, T) -> T ) -> T? {
  
    return list.first.map {
      head in
      recReduce(dropFirst(list), combine: combine)
        .map {b in combine(head, b)}
        ?? head
    }
}
recReduce([1, 2, 3], combine: +) // 6

Or, as a method:

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

Posted by

oisdk

Add a Comment

Answer 2

You can manage it with these generic requirements:

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

For instance, this sums a sliceable Collection:

func recSum<
  S : Sliceable where S.SubSlice : Sliceable,
  S.SubSlice.Generator.Element == Int,
  S.SubSlice.SubSlice == S.SubSlice,
  S.Generator.Element == Int
  >(list: S) -> Int {
    return list.first.map { $0 + recSum(dropFirst(list)) } ?? 0
}
recSum([1, 2, 3]) // 6

And if you wanted a more generic example, here's a kind of reduce1 with recursion:

func recReduce<
  T, S : Sliceable where S.SubSlice : Sliceable,
  S.Generator.Element == T,
  S.SubSlice.Generator.Element == T,
  S.SubSlice.SubSlice == S.SubSlice
  >(list: S, combine: (T, T) -> T ) -> T? {
  
    return list.first.map {
      head in
      recReduce(dropFirst(list), combine: combine)
        .map {b in combine(head, b)}
        ?? head
    }
}
recReduce([1, 2, 3], combine: +) // 6

Or, as a method:

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

Posted by

oisdk

Add a Comment

Answer 3

Wow, that's perfect, thank you.

I'm not sure that I yet understand why this works though. The compiler doesn't explain why I can't recurse without these conditions - how are we meant to get about finding them?

Posted by

Tim Armes

Add a Comment

Answer 4

As far as I understand it, the problem is that the slice method on a collection type returns a different type to the thing being sliced. So it's difficult to verify that the slice returned is itself sliceable. Thers's more information here: "Though it can't currently be enforced by the type system, the

SubSlice

type in a concrete implementation of

Sliceable

should also be

Sliceable

." So when you want to slice slices, the compiler can't verify that the subslice is also sliceable. So if you wrote, say:

func foo<S : Sliceable where S.SubSlice : Sliceable>(unSliced: S) -> S.SubSlice {
  return foo(unSliced[1..<unSliced.endIndex])
}

It won't compile, because while it may know that S.SubSlice is Sliceable, it doesn't know that S.SubSlice.SubSlice is Sliceable, and so on. I tried to get what I had above to be a little more concise (in terms of the type requirements) and I managed this:

protocol RecursiveSliceable: Sliceable { typealias SubSlice : RecursiveSliceable }

extension ArraySlice            : RecursiveSliceable {}
extension Array                 : RecursiveSliceable {}
extension String.CharacterView  : RecursiveSliceable {}

extension RecursiveSliceable where SubSlice.Generator.Element == Generator.Element {

  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
"hello".characters.recReduce { a, b in b }    // "o"

Which obviously isn't ideal. I was aiming for some protocol RecursiveSliceable that would enforce everything that you need, so you could write your slices under it. This also came pretty close to what I wanted:

protocol RecursiveSliceable: Sliceable {
  typealias SubSlice : RecursiveSliceable
  var first: SubSlice.Generator.Element? { get }
}
extension ArraySlice            : RecursiveSliceable {}
extension Array                 : RecursiveSliceable {}
extension String.CharacterView  : RecursiveSliceable {}
extension RecursiveSliceable {

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

    return self.first.map {
      (head: SubSlice.Generator.Element) -> SubSlice.Generator.Element in
      dropFirst(self)
        .recReduce(combine)
        .map {combine(head, $0)}
        ?? head
    }
  }
}
[1, 2, 3].recReduce(+)                        // 6
"hello".characters.recReduce { a, b in b }    // "o"

But again, not really ideal.

That's just if you're trying to keep up the "Sliceable", though. If you're just intersted in a headTail function, and you're only traversing the sequence once, this might work:

extension SequenceType {
  func headTail() -> (Generator.Element, GeneratorSequence<Generator>)? {
    var g = self.generate()
    return g.next().map{($0, GeneratorSequence(g))}
  }
}

Putting it into the other example:

extension SequenceType {
  func reduce(combine: (Generator.Element, Generator.Element) -> Generator.Element) -> Generator.Element? {
    return self.headTail().map {
      (head, tail) in
      tail
        .reduce(combine)
        .map{combine(head, $0)}
        ?? head
    }
  }
}
[1, 2, 3].reduce(+) // 6

Posted by

oisdk

Add a Comment

Answer 5

Great info, thank you.

Posted by

Tim Armes

Add a Comment

Recursion over a Sliceable

Accepted Reply

Replies