程式設計的本質就是運算,而運算的本質呢?艾倫圖靈觀察人們從事的運算任務,從中逐一分解,探討運算的能力來源,建立了狀態機、下推機、圖靈機等數學模型,運算的本質就是數學!

如果開發者試著學習一門純函數式語言,例如Haskell,藉由觀察重複,可以抽取出像是Functor、Applicative、Monad等行為,然而隨著抽象程度不斷地提高,會發現抽象出來的概念,越來越朝著數學基礎定義的方向前進,不少開發者也就越難以理解這些定義的實質作用,例如Haskell的Monoid型態類別,規範了恆等值(identity)與結合律(Associativity),這是什麼呢?

恆等值與結合律?

現代有不少命令式語言,融入了許多函數式的概念,Functor、Applicative、Monad等行為,或多或少都找得到對應的API。

例如,list與map方法就像實現了Functor,list與flatMap就像實現了Monad,如果曾經試著將運算子作為函式傳入某個方法來運算兩個物件,就像實現了Applicative,那麼,Monoid型態類別呢?這看來就像純數學上的定義吧!

函數式設計的入門課題中,不是有filter/map/reduce嗎?

在reduce這部份,是個消減操作,例如,將1到5加總,可以看成是將1到5的list,以0開始與指定加法來消減得到,那麼,指定的0是什麼值?許多API文件都說是初值?

其實,嚴格來說,這個初值必須是加法的恆等值,而reduce可指定的運算,其實必須具有結合律,加法就是具有結合律的運算。

或許有人會認為這太小題大作,不過,比較嚴謹的API文件就會標明,例如Java的Stream API,其reduce方法說明就確實規範了,accumulator必須是具有結合律的二元函數,identity參數必須是accumulator恆等值。

通用的reduce行為

雖然不少程式庫的reduce實作多是針對list,然而,Java的Stream來源,不一定要是list,也可能是Set,而且就算reduce只針對list,開發者也可以自行轉換為list再進行reduce,也就是reduce的對象不用是特定的資料結構。

另一方面,就算只針對list,執行reduce時是由左往右還是由右往左呢?JavaScript陣列確實有明確規範reduce與reduceRight,不過,大多數的reduce沒有限定方向,例如Java的reduce就明確說明了,reduce時並不限於循序。

這麼一來,如果要實作通用的reduce,會需要哪些條件呢?

能接受的函式必須是二元函式,它要將兩個型態相同的運算元結合,成為一個相同型態的值。例如,加法函式可以將2與3結合為5,*可以將2與3結合為6,字串的串接函式,可以將"abc"與"def"結合為"abcdef",而且,該二元函式必須具有結合律,例如,(1+2)+3會與1+(2+3)相同,因此,加法具有結合律。

這是因為事先無法預料可以折疊的資料型態會是什麼樣的結構,被丟進函式處理的兩個值,可能是從結構中任意處取得,如果函式不具備結合律,通用的reduce執行結果就可能不正確。

另外,指定的二元函式必須具有恆等值,函式套用恆等值與某值,結果還會是該值,例如,0對加法是個恆等值,因為任何數與0相加都會是原來的數,1加0還是1、2加0還是 2,類似地,1對乘法是個恆等值,因為任何數與1相乘,結果還是原數字,2乘1還是2,3乘1還是3。

這個考量同樣是因為,事先無法預料可以折疊的資料型態會是什麼樣的結構,因此,通用的reduce首次執行時,必須有個初始的恆等值才能作為開始。

Monoid規範積累行為

先前專欄〈掌握Haskell型態類別〉我曾提過,對於可折疊的行為,Haskell定義了Foldable型態類別,如果我們想要實現Foldable,可以實現foldr行為,這對於大部份開發者而言,沒有問題,另一個方式是實作foldMap,函式型態是Monoid m => (a -> m) -> t a -> m,這是什麼呢?

現代開發者應該對使用map轉換list的元素,後續進行reduce得到一個結果,滿熟悉的吧!

其實map目的之一,就是將list的元素轉換為具有Monoid行為的元素,之後再進行reduce,fold就是reduce,而foldMap就只是將map與fold結合起來,foldMap由右往左讀的意思,就是先map再fold,指定的a -> m就相當於指定給map的函式,該函式用於將t a的a轉換為m,後續將t m折疊為m,就結果而言,就是t a -> m。

記得Google提出的大數據架構MapReduce嗎?在分散式運算的架構下,各節點得到的資料彼此獨立,因此,Map階段要將資料轉換為具有Monoid行為的資料,才能在Reduce階段運算。

Monoid型態類別的mempty規範的就是恆等值,而mappend規範的就是有結合律的函式。其實還有個mconcat,規範了積累(accumulate)運算,積累是比折疊更為抽象的觀念,因為積累的方式並不限於折疊,只不過預設實作是透過右折疊foldr,如果沒特別要求,想實現Monoid時,只要實作mempty與mappend。

簡單來說,Monoid規範了資料該怎麼進行積累,像是一組字串如何積累為字串,一組list如何積累為一個list,一組數字如何積累為一個數字等。

有些開發者可能有疑問,方才談到數字的加法與乘法具有結合律,而且,有對應的恆等值,那麼,Haskell的數字是Monoid嗎?是的!不過,在此時,問題就來了,1 `mappend` 2要選哪個結合?加法還是乘法?

Haskell的Data.Monoid模組,以newtype定義了Sum與Product,對於具有加法及乘法概念的資料,可以透過Sum與Product來區分,例如以下同樣的r,面對Sum s,s會是加法的結果3,面對Product p,p會是乘法的結果2:

let r = 1 `mappend` 2
let (Sum s) = r
let (Product p) = r

Monoid的組合能力

Haskell的list、數字以外,還有許多的Monoid實現,例如Maybe,對兩個Maybe進行mappend,它會對內含的值做mappend(也就是內含值也要是Monoid),(Just "a") `mappend` (Just "b")可以得到Just "ab",也就是說,只要是Monoid,就可以自由地結合。

這就是為什麼,在純函數式的世界中,隨著抽象程度不斷地提高,抽象出來的概念,越來越會朝著數學基礎定義方向前進的原因,只要越是將運算的本質定義出來,就越能基於這些本質進行組合,得到各種運算的可能性,圖靈機的探討是如此,lambda演算的探討也是如此!

沒想到吧!reduce的來源元素需要有Monoid規範的結合律與恆等值,Monoid更接近純粹數學上的概念,是為了讓程式有更多的組合性。

如果下次我們遇到更接近數學層面的型態類別,不妨從組合性的方向思考,或許就能瞭解到其行為之意義!

專欄作者


熱門新聞

Advertisement