泛函程式設計（26）－泛函資料類型－Monad－Applicative Functor Traversal

  前面我們讨論了applicative。applicative 就是某種functor，因為我們可以用map2來實作map，是以applicative可以map，就是functor，叫做applicative functor。我們又說所有monad都是applicative，因為我們可以用flatmap來實作map2，但不是所有資料類型的flatmap都可以用map2實作，是以反之不是所有applicative都是monad。applicative注重于各種類型的函數施用，也就是map。包括普通函數的施用及在高階類型結構内的函數施用，還有多參數函數的連續施用。表面上看來monad已經覆寫了functor, applicative。可能就是因為monad的功能太強大了，是以monad的函數組合（functional composition）非常有限。我們隻能從applicative來擷取函數組合這部分的能力了。

    我們先研究一下applicative的一些規則：

1、map的恒等定律：map(v)(x => x) === v

   map(v)(f) === apply(unit(f))(v), 就是說把一個函數f用unit升階後apply就是map。apply就是map的一種。

   applicative的恒等定律：apply(unit(x => x))(v) === v

2、applicative的函數組合：如果我們具備以下條件：

   f類型 = f[a => b], g類型 = f[b => c]，x類型 = f[a]。那麼：

   apply(map2(f,g)(_ compose _))(x) === apply(f)(apply(g)(x))，或者更直接一點：

   map3(f,g,x)(_(_(_))) === f(g(x))。map3就是函數升階組合：把函數 (_(_(_))) >>> (a,b,c) => d 在高階類型結構内進行組合。

先看看兩個applicative元件的實作：

對于applicative f,g來說 (f[a],g[a])， f[g[a]]也都是applicative。通過對兩個applicative進行函數組合後形成一個更高階的applicative。這個applicative和其它普通的applicative一樣可以實作多參數函數的升階連續施用。

applicative另外一個強項展現在針對可遊覽類型（traversable type）内部元素的函數施用（map）。與可折疊類型（foldable type）相比較，traversable類型更加抽象，能覆寫類型更多資料類型。foldable類型的map用monoid實作，但monoid無法完全實作traversable類型的map。traversable類型的map是通過applicative實作。traversable覆寫了foldable，是以foldable隻是traversable的其中一種案例。那麼我們就看看這個traversable類型：

在前面我們讨論過的資料類型裡，我們都會實作traverse,sequence這兩個函數。那是因為我們嘗試把那些資料類型都變成traversable類型。traverse,sequence的函數款式是這樣的：

我們試試實作map類型的sequence:

實作過程還是挺複雜的。這裡有些特别的地方需要注意：在實作applicative執行個體時最好實作map2，因為它的函數款式更簡單清晰。而在進行applicative操作時使用apply會更友善。

既然traversable是那麼地普遍，為什麼不把它抽象出來形成一個特殊的類型呢？

這個trait裡的sequence,traverse函數與我們前面實作的sequence和traverse有什麼不同呢？

f[_]變成了ap[_]:applicative：就是說ap必須是一個applicative

list變成了t：trait traverse針對任何t[_]，包括list，更概括了。以前的sequence和traverse都隻針對list，現在的traverse類型可以拓展概括所有t[_]這種類型。

我們試着實作這個traverse類型：

我們可以試着實作list,option,tree這幾個traverse類型執行個體：

所有traverse類型的執行個體隻要實作traverse或sequence就可以了，因為traverse和sequence互相可以實作。

sequence和traverse可以互相實作，但sequence的實作需要使用map。我們可以試着在trait traverse裡實作一個預設的map函數：

我們可以得到一個identity functor：type id[a] = a, 這個東西存粹是為了擷取f[a]這麼個形狀以便比對類型款式。這樣我們可以得出一個identity monad:

raverse會保留traverse類型的原始結構。這點從traverse定律可以推導：針對traverse[f], xs類型是f[a]的話：

 traverse[id,a,a](xs)(x => x) === xs >>> map(xs)(x => x) ===xs， 這不就是functor恒等定律嗎？也就是說把traverse需要的applicative functor降至id functor後traverse相當于map操作。換句話說traverse可以概括functor并且traverse操作要比map操作強大許多。

這樣我們用idmonad就可以實作一個預設的map函數:

注意：在scala文法中:

 def traverse[ap[_]: applicative, a, b](ta: t[a])(f: a => ap[b]): ap[t[b]]

ap[_]：applicative是context bound, 相當于：

def traverse[ap[_], a, b](ta: t[a])(f: a => ap[b])(implicit m: applicative[ap]): ap[t[b]]

是以：

 def map[a,b](ta: t[a])(f: a => b): t[b] = traverse[id,a,b](ta)(f)(idmonad)

為什麼需要這個context bound applicative執行個體？實作traverse時需要applicative的map,map2操作：

現在我們通過traverse類型可以實作遊覽（traversal）那麼traverse和foldable有什麼差別嗎？從表面上來看traverse應該比foldable更高效，因為foldable是通過monoid來對結構内的元素進行函數施用的，而applicative比monoid更強大。我們先看看foldable最概括的操作函數foldmap：

def foldmap[a,b](as: f[a])(f: a => b)(mb: monoid[b]): b

再看看traverse的函數款式：

如果我們把ap[a]換成一個特制的類型：type constint[a] = int, 經過替換traverse就變成了：

 def traverse[a,b](fa: t[a])(f: a => int): int

經過替換的traverse在函數款式上很像foldmap。那麼我們就制造一個對任何b的類型:

 type const[a,b] = a

用這個類型加上monoid實作一個applicative執行個體：

有了這個applicative執行個體，我們就可以在trait traverse裡實作foldmap，也就意味着traverse可以extend foldable了：

既然traverse已經概括了foldable，而且traverse類型有比foldable效率高，那麼以後盡量使用traverse這種類型。

 state能夠很巧妙地對高階資料類型結構内部元素進行函數施用同時又維護了運算狀态資料。前面我們已經取得了state nonad執行個體。因為所有monad都是applicative，是以等于我們已經擷取了state applicative functor執行個體。如果我們在遊覽（traverse）一個集合的過程中用state applicative functor對集合元素進行操作并且維護狀态資料，那麼将會實作強大的高階資料類型處理功能。我們先看一個結合state的traverse函數:

我們用這個函數來遊覽集合并标注行号：

再用這個函數把t[a]轉成list[a]：

這兩個利用state的函數文法十分相近。實際上所有state遊覽（traversal）都很相似。我們可以再進一步抽象：

用maps重新實作zipwithindex,tolist,foldleft就簡單的多。maps遊覽天生是反序的，是以reverse函數隻要對t[a]用maps走一次就行了。

我們發現traverse類型會保持它的結構，這是它的強項也是它的弱點。如果我們嘗試将兩個traverse結構t[a],t[b]拼接成t[(a,b}]時就會發現這個操作對t[a]和t[b]的長度是有一定要求的。我們先試着用maps來拼接t[a],t[b]：

我們可以看到：tb的長度必須等于或大于ta。如此我們隻有把這個函數分拆成兩種情況的處理函數：

1、ta 長度大于 tb : 用下面的zipl函數

2、tb 長度大于 ta : 用下面的zipr函數

這樣我們得出的t[(a,b)]其中t[a],t[b]短出的部分就用none來填補。

我們能像monoid product 一樣在對一個可折疊結構進行遊覽時對結構内部元素一次性進行多次操作，我們同樣可以對可遊覽結構（traversable）在一輪遊覽時對結構内部元素進行多次操作：

兩個applicative執行個體通過product函數變成applicative[(m,n)]執行個體。在traverse運作中m,n分别同時進行函數施用。