遍历与队列 - Traversable

Array insideOut

假如我们现在有一个数字的数组，我们要把这些数字转换为对应的26个英文字母，但是这个转换肯能会失败，因为并不是所有的数字都是可以转换的，所以这种情况下我们可以使用Either来处理转换成功和转换失败：

const toChar = n => n < 0 || n > 25
  ? Left(n + ' is out of bounds!')
  : Right(String.fromCharCode(n + 65))

下面继续使用toChar函数:

  const res2 = [0, 1, 2].map(toChar)
  console.log(res2) // [ Right(A), Right(B), Right(C) ]

看上去问题不大！但是感觉怪怪的啊！或许我们理想的结果是Right([A,B,C])?

类似的例子:

const httpGet = name => new Promise((res,rej) => {
  setTimeout(() => res(`My name is ${name}`), 2000)
}) 

const nameList = ['James','Melo']

nameList.map(name => httpGet(name)) // => [Promise,Promise]

// 我们一般不会这么操作的，我们会借助Promise.all来完成这个过程
Promise.all(nameList.map(name => httpGet(name))) // => Promise([])

现在回头看一下，我们如何把[Right(A),Right(B),Right(C)]转换为Right([A,B,C])呢？实际上这是一个insideOut的过程，也就是把Right(A),Right(B)从Array中解救出来，然后再集合放到Right中。

这个过程我们可以借助Array.reduce来完成：

const res = [0, 1, 2].map(toChar)

const lift2 = (f, fx, fy) => fx.map(f).ap(fy)
const append = y => xs => xs.concat([y])
const insideOut = (T, xs) =>
    xs.reduce(
        (acc, x) => lift2(append, x, acc),
        T.of([])
    )
console.log(insideOut(Either, res)) // => Right(A,B,C)

本质上就是对一个数组先进行map,然后进行reduce(或者先reducer，然后map,结果应该是一样的)，这段代码，我们可以稍微做个抽象：

Array.prototype.traverse = function (T, f) {
    return this.reduce(
        (acc, x) => f(x).map(append).ap(acc),
        T.of([]))
}

 const res1 = [0, -1, 2, 3, 4].traverse(Either, toChar)
console.log(res1) // => Left(-1 is out of bounds!)

const res2 = [0, 1, 2, 3, 4].traverse(Either, toChar)
console.log(res2) // => Right(A,B,C,D,E)

List

之前我们仿照Array的map创建了一个最简单的Functor - box,现在，我们可以仿照traverse创建一个新的Functor：List

const List = x => ({
  x,
  map: f => List(x.map(f)),
  concat: ({ x: y }) => List(x.concat(y)),
  ap: o => x.map(f => o.map(f)).reduce((acc, a) => acc.concat(a)),
  chain: f => x.map(f).reduce((acc, a) => acc.concat(a)),
  traverse: (T, f) => x.reduce((acc, x) => f(x).map(append).ap(acc), T.of([])),
  [inspect]: () => `List([${x}])`,
});

List.of = x => Array.isArray(x) ? List(x) : List([x])

List的参数原则上是一个数组； map方法：和普通的Box有所区别在于是变换List中的每一项 concat方法：是把新项追加到数组中，然后用List重新包装, ap方法：接收另外一个List,然后把x中func逐一应用到o的item上(注意此时x为函数的数组)，然后通过reducer合并 chain方法：接收一个函数直接把List中的每一项全部应用map，然后通过reducer合并 traverse方法：完全相同与上面介绍的Array.prototype.traverse

List应用与并发应用

得益于Applicative的并行特性，我们可以使用traverse创建更简洁的并行逻辑

List traverse 同步逻辑

const app = (arr) => List(arr)
    .traverse(Either, toChar)
    .fold(x => console.log('log left', x),
        x => console.log('log right', x))

const res1 = app([0, 1, 2, 3]) // log right [ 'A', 'B', 'C', 'D' ]
const res2 = app([0, -1, -2, 3]) // log left  '-2 is out of bounds!-1 is out of bounds!'

List traverse 异步逻辑

const httpGet = name => new Promise((res,rej) => {
  setTimeout(() => res(`My name is ${name}`), 2000)
}) 

 const users = ['melo', 'james', 'brian']

console.time('getName')
const res = List(users)
    .traverse(Task, httpGet)
    .fork(x => console.log('log left', typeof x, x),
        x => {
            console.timeEnd('getName') //2006.420ms
            console.log('log right', typeof x, x) // log right object ['My name is melo', 'My name is james', 'My name is brian']
        })

SHARE ON: