I (roughly) defined (almost) every array method using recursion 😂
Tags: javascript, webdev, recursion
Published: 2021-04-30 12:07:51

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]`

```jsx
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)]
}
```

Note: we ignore the 2nd and 3rd arguments of `Array.from`. ([see docs](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/from))

# `Array.of`

```jsx
const arrayOf = (...xs) => {
  if (xs.length <= 0) return []
  const [head, ...tail] = xs
  return [head, ...arrayOf(...tail)]
}
```

# `Array.prototype.concat`

```jsx
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)
}
```

Note: assuming concat only takes in 2 parameters

# `Array.prototype.entries`

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

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

# `Array.prototype.every`

```jsx
const every = (xs, predicate) => {
  if (xs.length <= 0) return true
  const [head, ...tail] = xs
  return predicate(head) && every(tail, predicate)
}
```

# `Array.prototype.fill`

```jsx
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)]
}
```

# `Array.prototype.filter`

```jsx
const filter = (xs, predicate) => {
  if (xs.length <= 0) return []
  const [head, ...tail] = xs
  return [
    ...(predicate(head) ? [head] : []),
    ...filter(tail, predicate)
  ]
}
```

# `Array.prototype.find`

```jsx
const find = (xs, predicate) => {
  if (xs.length <= 0) return undefined
  const [head, ...tail] = xs
  if (predicate(head)) return head
  return find(tail, predicate)
}
```

# `Array.prototype.findIndex`

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

# `Array.prototype.forEach`

```jsx
const forEach = (xs, fn) => {
  if (xs.length <= 0) return
  const [head, ...tail] = xs
  fn(head)
  forEach(tail, fn)
}
```

notes: ignoring index

# `Array.prototype.includes`

```jsx
const includes = (xs, predicate) => {
  if (xs.length <= 0) return false
  const [head, ...tail] = xs
  const predicate(head) || includes(tail, predicate)
}
```

# `Array.prototype.indexOf`

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

# `Array.prototype.join`

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

# `Array.prototype.map`

```jsx
const map = (xs, fn) => {
  if (xs.length <= 0) return []
  const [head, ...tail] = xs
  return [fn(head), ...map(tail, fn)]
}
```

# `Array.prototype.reduce`

```jsx
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))
}
```

# `Array.prototype.reverse`

```jsx
const reverse = (xs) => {
  if (xs.length <= 0) return []
  const [head, ...tail] = xs
  return [...reverse(xs), head]
}
```

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

```jsx
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)]
}
```

# `Array.prototype.some`

```jsx
const some = (xs, predicate) => {
  if (xs.length <= 0) return false
  const [head, ...tail] = xs
  return predicate(head) || some(tail, predicate)
}
```