在 js 中使用 generator 模拟 do 语法

该特性仅供玩耍，有诸多限制，且在 Typescript 中不可用

Haskell 的 do 语法糖用于将 Monad 的组合计算扁平化，下面是一个对 List 的组合计算，以及在 js 中的等价代码：

do
  a <- [1, 2, 3]
  b <- [2, 3, 4]
  return $ a + b

[1, 2, 3].flatMap(a => 
  [2, 3, 4].flatMap(b => 
    [a + b])) // return 函数对 List 即为 x => [x]

在编写这种麻烦的嵌套代码的时候，总幻想着有没有方法将其扁平化以方便编写和阅读（确实有，见https://gcanti.github.io/fp-ts/guides/do-notation.html）；最近发现 js 的 generator 能够去模拟 do 语法，这里做一下记录。

generator 既能让它往外输出值，也能给它喂值，这里利用后者：

function* gen() {
  const a = yield
  const b = yield
  return a + b 
}

const g = gen()
g.next() // 第一次执行 next，使开始执行，在第一个 yield 阻塞
g.next(1) // 喂一个值，继续执行到第二个 yield
const res = g.next(2) // 再喂一个值，这时走到了 return，可以直接拿到返回值了
console.log(res) // { value: 3, done: true }

考虑下面 Haskell 代码：

do
  a <- [1, 2, 3]
  b <- [2, 3, 4]
  [a + b, a * b]

其可以描述为，对任意[1, 2, 3]中的值 a，对任意[1, 2, 3]中的值 b，获取所有 a+b 和 a*b 的值，将所有结果组成列表，最后结果为[1 + 2, 1 * 2, 1 + 3, 1 * 3, 1 + 4, 1 * 4, 2 + 2, 2 * 2, 2 + 3, 2 * 3, 2 + 4, 2 * 4, 3 + 2, 3 * 2, 3 + 3, 3 * 3, 3 + 4, 3 * 4]；

如何做到这样呢？显然我们只需要获取[1, 2, 3]和[2, 3, 4]的笛卡尔积即可，然后对结果集合中的每个值，都去创建 generator 并把值喂给他。一个例子见下面：

function* gen() {
  const a = yield
  const b = yield
  return [a + b] // do 的返回值是上下文中的，所以这里（及之后都）用数组形式
}

// 首先构造 [1, 2, 3] 和 [2, 3, 4] 的笛卡尔积
const allInputs = [1, 2, 3].flatMap(i => 
  [2, 3, 4].map(j => {
    return [i, j]
  }))

// 对每个笛卡尔积，将其
allInputs.flatMap(([a, b]) => {
  const g = gen()
  g.next() 
  // 下面的代码可以抽象成使用 for 的形式去适配更多个 yield
  g.next(a)
  return g.next(b).value
}) // [ 3, 4, 5, 4, 5, 6, 5, 6, 7 ]

但显然 yield 不一定只有两个，我们需要支持任意个 yield 的情况，因此根据需求，这里编写一个获取任意数量列表的笛卡尔积的函数：

// crossJoin() = []
// crossJoin([1, 2, 3]) = [[1], [2], [3]]
// crossJoin([1, 2], [3, 4, 5]) = [ [1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5] ]
function crossJoin(...arrs) {
  if (arrs.length === 0) return []
  if (arrs.length === 1) return arrs[0].map(i => [i])
  const [x, ...xs] = arrs
  const lasts = crossJoin(...xs)
  return x.flatMap(i => lasts.map(js => [i, ...js]))
}

然后就可以做抽象了：

function listDo(generator, ...arrs) {
    return crossJoin(...arrs).flatMap(elems => {
        const g = generator()
        g.next()
        for(let i = 0; i < elems.length - 1; i++) {
            g.next(elems[i])
        }
        return g.next(elems[elems.length - 1]).value
    })
}

玩耍一下：

listDo(function*(){
    const a = yield
    const b = yield
    const sum = a + b
    if (sum % 2 === 0) return [] // 筛选掉结果的所有偶数
    return [sum]
}, [1, 2, 3], [2, 3, 4]) // [ 3, 5, 5, 5, 7 ]

再来考虑另一个典型的 Monad——Maybe，简单抽象一波并实现 map 和 flatMap：

class Maybe {
    constructor(value, tag) {
        this.value = value
        this.tag = tag
    }
    static of(value) {
        if (value === null || value === undefined) {
            return Maybe.Nothing()
        }
        return Maybe.Just(value)
    }
    static Just(value) {
        if (value === null || value === undefined) 
            throw new Error("?")
        return new Maybe(value, "Just")
    }
    static Nothing() {
        return new Maybe(undefined, "Nothing")
    }
    match(onJust, onNothing) {
        if (this.tag === "Just") return onJust(this.value)
        return onNothing()
    }
    flatMap(f) {
        return this.match( x => f(x), () => this )
    }
    map(f) {
        return this.match( x => Maybe.of(f(x)), () => this )
    }
}

考虑下面的 Haskell 代码：

do
  a <- Just 1
  b <- Just 2
  return $ a + b

对应的 generator 和 flatMap 的形式是：

Maybe.Just(1).flatMap(a => 
  Maybe.Just(2).flatMap(b =>
    Maybe.Just(a + b))) // // return 函数对 Maybe 即为 Just

function* gen() {
  const a = yield
  const b = yield
  return Maybe.Just(a + b)
}

那么，如何去使用这个 generator 呢？考虑 Maybe 的特性——这里有两个 Maybe 值，其中任何一个为 Nothing 时，结果就为 Nothing；若两个都为 Just，则我们把它们的值取出来，应用给这个 generator，具体流程如下（注意该代码与上面数组这样操作的异同）：

const input = Maybe.Just(1).flatMap(i => 
  Maybe.Just(2).map(j => {
    return [i, j]
  })) // 得到 Just([1, 2])

allInputs.flatMap(([a, b]) => {
  const g = gen()
  g.next() 
  g.next(a)
  return g.next(b).value
}) 

于是和数组一样的问题——如果有多个 yield 怎么办呢？我们需要某种方法去接受一个Array<Maybe<A>>，返回一个Maybe<Array<A>>，它的实现和数组的实现基本相同：

// 容易注意到，这就是 sequence 的定义；于是，嵌套列表的 sequence 的行为就是对其中所有子列表做笛卡尔积喽？
function sequenceMaybe(...maybes) {
    if (maybes.length === 0) return Maybe.Just([])
    if (maybes.length === 1) return maybes[0].map(x => [x])
    const [x, ...xs] = maybes
    const lasts = sequenceMaybe(...xs)
    return x.flatMap(i => lasts.map(js => [i, ...js]))
}

然后便可以实现 maybe 的 do，它的实现和数组的版本完全相同，除了 sequence 的实例不同：

function maybeDo(generator, ...arrs) {
    return sequenceMaybe(...arrs).flatMap(elems => {
        const g = generator()
        g.next()
        for(let i = 0; i < elems.length - 1; i++) {
            g.next(elems[i])
        }
        return g.next(elems[elems.length - 1]).value
    })
}

看来这个形式可能可以适用于所有 Monad，但观察这个抽象的形式，它显然有一个限制，就是后面的Monad无法利用前面计算的结果，这让它的实用性大打折扣。but why so serious？

玩耍一下：

console.log(maybeDo(function*(){
    const a = yield
    const b = yield
    const c = yield
    return Maybe.Just(a + b + c)
}, Maybe.Just(1), Maybe.Just(2), Maybe.Just(3))) // Maybe { value: 6, tag: 'Just' }

console.log(maybeDo(function*(){
    const a = yield
    const b = yield
    const c = yield
    return Maybe.Just(a + b + c)
}, Maybe.Just(1), Maybe.Nothing(), Maybe.Just(3))) // Maybe { value: undefined, tag: 'Nothing' }