Day 24 - Travserable

在介绍 Task Monad 前，来介绍一个重要的概念，

想像一下，有一组阵列里面的项目都是 userId，现在要将 userId 去做 http request，

usersId

const usersId = [1, 2, 3, 4, 5]

http request

const userGet = id => 
    fetch(`https://jsonplaceholder.typicode.com/users/${id}`).then(r => r.json())

result

usersId.map(userGet)

然而它的结构变成 Array<Promise>

[Promise, Promise, Promise, Promise, Promise]

这其实是可以想像得到的，但我们更想要的是 Array<User>，那该怎麽办?

Promise([User, User, User, User, User])

大家应该想到了，在 Promise 有 Promise.all 可以帮助我们完成这件事

Promsie.all(usersId.map(userGet)).then(console.log)

// [User, User, User, User, User]

但现在也像要让前面几章提到的 Effect 也有类似 Promise.all 的效果呢?

没错，本章要来介绍 Travserable

Travserable

type signature

traverse :: Applicative f, Traversable t 
    => t a ~> (TypeRep f, a -> f b) -> f (t b)

什麽是 TypeRep 呢? 可以看一下 Fantasy-land 的解释

来分析一下此 type singature， 首先会有一个 t a 透过 map a -> f b 将其进行转换後，我们会得到 f (t b)，此时大家可能会百思不得其解的想，为何不是变成 t (f a) 而是 f (t b) 呢?

接下来带大家看一下范例(参考来源) toChar 函式，在讲解 traverse 是怎麽运作的

const toChar = (n) =>
  n < 0 || n > 25
    ? Left(`${n} is out of bound`)
    : Right(String.fromCharCode(n + 65));

如果 Either 有了 traverse, 则我们就可以将 Array 进行 map 後在 flip 成 Either

const Right = (x) => ({
  ...
  traverse: (of, f) => f(x).map(Right),
  ...
});

const Left = (x) => ({
  ...
  traverse: (of, _) => of(Left(x)),
  ...
});

const Either = {
  Left,
  Right,
  of: Right,
};

// Right(["B", "C", "D", "E"])
[1, 2, 3, 4].traverse(Either, toChar).inspect()

// Left("100 is out of bounds!")
[100].traverse(Either, toChar).inspect()

这样大家应该对 traverse 不陌生了，接下来可以看一下 traverse 到底是如何实作的

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

读者们可能会觉得为什麽 Array 是 Traversable 的呢? 要是 Traversable 前提是其必须是 Functor (可以 map) 跟 Foldable (可以被 reduce)，而 JavaScript 的 Array 满足了上面两个条件，所以它也有 Traversable 的特性.

reduce

首先是 reduce 想必大家都不陌生，就是将其进行合并

type signature

reduce :: [a] ~> ((b, a) -> b, b) -> b

其放入 reducer 跟 initial value

initial value

T.of([])

这边体现了 Applicative 的重要性，因为它可以进行指向，也就是将值包进容器中，

reducer

const append = x => y => y.concat(x)

(acc, val) => f(val).map(x => y => y.concat(x)).ap(acc)

可以看到此的 reducer 会先将转换函式 (ex: toChar) 套用在每个迭代的值 (val) 并且此时再将两个 effect type 进行透过(append) 合并, 以此类推

可以看到这个 reducer 是不是很像之前提到的 lift2, 所以在将其改写一下

(acc, val) => lift2(append, f(val), acc)

最终 Array.prototype.traverse 的样貌

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

而要提到另外一个概念就是 sequence, 其就只是将 traverse 第二个参数换成 identity

const sequence = (T, xs) => xs.traverse(T, R.identity)

law

1. identity

u.traverse(F, F.of) === F.of(u)

traverse 要符合 identity 的条件，且 F 必须是 Applicative

[1, 2, 3].traverse(Either, Either.of) === Either.of([1, 2, 3])

注: 其实不只有 identity 一个条件而已，还有 naturality 跟 composition 之後有机会提到 natural transform 在进行补充

小结

感谢大家阅读

NEXT: Task Monad | State Monad

Reference

1. traversable
2. mostly-adequate ch12
3. fantasy-land