為什麼haskell里需要monoid?

小弟初學haskell,看到monoid這裡有點不理解, 為什麼需要這種抽象?


因為monoid是種很廣泛的代數結構, 一旦可以利用這代數結構的性質做些什麼事情, 同樣也可以應用到滿足這些性質的數據類型(instance).

monoid的廣泛是因為它的"簡單": 一個集合, 一個滿足結合律的封閉二元運算(mappend), 一個單位元(mempty). 例如最經常處理的一種數據類型: 字元串. 集合就是字符集各種字元組成的字元串, 二元運算就是字元串連接(++), 單位元就是空串("")

一些性質:

"abc" ++ "" == "abc"
("a" ++ "bb") ++ "ccc" == "a" ++ ("bb" ++ "ccc")

滿足結合律一個好處就是: 結果跟運算順序無關

例如:

"a" ++ "bb" ++ "ccc" ++ "dddd" + "eeeee" + "ffffff" -- 可以拆分成:
("a" ++ "bb" ) ++ ("ccc" ++ "dddd") ++ ("eeeee" ++ "ffffff" )

這樣可以幾個部分可以分別一起計算.

然後,有個處理monoid這種數據結構很常用的函數fold (foldl, foldr,可能更加常見的名字是reduce)

用fold實現map算是學FP里一道經典習題了==, 還有fold的一些性質可以讓編譯器做優化(stream fusion)或者做程序的Reasoning, 可以看ref.

這些都是FP里比較基本的抽象,不限於在Haskell里應用, 更深入點關於monoid, fold的推廣(recursion schemes) 太難就沒有深入進去了

update: 發現大神的Slide已經囊括了我想說的了:

http://comonad.com/reader/wp-content/uploads/2009/07/AllAboutMonoids.pdf

ref:

關於函數編程(二)摺疊與抽象化

關於函數編程(三)摺疊

Googles MapReduce Programming Model -- Revisited


這叫抽(chong)象(zai)的力量……

比如處理String, ByteString, Text, ShowS這些「字元串」類型的時候,拼接兩個「字元串」只要用`&<&>`就好了。而不是`++`, `append`, `.`等不同的函數。除了美觀以外,更主要的是你可以基於這種抽象去實現能夠處理不同類型(滿足給定type constraints的所有類型)的通用函數。

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE TypeSynonymInstances #-}
{-# OPTIONS_GHC -fno-warn-orphans #-}
import Data.Monoid (Monoid(mappend))
import qualified Data.ByteString as B
import qualified Data.ByteString.Lazy as LB
import qualified Data.Text as T

instance Show ShowS where
show s = show $ s ""

gao :: (Show a, Monoid a) =&> a -&> a -&> IO ()
gao a b = print $ a `mappend` b

main :: IO ()
main = do
gao "Hukurei" ("Reimu" :: String)
print $ "Hukurei" ++ ("Reimu" :: [Char])
gao "Kirisame" ("Marisa" :: B.ByteString)
print $ "Kirisame" `B.append` "Marisa"
gao "Kochiya" ("Sanae" :: LB.ByteString)
print $ "Kochiya" `LB.append` "Sanae"
gao "Konpaku" ("Youmu" :: T.Text)
print $ "Konpaku" `T.append` "Youmu"
gao "Konpaku" ("Youmu" :: T.Text)
print $ "Konpaku" `T.append` "Youmu"
gao (showString "Izayoi") (showString "Sakuya")
print $ (showString "Izayoi") . (showString "Sakuya")


補充點形象的回答

Monoid泛指所有隻需留意排列Permutation順序的狀況, 不必在意是哪幾個東西優先運算, 有串接的意思

假設##是Monoid運算元, 那麼如下例

x ## ((y ## k) ## z) = x ## (y ## (k ## z)) = (x##y) ## (k ## z) = ......

非常多種結合法一下就劃歸成同一種, 這就是他的力量來源

只須知道他們的排列依序是 x y k z 且都是由 ## 串起來的就行

這性質稱作Composable可組合性, Monoid是其中所有定義中的最簡定義


Haskell的庫的特點是凡是可以抽象的東西他一概不放過。之所以會有monoid,大概是因為有了monoid和monad之後,很多東西都可以用他們來表達,一層一層薄薄的抽象累積起來成為一個巨大的庫,跟我們使用C++還是C#的時候的感覺截然不同。

舉個例子,你要做尾遞歸優化,譬如說下面這個函數

sum [] = 0
sum (x:xs) = x + sum xs

其實是可以寫成循環的,但是你這麼寫,他就不是一個尾遞歸函數。那要怎麼辦呢?人肉優化都知道我們需要加一個acc參數把他寫成為遞歸的,但是實際上這麼做我們是把右結合的加法改成了左結合的加法。那Haskell怎麼知道加法可以這麼做呢?當然他可以hardcode。那我們自己的運算怎麼辦呢?

所以你還會看到Haskell裡面有一個type class叫做群(抽象代數),你聲明了他,或許他就會幫你優化了。很多抽象就是這麼一點一點搞出來的。它不像我們寫C++和C#,每一個抽象背後的代碼都十分底層無比複雜,Haskell喜歡在一個抽象裡面,改一點點東西做成一個新的抽象,當你得到了大量的抽象之後,你突然發現它可以用來解決現實問題了。所以你才會看到大量的這些你平時估計直接用不到的東西。


Functors, Applicative Functors and Monoids

最後


推薦閱讀:

為什麼 Haskell 始終沒法流行呢?
Robert Harper 不支持Haskell 的理由是?
Haskell 最有代表性的一段程序是什麼?
國內有哪些公司用Haskell做網站後端的?
Haskell 有哪些威力十足的庫?

TAG:函數式編程 | Haskell | 編程範式 |