Reduce reduce with reduced

Check out part 1

Let’s play some more code golf!

function some(pred, xs) {
  for (let i = 0; i < xs.length; i++) {
    if (pred(xs[i], i)) {
      return true
    }
  }

  return false
}

function every(pred, xs) {
  for (let i = 0; i < xs.length; i++) {
    if (!pred(xs[i], i)) {
      return false
    }
  }

  return true
}

function reduce(fn, xs, init) {
  let result = init

  for (let i = 0; i < xs.length; i++) {
    result = fn(result, xs[i], i)
  }

  return result
}

some returns true when a predicate returns true at least one time , while iterating over a list. every returns true when a predicate always returns true. some and every can be implemented with reduce:

function some(pred, xs) {
  return reduce((acc, item, i) => acc || pred(item, i), xs, false)
}

function every(pred, xs) {
  return reduce((acc, item, i) => acc && pred(item, i), xs, true)
}

function reduce(fn, xs, init) {
  let result = init

  for (let i = 0; i < xs.length; i++) {
    result = fn(result, xs[i], i)
  }

  return result
}

While this is shorter and for the trained eye easier to read. It has no early return. When a predicate in some returns true the list will still be traversed completely. In order to improve this, we need to extent the functionality of reduce:

function reduce(fn, xs, init) {
  let result = init

  for (let i = 0; i < xs.length; i++) {
    result = fn(result, xs[i], i)
    if (isReduced(result)) return getReduced(result)
  }

  return result
}

Functions that are passed into reduce now have the ability to early return the reduce function. Those functions communicate their desire for an early return, by decorating their return-value in a specific way.

function some(pred, xs) {
  return reduce(
    (_, item, i) => (pred(item, i) ? reduced(true) : false),
    xs,
    false
  )
}

function every(pred, xs) {
  return reduce(
    (_, item, i) => (pred(item, i) ? true : reduced(false)),
    xs,
    true
  )
}

reduced wraps the value in some way, so that it can be detected by isReduced. When some discovers a truthy value, it returns this wrapped value. Signaling to the outside reduce function that it should return early. reduced, isReduced and getReduced could be implemented like this:

const reduced = x => ({
  "@@transducer/value": x,
  "@@transducer/reduced": true,
})
const isReduced = x => x?.["@@transducer/reduced"]
const getReduced = x => x?.["@@transducer/value"]

Why I chose to prefix the props with @@transducer is a topic for another time. Here is the full code:

function some(pred, xs) {
  return reduce(
    (_, item, i) => (pred(item, i) ? reduced(true) : false),
    xs,
    false
  )
}

function every(pred, xs) {
  return reduce(
    (_, item, i) => (pred(item, i) ? true : reduced(false)),
    xs,
    true
  )
}

function reduce(fn, xs, init) {
  let result = init

  for (let i = 0; i < xs.length; i++) {
    result = fn(result, xs[i], i)
    if (isReduced(result)) return getReduced(result)
  }

  return result
}

const reduced = x => ({
  "@@transducer/value": x,
  "@@transducer/reduced": true,
})
const isReduced = x => x?.["@@transducer/reduced"]
const getReduced = x => x?.["@@transducer/value"]

Well we did not win that much in terms of LoC, but this early return strategy can be used in other list operations:

function find(pred, xs) {
  for (let i = 0; i < xs.length; i++) {
    if (pred(xs[i], i)) {
      return xs[i]
    }
  }

  return undefined
}

function indexOf(target, xs) {
  for (let i = 0; i < xs.length; i++) {
    if (xs[i] === target) {
      return i
    }
  }

  return -1
}

function includes(target, xs) {
  for (let i = 0; i < xs.length; i++) {
    if (xs[i] === target) {
      return true
    }
  }

  return false
}

function findIndex(pred, xs) {
  for (let i = 0; i < xs.length; i++) {
    if (pred(xs[i], i)) {
      return i
    }
  }

  return -1
}

Use reduce:

function find(pred, xs) {
  return reduce(
    (_, item, i) => (pred(item, i) ? reduced(item) : undefined),
    xs,
    undefined
  )
}

function indexOf(target, xs) {
  return reduce((_, item, i) => (target === item ? reduced(i) : -1), xs, -1)
}

function includes(target, xs) {
  return reduce(
    (_, item) => (target === item ? reduced(true) : false),
    xs,
    false
  )
}

function findIndex(pred, xs) {
  return reduce((_, item, i) => (pred(item, i) ? reduced(i) : -1), xs, -1)
}

A lot of list operations can be expressed with reduce. Those operations have one thing in common: a collection of items gets traversed, each item is examined to produce a result. That is the concept of reduce. However, the current implementation of this concept is unnecessary specific. Notice that even though reduce seems to be extremely generic, it can still only be used with one kind of ‘collection’: the list. The shown version does not even work with iterators. Or with anything else that we might want to use map and filter on (Maybe-Constructs or Observables, etc.). For each other type of ‘collection’ we would need to reimplement all of those operations again.

Can we abstract reduce even further?

Yes we can, by using so-called transducers. Coming soon…