Transformations an array, combination of between map and reduce

Question

I'm working on a function that reduces pairs of elements if they meet some criteria.

For example, given an array: ["1", "2", "a", "b", "3", "4"] I want to transform it so that strings that represent numbers are combined with addition, and strings that represent letters are concatenated so the output would be: ["3" "ab" "7"].

The approach I've taken is to sort of gobble the array up from the head pair, which with the example above goes through the following steps:

(1, 2, a, b, 3, 4) // combine 1 and 2 ->
(3, a, b, 3, 4) // combine a and b ->
(3, ab, 3, 4) // combine 3 and 4 ->
(3, ab, 7)

I'm calling transform a 'knot' because I'm visualizing elements in the array being knotted together to unlimitedly shorten the sequence.

Is this a pattern that's known by some other name? Any suggestions other than knot that might be more descriptive (knit? squish?).

Here's the current approach in Swift, would be great to get any feedback on style, documentation, or algorithm here:

public extension Array {
 /// A `knot` is like a discriminating `reduce`.
 ///
 /// Knotting an array incrementally looks at the next pair of sequential elements, and attempts to use 
 /// a closure to reduce that pair of elements into a single element.
 ///
 /// Unlike `reduce` this closure can be failable, in which case the element is not reduced, but simply 
 /// appended to the results.
 ///
 /// - Note: Forward knots.
 /// If (A B C D) can be knotted successfully as (ABCD) through series of knots:
 /// (A B C D) -> (AB C D) -> (ABC D) -> (ABCD).
 ///
 /// It's possible that A and B **cannot** be knotted, but A and BC **can** be knotted to achieve the
 /// equivalent result:
 /// (A B C D) -> (A BC D) -> (ABC D) -> ABCD
 ///
 /// - Parameter forwardKnot: A flag to indicate if a forward-knot should be attempted if the initial knot 
 /// fails.
 ///
 /// - Parameter transform: A knotting closure. `transform` accepts a pair of elements from this sequence
 /// as its parameter and returns a transformed value of the same type if the pair should be combined, or
 /// nil if the element can't be combined.
 ///
 /// - Returns: An array containing the transformed elements of this sequence.
 func knot(forwards forwardKnot: Bool = false, 
 _ transform: ((Element, Element) -> Element?)) -> [Element] {
 var upcoming = self
 var knotted: [Element] = []
 knotted.reserveCapacity(count)
 while !upcoming.isEmpty {
 let next = upcoming.remove(at: 0)
 // first iteration - nothing to knot, just add next element
 guard let last = knotted.last else {
 knotted.append(next)
 continue
 }
 // attempt to knot
 if let knot = transform(last, next) {
 knotted[knotted.count-1] = knot
 }
 else {
 if forwardKnot, let ahead = upcoming.first, 
 let under = transform(next, ahead), 
 let over = transform(last, under) {
 upcoming.remove(at: 0)
 knotted[knotted.count-1] = over
 }
 // can't forward knot, just add the next element
 else {
 knotted.append(next)
 }
 }
 }
 return knotted
 }
}

Example usage:

func additiveKnot(left: String, right: String) -> String? {
 let left: Any = Int(left) ?? left
 let right: Any = Int(right) ?? right
 switch (left, right) {
 case let(left as String, right as String):
 // knot Strings by concatenating
 // "a", "b" => "ab"
 return left + right
 case let (left as Int, right as Int):
 // knot Ints by addition
 // 1, 2 => 3
 return String(left + right)
 default:
 return nil
 }
}
let values = ["1", "2", "a", "b", "3", "4"]
let knotted = values.knot(additiveKnot)
// 'knotted' == ["3", "ab", "7"]

Answer 1

Your code looks overall good to me and is correct, as far as I can see. Possible improvements:

• upcoming is a copy of the given array from which one or two elements are removed at the front in each iteration step. Removing the first element of an array moves all remaining elements to the front and is a O(N) operation. This can be improved by using an array slice instead:

  var upcoming = ArraySlice(self)
  

  Removing the first element of an array slice only adjusts the start index and is an O(1) operation.

  Then

   while !upcoming.isEmpty {
   let next = upcoming.remove(at: 0)
   ...
  }
  

  can be simplified to

   while let next = upcoming.popFirst() {
   ...
  }
  

• Append to the knotted array only "finalized" values which can not be combined with upcoming values anymore, and use a separate variable for the current value which is still a candidate for further combination. This allows to move the

   // first iteration - nothing to knot, just add next element
  

  check outside of the loop.

• Use elsif instead of a nested else { if .. } statement.

• Perhaps there is a reason for naming the variables over and under in the forward knot part, but I did not get that.

The method would then look like this:

func knot(forwards forwardKnot: Bool = false,
 _ transform: ((Element, Element) -> Element?)) -> [Element] {
 var upcoming = ArraySlice(self)
 // Set `current` to first element:
 guard var current = upcoming.popFirst() else { return [] }
 var knotted: [Element] = []
 knotted.reserveCapacity(count)
 // Iterate over all remaining elements:
 while let next = upcoming.popFirst() {
 if let knot = transform(current, next) {
 // Successful knot, update `current`.
 current = knot
 } else if forwardKnot,
 let ahead = upcoming.first,
 let nextTwo = transform(next, ahead),
 let knot = transform(current, nextTwo) {
 // Successful forward knot, update `current`. 
 current = knot
 upcoming.removeFirst()
 } else {
 // No knot. Append `current` to final array and make `next` the 
 // next candidate.
 knotted.append(current)
 current = next
 }
 }
 knotted.append(current)
 return knotted
}

Without the "forward knot" feature you could iterate over the array elements directly:

func knot(_ transform: ((Element, Element) -> Element?)) -> [Element] {
 guard var current = self.first else { return [] }
 var knotted: [Element] = []
 for elem in self.dropFirst() {
 if let knot = transform(current, elem) {
 current = knot
 } else {
 knotted.append(current)
 current = elem
 }
 }
 knotted.append(current)
 return knotted
}

---

The additiveKnot() function can be simplified, your code does

 String -> Any -> String
 String -> Int -> Any -> Int

conversions. You can do a pattern matching on Int(left) and Int(right) instead, this avoids all unnecessary type conversions and does not require Any at all.

The switch statement checks if Int(left) and Int(right) are both != nil (two integers), both == nil (two strings), or if the values are of "mixed type":

func additiveKnot(left: String, right: String) -> String? {
 switch (Int(left), Int(right)) {
 case let (leftInt?, rightInt?): // Both are integers
 return String(leftInt + rightInt)
 case (nil, nil): // None of them is an integer
 return left + right
 default: // Mixed case
 return nil
 }
}

Here leftInt? is a shortcut for the .some(leftInt) pattern.

• MathewS: Thank you! I really like all these changes, especially the current variable so that only finalized knots are added to the array. I need to spend more time with docs learning where there are O(1) opportunities. You're right about the over/under variable names. They're leftovers from when I was thinking about option to define a different closures for a 'forward knot'. Thanks again for taking time to write this, I’ve learnt a lot!
• Martin R: @MathewS: You are welcome!