去往js函数式编程(7)

管道和组合

  管道和组合是一种技术，用于设置函数以便它们按顺序工作，使一个函数的输出称为下一个函数的输入。在 linux 中，执行一个命令并将其输出作为第二个命令的输入，而第二个命令的输出又成为第三个命令的输入，依此类推，这被称为管道。

const markers = [
  { name: 'AR', lat: -34.6, lon: -58.4 },
  { name: 'BO', lat: -16.5, lon: -68.1 },
  { name: 'BR', lat: -15.8, lon: -47.9 },
  { name: 'CL', lat: -33.4, lon: -70.7 },
  { name: 'CO', lat: 4.6, lon: -74.0 },
  { name: 'EC', lat: -0.3, lon: -78.6 },
  { name: 'PE', lat: -12.0, lon: -77.0 },
  { name: 'PY', lat: -25.2, lon: -57.5 },
  { name: 'UY', lat: -34.9, lon: -56.2 },
  { name: 'VE', lat: 10.5, lon: -66.9 }
]

  我们之前计算过的平均纬度和经度。我们的解决方案是:从每个点中提取纬度，使用函数创建一个纬度函数，将数组传递给我们的计算平均值函数。

const average = (arr) => arr.reduce(sum, 0) / arr.length
const getField = (attr) => (obj) => obj[attr]
const myMap = curry(flipTwo(demethodize(Array.prototype.map)))

const getLat = curry(getField)('lat')
const getAllLats = curry(myMap)(getLat)

let averageLat = pipeline(getAllLats, average)

  无参数风格(Pointfree style)。当你将函数连接在一起，你不需要任何中间变量来保存结果，这些结果将成为下一个函数的参数，它们是隐含的。你写出不提及参数的函数，这被称为 pointfree style.

链式调用

  当你处理对象或数组时，有另一种将多个调用链接起来的方法：使用链式调用。我们看一个常见的流畅，链式的 API 示例，然后考虑如何自己实现这种方法。

var node = svg
  .selectAll('.node')
  .data(pack(root).leaves())
  .enter()
  .append('g')
  .attr('class', 'node')
  .attr('transform', function (d) {
    return 'translate(' + d.x + ',' + d.y + ')'
  })

  每个放啊都在前一个对象上操作，并提供一个新对象的访问，后续的方法调用将应用于该对象。

递归

  递归是函数式编程的关键技术。计算机科学的一个基本事实是，无论你用递归做什么，都可以用循环来完成，反之亦然。

  什么是递归，简单的定义是函数一遍又一遍地调用自身，直到不再调用为止。递归可以解决多种问题：数学定义，斐波那契或数的阶乘。数据结构相关的算法。递归解决问题的关键是假设你已经拥有一个能够完成所需任务的函数，并正常调用它。另一方面，如果你试图在脑海中思考递归调用的工作原理并尝试跟踪思路的流程，你可能会迷失方向。所以你需要做以下几点：假设你已经有一个适合解决问题的函数。看看如何通过解决一个更小的问题来解决大问题。使用第一步中想象的函数来解决问题。确定你的基本情况是什么。确保它们足够简单，可以直接解决，而不需要进行更多的调用。

const search = (arr, key) => {
  if (arr.length == 0) {
    return false
  } else if (arr[0] == key) {
    return true
  } else {
    return search(arr.slice(1), key)
  }
}
// 我们可以稍微缩短搜索函数
const search2 = (arr, key) =>
  arr.length === 0 ? false : arr[0] === key || search2(arr.slice(1), key)

// 再进一步
// 但是并不真的建议使用这种方式编写函数，把它看作对某些开发者倾向的一种警告
// 他们试图追求最紧凑，最简短的解决方案，而不关心清晰度！
const search3 = (arr, key) =>
  arr.length && (arr[0] === key || search3(arr.slice(1), key))

  另一个经典的例子涉及高效的方式计算数字的幂。如果你想计算 2 的 13 次方，你可以通过进行 12 次乘法来实现。我们可以用几行代码来实现这个递归算法。

const powerN = (base, power) => {
  if (power === 0) {
    return 1
  } else if (power % 2) {
    // 奇数
    return base * powerN(base, power - 1)
  } else {
    return powerN(base * base, power / 2)
  }
}

  我们考虑一个经典的谜题，这个谜题涉及到一个印度的寺庙，有 3 根柱子和 64 个直径递减的金盘。僧侣们必须按照两个规则将盘子从第一根柱子移动到最后一根柱子；一次只能移动一个盘子，较大的盘子永远不能放在较小的盘子上面。根据传说，当这 64 个盘子移动完成时，世界将终结。这个谜题通常被称为汉诺塔。

function hanoi(n, source, target, auxiliary) {
  if (n > 0) {
    // 将 n-1 个盘子从源柱移动到辅助柱
    hanoi(n - 1, source, auxiliary, target)

    // 将第 n 个盘子从源柱移动到目标柱
    console.log(`Move disk ${n} from ${source} to ${target}`)

    // 将 n-1 个盘子从辅助柱移动到目标柱
    hanoi(n - 1, auxiliary, target, source)
  }
}

// 示例调用
hanoi(3, 'A', 'C', 'B')

  使用分而治之策略还可以解决其他类型的问题。例如，合并排序是一种经典的分而治之算法。它将一个大的排序问题分解为两个较小的排序问题，然后将这些子问题的解合并起来以获得最终的有序结果。

const mergeSort = (arr) => {
  if (arr.length <= 1) {
    return arr
  }

  const mid = Math.floor(arr.length / 2)
  const left = arr.slice(0, mid)
  const right = arr.slice(mid)

  const sortedLeft = mergeSort(left)
  const sortedRight = mergeSort(right)

  return merge(sortedLeft, sortedRight)
}

const merge = (arr1, arr2) => {
  let result = []
  let i = 0
  let j = 0
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      result.push(arr1[i])
      i++
    } else {
      result.push(arr2[j])
      j++
    }
  }

  while (i < arr1.length) {
    result.push(arr1[i])
    i++
  }

  while (j < arr2.length) {
    result.push(arr2[j])
    j++
  }

  return result
}

  第三种通用策略，动态规划，假设你需要解决许多较小的问题，但不是每次都使用递归，而是依赖于你之前存储的已找到的解决方案..也就是记忆化。给一定数量的美元和现有票面值的列表，计算我们可以用不同的票面组合多少种不同的方式支付这笔金额的美元。假设你可以无限次使用每张钞票。

const makeChange = (n, bills) => {
  if (n < 0) {
    return 0
  } else if (n == 0) {
    return 1
  } else if (bills.length == 0) {
    // 在此情况下，n>0
    return 0
  } else {
    return makeChange(n, bills.slice(1)) + makeChange(n - bills[0], bills)
  }
}

console.log(makeChange(64, [100, 50, 20, 10, 5, 2, 1]))

Mapping 和 filtering

  在很大程度上，map 和 filter 相似，因为两者都意味着遍历数组中的所有元素，并对每个元素应用回调函数以生成输出。我们自己写一个 map 版本：

const mapR = (arr, cb) =>
  arr.length === 0 ? [] : [cb(arr[0])].concat(mapR(slice(1), cb))

const mapR2 = (arr, cb, i = 0, orig = arr) =>
  arr.length == 0
    ? []
    : [cb(arr[0], i, orig)].concat(mapR2(arr.slice(1), cb, i + 1, orig))

  当你使用递归而不是迭代时，你无法访问索引，因此，如果你需要它，你就不得不自己生成它。然而，函数中有额外的参数并不好；开发人员可能会不小心提供它们，那么结果将是不可预测的。

const mapR3 = (org, cb) => {
  const mapLoop = (arr, i) =>
    arr.length == 0
      ? []
      : [cb[(arr[0], i, orig)]].concat(mapR3(arr.slice(1), vb, i + 1, orig))
  return mapLoop(orig, 0)
}

  延续传递方式(Continuation Passing Style,CPS)中，我们可以通过使用一个延续来将递归调用转换为尾调用。在函数时编程中，延续是表示进程状态并允许处理继续的东西。我们从代码看起。

function getTime() {
  return new Date().toTimeString()
}

console.log(getTime())

function getTime2(cont) {
  return cont(new Date().toTimeString())
}

getTime2(console.log)

  有什么区别？关键在于我们可以应用这种机制，将递归调用转换为尾调用，因为之后的所有代码都会在递归调用本身中提供。为了清楚起见，让我们重新审视一下阶乘函数的一个版本，该版本明确表示我们没有使用尾调用。

function fact2(n) {
  if (n === 0) {
    return 1
  } else {
    const aux = fact2(n - 1)
    return n * aux
  }
}

function factC(n, cont) {
  if (n == 0) {
    return cont(1)
  } else {
    return factC(n - 1, (x) => cont(n * x))
  }
}