iT邦幫忙

2021 iThome 鐵人賽

DAY 12
0
Software Development

Functional Programming For Everyone系列 第 12

Day 12 - Semigroup I

Definition of a Semigroup

  • 一個集合(Set)或稱型別(Type)
  • 有 concat method
  • 必須符合 associative

Type Signature

concat:: Semigroup a => a ~> a -> a

a 是 Semigroup 且有 concat 這個 method 在內, 則 a -> a 成立

Law

associative:

concat(concat(a, b), c) = concat(a, concat(b, c))

並且 Semigroup 要符合 associative, 也就是無論括號 () 包覆在哪裡,其運算出來的值都要是相等的。

Alert:
concat 輸出出來的結果也必須是同一型別!!! 其可以確保其輸出值可以再次進行 concat ,直到我們想要結束為止。

以上就是 fantasy-land 對於 Semigroup 的定義,想必到這裡讀著們應該一頭霧水,這到底有啥用!!

從簡單的範例開始

根據上面提到的定義,想必各位讀者應該都聯想到了 JavaScript 似乎有幾個 Type 是已經符合 Semigroup 的定義了。

String

沒錯, JavaScript 中的 String 已經是一個合法的 Semigroup 了

'Functional'.concat(' ').concat('Programming') // "Functional Programming"
// same as
('Functional'.concat(' ')).concat('Programming')
// same as
'Functional'.concat(' '.concat('Programming'))

Array

Array 也是一個合法的 Semigroup,並且裡面 item 的資料型別可以不同。

[1, 2].concat([3, 4]) // [1, 2, 3, 4]
// same as
[1].concat([2, 3]).concat([4])
// same as
[1].concat([2, 3].concat([4]))

上述兩種 (String, Array) 原生資料型別皆有 concat 並且都符合 associative,當然,我們也可以創建屬於自己的 Semigroup

Sum & Product

只要兩個型別是 Sum 或 Product,就可以將兩值相加或相乘

const Sum = val => ({
  val, 
  concat: (o) => Sum(val + o.val),
  inspect: () => `Sum(${val})`
})

Sum(1).concat(Sum(1)).val // 2

const Product = val => ({
  val,
  concat: (o) => Product(val * o.val),
  inspect: () => `Product(${val})`
})

Product(10).concat(Product(10)).val // 100

Any & All

const Any = val => ({
  val,
  concat: (o) => Any(val || o.val),
  inspect: () => `Any(${val})`
})

Any(true).concat(Any(false)).val // true


const All = val => ({
  val,
  concat: (o) => All(val && o.val),
  inspect: () => `All(${val})`
})

All(true).concat(All(false)).val // false

Intersection

對兩組陣列取交集

const Intersection = (val) => ({
  val,
  concat: ({ val: oVal }) =>
    Intersection(val.filter((x) => oVal.some((y) => x === y))),
  inspect: () => `Intersection(${JSON.stringify(val)})`,
});

 Intersection([1, 2, 3]).concat(Intersection([3, 4, 5])).val // [3]

到目前為止,大家都知道如何實作屬於自己的 Semigroup 了! 但 So What...?

別急別急,現在我們可以將兩個相同的 Type 進行 concat,那是不是就可以將多個相同的 Type 進行 concat 呢?

沒錯!! 讓我們來實作一個 concatAll 函式吧!

concatAll

我們可以想想看這個函式需要什麼參數,或許參照 JavaScript 有類似功能(可以將相同的Type 進行累加)的 method,就是 Array.prototype.reduce

首先我們需要放入的參數會有

  • 一個 Semigroup
  • 有初始值
  • 是一組陣列
const concatAll = R.curry((semi, initValue, arr) => 
   arr.map(semi).reduce((acc, val) => acc.concat(val), semi(initValue)))

不難發現他就是將 Array 內的 item 轉換成給定的 Semigroup 後,在 reduce 成一個值,而我們可以用這個概念實作出 Array 原生的函式

max

找出給定陣列中最大值

const max = concatAll(Max, Number.NEGATIVE_INFINITY);

max([1, 2, 3, 4, 5]).val // 100

some

給定陣列中是否滿足給定條件,只要符合一個以上即為 ture

const some = R.curry((predicate, xs) => concatAll(Any, false, xs.map(predicate)))

some(isEven)([2, 4, 6])

every

給定陣列中是否滿足給定條件,必須全部符合才為 ture

const every = concatAll(All, true)

every(isEven)([2, 4, 6])

小結

本章介紹基本的 Semigroup 概念,下一章則是會在介紹 Monoid 以及 Semigroup 的實際範例

感謝大家閱讀

NEXT: Semigroup II & Monoid


上一篇
Day 11 - Algebraic Data Types
下一篇
Day 13 - Semigroup II & Monoid
系列文
Functional Programming For Everyone30

尚未有邦友留言

立即登入留言