用 JavaScript 学习函数式编程？

可能是因为之前看了几场 RacketCon，今天 YouTube 给我推荐了「用 JavaScript 学习函数式编程」这个演讲。该演讲的时长不足半个小时，但是函数式编程中的一些重要概念都有讲到，因此非常适合作为入门教程。演讲者 Anjana Vakil 的 GitHub 上还有一个工作坊项目 functional-workshop，可以作为配套练习。

下面来写几个简单的函数玩一玩。

链表

JavaScript 没有内置的链表，暂且用数组代替一下。

const length = (lst) => lst.length

const isEmpty = (lst) => lst.length === 0

const first = (lst) => lst[0]

const rest = (lst) => lst.slice(1)

const slice = (lst, begin, end = length(lst)) => lst.slice(begin, end)

const append = (...lsts) => {
  if (isEmpty(lsts)) {
    return lsts
  } else {
    return [...first(lsts), ...append(...rest(lsts))]
  }
}

const cons = (item, lst) => append([item], lst)

辅助函数

const map = (mappingFn, lst) => {
  if (isEmpty(lst)) {
    return lst
  } else {
    return cons(mappingFn(first(lst)), map(mappingFn, rest(lst)))
  }
}

const reduce = (reducerFn, initialValue, lst) => {
  if (isEmpty(lst)) {
    return initialValue
  } else {
    return reduce(reducerFn, reducerFn(initialValue, first(lst)), rest(lst))
  }
}

const filter = (predicateFn, lst) => {
  if (isEmpty(lst)) {
    return lst
  } else if (predicateFn(first(lst))) {
    return cons(first(lst), filter(predicateFn, rest(lst)))
  } else {
    return filter(predicateFn, rest(lst))
  }
}

选择排序

const selectionSort = (lst) => {
  if (isEmpty(lst)) {
    return lst
  } else {
    const minItem = reduce(Math.min, first(lst), rest(lst))
    return append(
      filter(x => x === minItem, lst),
      selectionSort(filter(x => x !== minItem, lst))
    )
  }
}

插入排序

const insertionSort = (lst) => {
  const insert = (lst, item) => {
    if (isEmpty(lst)) {
      return [item]
    } else if (first(lst) < item) {
      return cons(first(lst), insert(rest(lst), item))
    } else {
      return cons(item, lst)
    }
  }

  if (isEmpty(lst)) {
    return lst
  } else {
    return insert(insertionSort(rest(lst)), first(lst))
  }
}

归并排序

const mergeSort = (lst) => {
  const merge = (lhs, rhs) => {
    if (isEmpty(lhs)) {
      return rhs
    } else if (isEmpty(rhs)) {
      return lhs
    } else if (first(lhs) < first(rhs)) {
      return cons(first(lhs), merge(rest(lhs), rhs))
    } else {
      return cons(first(rhs), merge(lhs, rest(rhs)))
    }
  }

  if (length(lst) <= 1) {
    return lst
  } else {
    const mid = Math.ceil(length(lst) / 2)
    return merge(
      mergeSort(slice(lst, 0, mid)),
      mergeSort(slice(lst, mid))
    )
  }
}

（不快速的）快速排序

const quickSort = (lst) => {
  if (length(lst) <= 1) {
    return lst
  } else {
    const pivot = first(lst)
    return append(
      quickSort(filter(x => x < pivot, lst)),
      filter(x => x === pivot, lst),
      quickSort(filter(x => x > pivot, lst))
    )
  }
}