Lambda Academy

JavaScript 惰性求值的一种实现

August 25, 2018

在学习 Haskell 时,我遇到了这种写法:

sum (takeWhile (<10000) (filter odd (map (^2) [1..])))

这段代码的意思是,找出自然整数中小于 10000 的同时是乘方数和奇数的数字,再把这些数加总。由于 Haskell 的懒运算特性,上面的程序并不会立马生成从 1 到 无限大的自然数列表,而是会等待 takeWhile 指令,再生成符合条件的列表。如果用 JS 来写,很难写出这么简洁高表达性的代码。一个可能的思路就是写个 while 循环,然后找到符合条件的数进行加总。这个比较简单,我就不演示了。

但是如果我们要用高阶函数来模拟 Haskell 的写法,就要想个办法实现懒运算了。提到懒,首先想到的就是 Iterator 。没人踢它一脚告诉它 next(),它会一直坐那儿不动的。现在我们就来用 Iterator 来实现一个懒运算。

首先定义一个生成从 1 到无穷大自然数的 generator :

const numbers = function*() {
  let i = 1
  while (true) {
    yield i++
  }
}

由于只有在 generator 执行后生成的 iterator 上执行 next() 方法,yield 才会执行,所以我们要做的主要工作就是实现不同的 next 方法,达到目的。

我们需要先创建一个工厂函数 LazyLazy 封装了我们的各种目标操作 :

const Lazy = iterator => {
  const next = iterator.next.bind(iterator)
    const map = () => {}
    const filter = () => {}
    const takeWhile = () => {}
    return {
      next,
      map,
      filter,
      takeWhile,
    }

我们先实现 map 方法,它会把每次 next 返回的值根据提供的回调函数进行修改:

const map = f => {
  const modifiedNext = () => {
    const item = next()
    const mappedValue = f(item.value)
    return {
      value: mappedValue,
      done: item.done,
    }
  }
  const newIter = { ...iterator, next: modifiedNext }
  return Lazy(newIter)
}

再定义 filter 方法,它会让 next 只返回符合判断条件的值:

const filter = predicate => {
  const modifiedNext = () => {
    while (true) {
      const item = next()
      if (predicate(item.value)) {
        return item
      }
    }
  }
  const newIter = { ...iterator, next: modifiedNext }
  return Lazy(newIter)
}

最后,定义 takeWhile,它会限制 next 执行的条件,一旦条件不满足,则停止执行 next 并返回历史执行结果:

const takeWhile = predicate => {
  const result = []
  let value = next().value
  while (predicate(value)) {
    result.push(value)
    value = next().value
  }
  return result
}

主要的方法都定义完了,现在把它们合并起来:

const Lazy = iterator => {
  const next = iterator.next.bind(iterator)

  const map = f => {
    const modifiedNext = () => {
      const item = next()
      const mappedValue = f(item.value)
      return {
        value: mappedValue,
        done: item.done,
      }
    }
    const newIter = { ...iterator, next: modifiedNext }
    return Lazy(newIter)
  }

  const filter = predicate => {
    const modifiedNext = () => {
      while (true) {
        const item = next()
        if (predicate(item.value)) {
          return item
        }
      }
    }
    const newIter = { ...iterator, next: modifiedNext }
    return Lazy(newIter)
  }

  const takeWhile = predicate => {
    const result = []
    let value = next().value
    while (predicate(value)) {
      result.push(value)
      value = next().value
    }
    return result
  }

  return Object.freeze({
    map,
    filter,
    takeWhile,
    next,
  })
}

const numbers = function*() {
  let i = 1
  while (true) {
    yield i++
  }
}

现在用我们写的 Lazynumbers 函数来实现文章开头的 Haskell 代码:

Lazy(numbers())
  .map(x => x ** 2)
  .filter(x => x % 2 === 1)
  .takeWhile(x => x < 10000)
  .reduce((x, y) => x + y)
// => 16650

参考:


Lambda Academy

Lei Huang

这个博客我主要分享函数式编程和前端开发。我还有一个英文网站