iT邦幫忙

2021 iThome 鐵人賽

DAY 24
0
Software Development

Functional Programming For Everyone系列 第 24

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

上一篇
Day 23 - Either Monad
下一篇
Day 25 - Reader Monad
系列文
Functional Programming For Everyone30

尚未有邦友留言

立即登入留言