Implementation technique of `try_fold()`

Using Swift
1

I'm studying the technique for implementing something similar to Rust try_fold(), which in un-optimised form should be the following. It incurs heavy overhead of copying collection. I'd like to know what is the way or ways to optimise it?

extension Sequence {
  func try_fold<T, C: MutableCollection<T>, E>(
    _ initial: C,
    _ transform: (inout C, Element) throws -> Result_<C, E>
  ) rethrows -> Result_<C, E> {
    var collection = initial
    for element in self {
      switch try transform(&collection, element) {
      case .Ok(let updatedCollection):
        collection = updatedCollection
      case .Err(let error):
        return .Err(error)
      }
    }
    return .Ok(collection)
  }
}

Enum Result_<T, E> is defined as follows:

public enum Result_<T, E> {
  case Ok(T)
  case Err(E)
}
2

Why are you both passing the collection as inout and returning it in a result?

Rust's try_fold() is defined on Iterator as:

fn try_fold<B, F, R>(&mut self, init: B, f: F) -> R
where
    Self: Sized,
    F: FnMut(B, Self::Item) -> R,
    R: Try<Output = B>,

Which I guess is roughly equivalent in Swift to

extension Sequence {
    func tryFold<B: ~Copyable, Failure: Error>(
       _ b: consuming B,
       _ f: (consuming B, Element) throws(Failure) -> B
    ) throws(Failure) -> B
}

The naïve implementation of which compiles fine:

extension Sequence {
    func tryFold<B: ~Copyable, Failure: Error>(
       _ b: consuming B,
       _ f: (consuming B, Element) throws(Failure) -> B
    ) throws(Failure) -> B {
        var b = b
        for element in self {
            b = try f(b, element)
        }
        return b
    }
}

And shouldn't result in any copies of B...

If you want B to go inout, that works too:

extension Sequence {
    func tryFold<B: ~Copyable, Failure: Error>(
       _ b: inout B,
       _ f: (inout B, Element) throws(Failure) -> Void
    ) throws(Failure) {
        for element in self {
            try f(&b, element)
        }
    }
}

But Swift already has this function in the stdlib, as reduce (though it requires the equivalent of B to be Copyable): reduce(_:_:) | Apple Developer Documentation

1 Like
3

@KeithBauerANZ Thanks. I was aware of reduce().

The use of consuming and ~Copyable is new to me. This should bridge the gap.