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