iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 21
1
Software Development

mostly:functional 從零開始的異世界程式觀 --- 函數式程式設計的試煉系列 第 21

mostly:functional 第二十章:Semigroup 的實體

-- 0823

我試了好幾個數字,丟進去時都沒什麼反應。自暴自棄之下,我開始亂試,其中有幾個東西丟進去的時候,開孔很快的把東西噴回來。感覺好像是有點生氣了。

一直到我放了一個空的串列 [] 進去時,洞口上方的字終於變了,寫著 Sum ?。我還注意到,當我把空串列丟進去的時候,隔壁的建築似乎微微的發亮了一下。

嗯… Sum... 是什麼呢?




什麼東西是 Semigroup

看過了 Semigroup 的法則之後,我們來思考一下有哪些東西可以算是 Semigroup:

字串是一種 Semigroup 嗎?

字串是一種 Semigroup。把兩個字串相接在一起的二元運算是 ++

  1. 封閉律:
    任兩個字串相接,結果也是個字串。

    -- Haskell語法
    "Haskell" ++ "Rocks" -- => "HaskellRocks"
    
  2. 結合律:
    三個字串相接,先接哪兩個沒有差別。

    -- Haskell語法
    ("I" ++ "like") ++ "Haskell" == "I" ++ ("like" ++ "Haskell")
    

字串的 Semigroup 實作

-- Haskell 語法
instance Semigroup String where
  (<>) = (++)

串列是一種 Semigroup 嗎?

串列也是一種 Semigroup。把兩個串列相接在一起的二元運算,也是 ++

  1. 封閉律:
    任兩個串列相接,結果也是個串列。

    -- Haskell語法
    [1, 2, 3] ++ [4, 5, 6] # --> [1, 2, 3, 4, 5, 6]
    
  2. 結合律:
    三個串列相接,先接哪兩個沒有差別。

    -- Haskell語法
    ([1, 2] ++ [3, 4]) ++ [5, 6] == [1, 2] ++ ([3, 4] ++ [5, 6])
    

串列的 Semigroup 實作

```haskell
-- Haskell 語法
instance Semigroup [a] where
  (<>) = (++)
```

整數是一種 Semigroup… 嗎?

很不幸的,整數不是 Semigroup。

因為整數上符合封閉律與結合律的二位運算...不只一種。而每個型別,只能有一個 typeclass 的實作(實體)。所以,必須要想辦法把它們分開。

整數加法是一種 Semigroup 嗎?

是的。

一旦指定了是加法之後,那麼整數加法就符合了 Semigroup 的法則了。Haskell 的做法是做出一種新的型別,表示整數加法的概念。這個型別是:Sum

整數乘法是一種 Semigroup 嗎?

同理,整數乘法也是 Semigroup。代表整數乘法的型別叫 Product。上述的 Sum 及這裡的 Product,都放在 Semigroup.Data 模組下。需要另行載入才能使用。

整數減法是一種 Semigroup 嗎?

減法可以透過改成加上負數來實現,所以視同加法。

整數除法是一種 Semigroup 嗎?

不是。https://chart.googleapis.com/chart?cht=tx&chl=3%20%2F%202%20%3D%201.5,而 https://chart.googleapis.com/chart?cht=tx&chl=1.5 不是整數,違反封閉律。這個沒辦法救。


試試看吧

-- Haskell 語法
[1, 2] ++ [3, 4] -- => [1, 2, 3, 4] -- 這是正常的串列串接

[1, 2] <> [3, 4] -- => [1, 2, 3, 4] -- 把串列當做 Semigroup 操作

"Hello" <> "World" -- => "HelloWorld" -- 把字串當做 Semigroup 操作

-- 有趣的部份
import Data.Semigroup

Sum 2 <> Sum 3 -- => Sum {getSum = 5} -- 把整數加法當做 Semigroup 操作

Product 2 <> Product 3 -- => Product {getProduct = 6} -- 把整數乘法當做 Semigroup 操作

半群 (Semigroup) 這個字是什麼意思?

這個字,由拉丁文的一半的字首:semi,加上數學上的群:group 所組成。之所以用了一半這個字,是因為要把一堆東西定義為一個,需要符合四條法則。而半群只符合了其中兩條,故稱為半群。




當我走到盡頭的房間,看到了一樣的平台,正想著又要解謎題了的時候,卻發現那塊泛著紫色光暈的金屬板,蓋在上面。

「呃,可以…借過一下嗎?」

金屬板上,慢慢浮現了字樣:

Left $ First $ Just "go there"

「不能讓我先處理這個嗎?」

而看來它完全沒有要動的意思。

我嘆了口氣,往四周看了看,而就我左方的房間側面,看到一扇很高的門。從後方的窗戶看出去,似乎會通到…隔壁那棟建築。而從這裡看起來,它外觀已經變得非常明顯了。一回神,我發現金屬板又浮在那個門前了。

門上標識的符號是: mempty

[to be continue]


上一篇
mostly:functional 第十九章:Semigroup 的法則
下一篇
mostly:functional 第二十一章:Monoid 的法則
系列文
mostly:functional 從零開始的異世界程式觀 --- 函數式程式設計的試煉35

2 則留言

0
taiansu
iT邦新手 5 級 ‧ 2020-10-06 03:13:06

故事改動

0
lancer1268
iT邦新手 5 級 ‧ 2021-07-04 01:02:41

整數減法不是 semigroup 吧?(a-b)-c 不等於 a-(b-c)

taiansu iT邦新手 5 級 ‧ 2021-07-07 02:46:21 檢舉

感謝提問~

如果用「"加一個負數"來實現減法」的概念的話,
(a - b) - ca - (b - c) 不是同一條式子。

第一條的 (a - b) - c 會寫成
a + (-b) + (-c)

其結合律為: (a + (-b)) + (-c) = a + ((-b) + (-c))

第二條的 a - (b - c) 則是 a + (-b) + c
( c 的部份"減去一個負數"變成"加上一個正數")

其結合律為 (a + (-b)) + c = a + ((-b) + c)

我要留言

立即登入留言