iT邦幫忙

2021 iThome 鐵人賽

DAY 13
0
Software Development

Functional Programming For Everyone系列 第 13

Day 13 - Semigroup II & Monoid

yo, what's up

Semigroup II

多組 Semigroup 進形合併

到目前為止我們已經知道 Semigroup 可以透過 concat 將多個相同的 Type 進行 reduce,那如果我們想要將多組不同的 Type 進行 concat 呢?

那我們就建立一個 Tuple Semigroup 其職責就是給定特定組數的 Semigroup 各自進行 reduce.

const Tuple = (x, y) => ({
    x, 
    y,
    concat: o => Tuple(x.concat(o.x), y.concat(o.y)),
    inspect: () => `Tuple(${x}, ${y})`
})

舉例來說,我們有兩組 Tuple 其中一組內有 Tuple(Sum(1), Max(1)),另一組則是有 Tuple(Sum(1), Max(100)),這時我們就可以用 concat 將其各自的 Semigroup 進行合併

Tuple(Sum(1), Max(1)).concat(Tuple(Sum(1), Max(100))).inspect() // Tuple(2, 100)

當然我們也可以有 Tuple3 ,Tuple4 , ... TupleN

Example

假設我們現在有兩組資料結構,但皆是同一個使用者的資訊,

const Jing1 = {
    name: 'Jing',
    lastLoginTime: new Date(2021, 8, 4).getTime(),
    techStacks: ["JavaScript"]
}

const Jing2 = {
    name: 'Jing*5',
    lastLoginTime: new Date(2021, 8, 1).getTime(),
    techStacks: ["Functional Programming", "React"]
}

如果現在我們想要將

  • 取第一組資料結構的 name
  • 取最近登入的 lastLoginTime
  • 合併該使用者的 techStacks

大家有想到要如何做嗎? 此時這個概念就可以派上用場

Step01

由於合併資料欄位有三筆,所以要先建立一個 Tuple3

const Tuple3 = (x, y, z) => ({
    x, 
    y,
    z,
    concat: o => Tuple(x.concat(o.x), y.concat(o.y), z.concat(o.z)),
    inspect: `Tuple(${x}, ${y}, ${z})`
})

Step02

建立該合併策略

const mergeStrategy = {
  to: user => Tuple3(First(user.name), Max(user.lastLoginTime), user.techStacks),
  from: ({x, y, z}) => ({name: x.val,lastLoginTime: y.val, techStacks:z })
}


const merge = strategy => x => y =>
  strategy.from(strategy.to(x).concat(strategy.to(y)));
  
merge(mergeStrategy)(Jing1)(Jing2)

// {
//    "name":"Jing",
//    "lastLoginTime":1630684800000,
//    "techStacks":[
//       "JavaScript",
//       "Functional Programming",
//       "React"
//    ]
// }

isn't neat!! 而這就是 Semigroup 的強項!

然而我們似乎還少提到了一個概念,就是 Monoid

Monoid

Definition of a Monoid

Type Signature

empty :: Monoid m => () -> m

m 是 Monoid, 則 empty 這個函式的 signature () -> m 成立

Law

  • 一個集合(Set)或稱型別(Type)
  • 有 concat method
  • 必須符合 associative
  • 此一集合(aka, A) 內有一個元素 (a),可以被稱作 empty,且其符合以下定理
    • Right identity: a.concat(empty) === a
    • Left identity: empty.concat(a) === a

則可以稱作為 Monoid,而 Monoid 也必定是一個 Semigroup. 所以可以看到它也必須符合 Semigroup 的定義。

那就來嘗試看看,可不可以將上篇提到的 Semigroup,找出其對應的 empty 元素,並滿足 Monoid 的所有條件

Sum & Product

Sum.empty = () => Sum(0);

Sum(1).concat(Sum.empty()) === Sum(1) // true
Sum.empty().concat(Sum(1)) === Sum(1) // true


// Product
Product.empty = () => Product(1);

Any & All

// Any
Any.empty = () => Any(false)

// All
All.empty = () => All(true)

Intersection

Intersection semigroup 沒有 empty value 所以不是 monoid!

Rewrite concatAll

記得前篇提到過的 concatAll 嗎? 如果該 Type 是 Monoid,由於 Monoid 本身一定有 empty method,所以我們在實作 concatAll 的時候,就可以省去 initValue 做為參數傳入,我們改寫一下吧!

const concatAll = R.curry((m, arr) => 
    arr.map(m).reduce((acc, val) => acc.concat(val), m.empty()))

小結

感謝大家閱讀

NEXT: Functor

Reference

  1. Semigroup

上一篇
Day 12 - Semigroup I
下一篇
Day 14 - Functor
系列文
Functional Programming For Everyone30

尚未有邦友留言

立即登入留言