DEV Community

Cover image for I (roughly) defined (almost) every array method using recursion ๐Ÿ˜‚
YCM Jason
YCM Jason

Posted on

I (roughly) defined (almost) every array method using recursion ๐Ÿ˜‚

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

Top comments (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