DEV Community

loading...
Cover image for I (roughly) defined (almost) every array method using recursion 😂

I (roughly) defined (almost) every array method using recursion 😂

ycmjason profile image Jason Yu ・3 min read

So... I have decided to define every array methods using recursion. (I haven't really tested all of them... so there might be some errors.)

Also, I only defined the "essence" of most methods. Didn't follow the complete spec for most.

Why?

Why not?

How is this useful?

It is not.

Array.from

Array.from takes in two kinds of objects.

  1. Array-like objects that have a length property with zero-indexed elements
  2. Iterable objects that have an iterator at [Symbol.iterator]
const arrayFrom = (o) => {
  if ('length' in o) return arrayFromArrayLike(o)
  if (Symbol.iterator in o) return arrayFromIterator(o[Symbol.iterator]())
  return []
}

const arrayFromArrayLike = (arrayLikeObject) => {
  if (arrayLikeObject.length <= 0) return []
  return [
    ...arrayFromArrayLike({
      ...arrayLikeObject,
      length: arrayLikeObject.length - 1,
    }),
    arrayLikeObject[arrayLikeObject.length - 1],
  ]
}

const arrayFromIterator = (iterator) => {
  const { value, done } = iterator.next()
  if (done) return []
  return [value, ...arrayFromIterator(iterator)]
}
Enter fullscreen mode Exit fullscreen mode

Note: we ignore the 2nd and 3rd arguments of Array.from. (see docs)

Array.of

const arrayOf = (...xs) => {
  if (xs.length <= 0) return []
  const [head, ...tail] = xs
  return [head, ...arrayOf(...tail)]
}
Enter fullscreen mode Exit fullscreen mode

Array.prototype.concat

const concat = (xs, ...arrays) => {
  if (arrays.length <= 0) return xs
  const [ys, ...restArrays] = arrays
  if (ys.length <= 0) return concat(xs, ...restArrays)
  const [head, ...tail] = ys
  return concat([...xs, head], tail, ...restArrays)
}
Enter fullscreen mode Exit fullscreen mode

Note: assuming concat only takes in 2 parameters

Array.prototype.entries

function* entries(xs, i = 0) {
  if (xs.length <= 0) return
  const [head, ...tail] = xs
  yield [i, head]
  yield* entries(tail, i + 1)
}
Enter fullscreen mode Exit fullscreen mode

note: i does not exist in Array.prototype.entries

Array.prototype.every

const every = (xs, predicate) => {
  if (xs.length <= 0) return true
  const [head, ...tail] = xs
  return predicate(head) && every(tail, predicate)
}
Enter fullscreen mode Exit fullscreen mode

Array.prototype.fill

const fill = (xs, k, start = 0, end = xs.length + 1) => {
  if (xs.length <= 0) return []
  const [head, ...tail] = xs
  if (start > 0) return [head, ...fill(tail, k, start - 1, end - 1)]
  return fillFromStart([head, ...tail], k, end)
}

const fillFromStart = (xs, k, end = xs.length + 1) => {
  if (xs.length <= 0) return []
  if (end <= 0) return xs
  const [_, ...tail] = xs
  return [k, ...fillFromStart(tail, k, end - 1)]
}
Enter fullscreen mode Exit fullscreen mode

Array.prototype.filter

const filter = (xs, predicate) => {
  if (xs.length <= 0) return []
  const [head, ...tail] = xs
  return [
    ...(predicate(head) ? [head] : []),
    ...filter(tail, predicate)
  ]
}
Enter fullscreen mode Exit fullscreen mode

Array.prototype.find

const find = (xs, predicate) => {
  if (xs.length <= 0) return undefined
  const [head, ...tail] = xs
  if (predicate(head)) return head
  return find(tail, predicate)
}
Enter fullscreen mode Exit fullscreen mode

Array.prototype.findIndex

const findIndex - (xs, predicate) => {
  if (xs.length <= 0) return -1
  const [head, ...tail] = xs
  if (predicate(head)) return 0
  return findIndex(tail, predicate) + 1
}
Enter fullscreen mode Exit fullscreen mode

Array.prototype.forEach

const forEach = (xs, fn) => {
  if (xs.length <= 0) return
  const [head, ...tail] = xs
  fn(head)
  forEach(tail, fn)
}
Enter fullscreen mode Exit fullscreen mode

notes: ignoring index

Array.prototype.includes

const includes = (xs, predicate) => {
  if (xs.length <= 0) return false
  const [head, ...tail] = xs
  const predicate(head) || includes(tail, predicate)
}
Enter fullscreen mode Exit fullscreen mode

Array.prototype.indexOf

const indexOf = (xs, x) => {
  if (xs.length <= 0) return -1
  const [head, ...tail] = xs
  if (head === x) return 0
  return indexOf(tail, x) + 1
}
Enter fullscreen mode Exit fullscreen mode

Array.prototype.join

const join = (xs, separator = ',') => {
  if (xs.length <= 0) return ''
  const [head, ...tail] = xs
  return `${head}${separator}${join(tail, separator)}`
}
Enter fullscreen mode Exit fullscreen mode

Array.prototype.map

const map = (xs, fn) => {
  if (xs.length <= 0) return []
  const [head, ...tail] = xs
  return [fn(head), ...map(tail, fn)]
}
Enter fullscreen mode Exit fullscreen mode

Array.prototype.reduce

const reduce = (xs, fn, acc) => {
  if (xs.length <= 0) {
    if (typeof acc === 'undefined') {
      throw new TypeError('Reduce of empty array with no initial value')
    } else {
      return acc
    }
  }

  const [head, ...tail] = xs
  if (typeof acc === 'undefined') return reduce(tail, fn, head)
  return reduce(tail, fn, fn(acc, head))
}
Enter fullscreen mode Exit fullscreen mode

Array.prototype.reverse

const reverse = (xs) => {
  if (xs.length <= 0) return []
  const [head, ...tail] = xs
  return [...reverse(xs), head]
}
Enter fullscreen mode Exit fullscreen mode

Array.prototype.slice

Slice is a surprisingly annoying one to define. It needs to deal with negative indices, but you can't simply "mod" the numbers...

const slice = (xs, start = 0, end = xs.length) => {
  if (xs.length <= 0) return []
  if (start < 0) return slice(xs, Math.max(0, start + xs.length), end)
  if (end < 0) return slice(xs, start, Math.max(0, end + xs.length))
  const [head, ...tail] = xs

  if (end <= start) return []
  if (start > 0) return slice(tail, start - 1, end - 1)

  return [head, ...slice(tail, 0, end - 1)]
}
Enter fullscreen mode Exit fullscreen mode

Array.prototype.some

const some = (xs, predicate) => {
  if (xs.length <= 0) return false
  const [head, ...tail] = xs
  return predicate(head) || some(tail, predicate)
}
Enter fullscreen mode Exit fullscreen mode

Discussion (1)

Collapse
aminnairi profile image
Amin

You got me at

How is this useful ? It's not.

Here is my proposal for Array.prototype.flat.

const flatten = (target, level = 1) => {
  if (!Array.isArray(target)) {
    return target;
  }

  if (target.length === 0) {
    return [];
  }

  const [item, ...remainingItems] = target;

  if (!Array.isArray(item) || level === 0) {
    return [item, ...flatten(remainingItems, level)];
  }

  return [...flatten(item, level - 1), ...flatten(remainingItems, level)];
};

console.log(flatten([1, 2, 3, [4, 5, [6, 7]]]));
// [1, 2, 3, 4, 5, [6, 7]]

console.log(flatten([1, 2, 3, [4, 5, [6, 7]]], Infinity));
// [1, 2, 3, 4, 5, 6, 7]
Enter fullscreen mode Exit fullscreen mode
Forem Open with the Forem app