# Transformations an array, combination of between map and reduce

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 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):
// 1, 2 => 3
return String(left + right)

default:
return nil
}
}

let values = ["1", "2", "a", "b", "3", "4"]
// 'knotted' == ["3", "ab", "7"]


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

• 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! – MathewS Dec 15 '16 at 17:04
• @MathewS: You are welcome! – Martin R Dec 15 '16 at 19:32