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