泛函程式設計（20）－泛函庫設計－Further Into Parallelism

    上兩節我們建了一個并行運算元件庫，實作了一些基本的并行運算功能。到現在這個階段，編寫并行運算函數已經可以和數學代數解題相近了：我們了解了問題需求，然後從類型比對入手逐漸産生題解。下面我們再多做幾個練習吧。

在上節我們介紹了asyncf，它的類型款式是這樣的：asyncf(f: a => b): a => par[b]，從類型款式（type signature）分析，asyncf函數的功能是把一個普通的函數 a => b轉成a => par[b]，par[b]是一個并行運算。也就是說asyncf可以把一個輸入參數a的函數變成一個同樣輸入參數a的并行運算。asyncf函數可以把list[a]，一串a值，按照函數a => b變成list[par[a]]，即一串并行運算。

例：函數f: (a: a) => a + 10：list(1,2,3).map(asyncf(f))=list(par(1+10),par(2+10),par(3+10))，這些par是并行運算的。但它們的運算結果需要另一個函數sequence來讀取。我們從以上分析可以得出sequence的類型款式：

用sequence把list[par[a]]轉成par[list[a]]後我們就可以用par.map對list[a]進行操作了。list有map，我們可以再用map對a進行操作。在上一節我們做了個練習：

parmap按list[a]産生了一串并行運算的函數f。我們可以從類型比對着手一步一步推導：

1、lp: list[par[b]] = l.map(asyncf(f))

2、pl: par[list[b]] = sequence(lp) >>> parmap

再做個新的習題：用并行運算方式filter list：

 我們還是從類型比對着手一步步推導：

1、asyncf( a => if(f(a)) list(a) else list() )  >>> par[list[a]]

2、lpl: list[par[list[a]]] = as.map( asyncf( a => if(f(a)) list(a) else list()))

3、pll: par[list[list[a]]] = sequence(lpl)

4、map(pll){ a => a.flatten } >>> par[list{a]]

 測試結果：

再做一個計算字數的練習：用并行運算方式來計算list裡的文字數。我們盡量用共性的方法來通用化解答。如果文字是以list裝載的活，類型就是：list[string]，舉個執行個體：list("the quick fox","is running","so fast")。我們可以分兩步解決：

1、"the quick fox".split(' ').size >>> 把字元串分解成文字并計算數量

2、list(a,b,c) >>> a.size + b.size + c.size >>> 把list裡的文字數積合。

這兩步可以分兩個函數來實作：

1. f: a => b >>> 我們需要把這個函數轉成并行運算：list[par[b]]

2. g: list[b] => b

相信大家對泛函程式設計的這種數學解題模式已經有了一定的了解。

在前面我們曾經提過現在的fork實作方式如果使用固定數量線程池的話有可能造成鎖死：

我們再回顧一下fork的實作：

可以看出我們送出的callable内部是一個run par，這個run會再送出一個callable然後鎖定get。外面的callable必須等待内部callable的get鎖定完成。是以這種fork實作是需要兩個線程的。如果線程池無法再為内部callable提供線程的話，那麼外面的callable就會處于永遠等待中形成死鎖。上面的parmap函數會按照list的長度分解出同等數量的并行運算，運作時會造成死鎖嗎？如果線程池不是固定數量線程的話，答案就是否定的：如果并行運算數量大于線程數，那麼運算會分批進行：後面的運算可以等待前面的運算完成後釋放出線程後繼續運作，這裡重點是前面的運算始終是可以完成的，是以不會造成死鎖。

我們再看看現在所有的元件函數是否足夠應付所有問題，還需不需要增加一些基本元件，這也是開發一個函數庫必須走的過程；這就是一個不斷更新的過程。

現在有個新問題：如果一個并行運算的運作依賴另一個并行運算的結果，應該怎樣解決？先看看問題的類型款式：

我們可能馬上想到用map: map(pa){b => if(b) iftrue else iffalse}， 不過這樣做的結果類型是：par[par[a]], 是代表我們需要新的元件函數來解決這個問題嗎？我們先試着解這個題：

我們可以看到現在choice是個最基本元件了。為了解決一個問題就創造一個新的元件不是泛函程式設計的風格。應該是用一些更基本的元件組合成一個描述這個問題的函數，那才是我們要采用的風格。我們應該試着用一個函數能把par[par[a]]變成par[a]，可能就可以用map了：

ppa: par[par[a]]， 如果 run(es)(ppa).get 得到 pa: par[a], 再run(es)(pa) >>> future[a]。 par[a] = es => future[a]，不就解決問題了嘛：

現在可以用map來實作choice了吧。但是，map是針對元素a來操作的，iftrue和iffalse都是par[a]，還無法使用map。那就先放放吧。

既然我們能在兩個并行運算中選擇，那麼能在n個并行運算中選擇不是能更抽象嗎？

run(es)(pb).get 得出指數(index), choices(index)就是選擇的運算了：

從choicen中我們可以發現一個共性模式：是一個選擇函數：int => par[a]。再抽象一步我們把選擇函數變成：a => par[b]。這個函數就像之前接觸過的flatmap函數的傳入參數函數f一樣的。我們先看看flatmap的類型款式：

我們隻要flatmap pb 傳入 a => par[b]就可以實作choicen了： 

有了flatmap，我們可以用它來實作choice,choicen了：

在前面我們無法用map來實作choice，因為類型不比對。加了一個join函數，又因為map元素類型不比對，又不行。現在看來flatmap恰恰是我們需要解決choice的元件，而且flatmap能更抽象一層，連choicen都一并解決了。值得注意的是我們在以上解決問題的過程中一再提及類型比對，這恰恰展現了泛函程式設計就是函數解題的過程。

那麼flatmap,join,map之間有沒有什麼數學關系呢？

它們之間的确可以用數學公式來表達。