Getting started with fp-ts: Semigroup

原文：https://dev.to/gcanti/getting-started-with-fp-ts-semigroup-2mf7

这篇文章的标题是《Getting started with fp-ts: Semigroup》，由Giulio Canti在2019年3月13日发表。由于半群是函数式编程的一个基本抽象，这篇博客文章会比平时更长。

一般定义

半群是一对(A, *)，其中A是一个非空集合，而*是一个在A上的二元结合操作，即一个函数，它接受两个A中的元素作为输入，并返回一个A中的元素作为输出...

*: (x: A, y: A) => A

...而结合性意味着下面的等式

(x * y) * z = x * (y * z)

对所有A中的x，y，z都成立。

结合性简单地告诉我们，我们不需要担心表达式的括号化，并且可以写x * y * z。

半群捕捉了可并行化操作的本质。

半群的例子有很多：

• (number, *)，其中*是数字的通常乘法

• (string, +)，其中+是字符串的通常连接

• (boolean, &&)，其中&&是布尔值的通常逻辑与

等等。

类型类定义

像往常一样，在fp-ts中，类型类Semigroup包含在fp-ts/Semigroup模块中，被实现为TypeScript的interface，其中操作*被命名为concat：

interface Semigroup<A> {
  concat: (x: A, y: A) => A
}

必须满足以下法则：

• 结合性：concat(concat(x, y), z) = concat(x, concat(y, z))，对于所有A中的x，y，z。

名称concat对于数组来说特别有意义（稍后见），但是，根据上下文和我们正在实现实例的类型A，半群操作可以有多种解释：

• “连接”

• “合并”

• “融合”

• “选择”

• “加法”

• “替换”

等等。

实例

以下是我们如何实现半群(number, *)：

/** 数字的乘法 `Semigroup` */
const semigroupProduct: Semigroup<number> = {
  concat: (x, y) => x * y
}

注意，你可以为同一个类型定义不同的半群实例。这里是半群(number, +)的实现，其中+是数字的通常加法：

/** 数字的加法 `Semigroup` */
const semigroupSum: Semigroup<number> = {
  concat: (x, y) => x + y
}

另一个例子，这次是字符串：

const semigroupString: Semigroup<string> = {
  concat: (x, y) => x + y
}

我找不到实例！

如果对于给定的类型A，你找不到一个在A上的结合操作怎么办？你可以使用以下构造为每种类型创建一个（平凡的）半群实例：

/** 总是返回第一个参数 */
function getFirstSemigroup<A = never>(): Semigroup<A> {
  return { concat: (x, y) => x }
}

/** 总是返回第二个参数 */
function getLastSemigroup<A = never>(): Semigroup<A> {
  return { concat: (x, y) => y }
}

另一种技术是为Array<A>定义一个半群实例，称为A的自由半群。

function getArraySemigroup<A = never>(): Semigroup<Array<A>> {
  return { concat: (x, y) => x.concat(y) }
}

并将A的元素映射到Array<A>的单例元素：

function of<A>(a: A): Array<A> {
  return [a]
}

（*）严格来说，是非空数组的A的半群实例。

注意。这里的concat是原生数组方法，这多少解释了最初选择Semigroup操作名称的原因。

A的自由半群是由所有可能的非空有限序列的A元素组成的半群。

从Ord派生

还有另一种方法可以为类型A构建半群实例：如果我们已经有了A的Ord实例，那么我们就可以“将其”转换为半群。

实际上有两种可能的半群：

import { ordNumber } from 'fp-ts/Ord'
import { getMeetSemigroup, getJoinSemigroup } from 'fp-ts/Semigroup'

/** 取两个值中的最小值 */
const semigroupMin: Semigroup<number> = getMeetSemigroup(ordNumber)

/** 取两个值中的最大值 */
const semigroupMax: Semigroup<number> = getJoinSemigroup(ordNumber)

semigroupMin.concat(2, 1) // 1
semigroupMax.concat(2, 1) // 2

让我们为更复杂的类型写一些Semigroup实例：

type Point = {
  x: number
  y: number
}

const semigroupPoint: Semigroup<Point> = {
  concat: (p1, p2) => ({
    x: semigroupSum.concat(p1.x, p2.x),
    y: semigroupSum.concat(p1.y, p2.y)
  })
}

这主要是样板代码。好消息是，如果我们能为每个字段提供一个Semigroup实例，我们可以为像Point这样的结构体构建一个Semigroup实例。

事实上，fp-ts/Semigroup模块导出了一个getStructSemigroup组合器：

import { getStructSemigroup } from 'fp-ts/Semigroup'

const semigroupPoint: Semigroup<Point> = getStructSemigroup({
  x: semigroupSum,
  y: semigroupSum
})

我们可以继续用刚刚定义的实例来喂getStructSemigroup：

type Vector = {
  from: Point
  to: Point
}

const semigroupVector: Semigroup<Vector> = getStructSemigroup({
  from: semigroupPoint,
  to: semigroupPoint
})

getStructSemigroup并不是fp-ts提供的唯一组合器，这里有一个组合器允许我们派生函数的Semigroup实例：给定一个S的实例，我们可以派生出函数(a: A) => S的实例，对于所有A：

import { getFunctionSemigroup, Semigroup, semigroupAll } from 'fp-ts/Semigroup'

/** `semigroupAll`是在逻辑与下的布尔半群 */
const semigroupPredicate: Semigroup<(p: Point) => boolean> = getFunctionSemigroup(
  semigroupAll
)<Point>()

现在我们可以“合并”两个关于Point的谓词：

const isPositiveX = (p: Point): boolean => p.x >= 0
const isPositiveY = (p: Point): boolean => p.y >= 0

const isPositiveXY = semigroupPredicate.concat(isPositiveX, isPositiveY)

isPositiveXY({ x: 1, y: 1 }) // true
isPositiveXY({ x: 1, y: -1 }) // false
isPositiveXY({ x: -1, y: 1 }) // false
isPositiveXY({ x: -1, y: -1 }) // false

折叠

根据定义，concat只适用于两个A元素，如果我们想要连接更多的元素怎么办？

fold函数接受一个半群实例，一个初始值和一个元素数组：

import { fold, semigroupSum, semigroupProduct } from 'fp-ts/Semigroup'

const sum = fold(semigroupSum)

sum(0, [1, 2, 3, 4]) // 10

const product = fold(semigroupProduct)

product(1, [1, 2, 3, 4]) // 24

类型构造子的半群

如果我们想要“合并”两个Option<A>怎么办？有四种情况：

最后一个有问题，我们需要一些东西来“合并”两个A。

这就是Semigroup的作用！我们可以要求一个A的半群实例，然后派生一个Option<A>的半群实例。这就是getApplySemigroup组合器的工作原理：

import { semigroupSum } from 'fp-ts/Semigroup'
import { getApplySemigroup, some, none } from 'fp-ts/Option'

const S = getApplySemigroup(semigroupSum)

S.concat(some(1), none)// none 
S.concat(some(1), some(2)) // some(3)

附录

我们已经看到，半群帮助我们任何时候我们想要“连接”、“合并”或“组合”（任何给你最好直觉的词）几个数据成一个。 让我们用一个最终的例子来总结（改编自Fantas, Eel, 和 Specification 4: Semigroup）。 假设你正在构建一个系统，其中你存储的客户记录如下：

interface Customer {
  name: string
  favouriteThings: Array<string>
  registeredAt: number // 自epoch以来
  lastUpdatedAt: number // 自epoch以来
  hasMadePurchase: boolean
}

出于某种原因，你可能会为同一个人得到重复的记录。我们需要的是合并策略。这就是半群的全部内容。

import {
  Semigroup,
  getStructSemigroup,
  getJoinSemigroup,
  getMeetSemigroup,
  semigroupAny
} from 'fp-ts/Semigroup'
import { getMonoid } from 'fp-ts/Array'
import { ordNumber, contramap } from 'fp-ts/Ord'

const semigroupCustomer: Semigroup<Customer> = getStructSemigroup({
  // 保留更长的名字
  name: getJoinSemigroup(contramap((s: string) => s.length)(ordNumber)),
  // 积累事物
  favouriteThings: getMonoid<string>(), // <= getMonoid返回`Array<string>`的半群，稍后见
  // 保留最近日期
  registeredAt: getMeetSemigroup(ordNumber),
  // 保留最不近的日期
  lastUpdatedAt: getJoinSemigroup(ordNumber),
  // 在析取下的布尔半群
  hasMadePurchase: semigroupAny
})

semigroupCustomer.concat(
  {
    name: 'Giulio',
    favouriteThings: ['math', 'climbing'],
    registeredAt: new Date(2018, 1, 20).getTime(),
    lastUpdatedAt: new Date(2018, 2, 18).getTime(),
    hasMadePurchase: false
  },
  {
    name: 'Giulio Canti',
    favouriteThings: ['functional programming'],
    registeredAt: new Date(2018, 1, 22).getTime(),
    lastUpdatedAt: new Date(2018, 2, 9).getTime(),
    hasMadePurchase: true
  }
)
/*
{ name: 'Giulio Canti',
  favouriteThings: [ 'math', 'climbing', 'functional programming' ],
  registeredAt: 1519081200000, // new Date(2018, 1, 20).getTime()
  lastUpdatedAt: 1521327600000, // new Date(2018, 2, 18).getTime()
  hasMadePurchase: true }
*/

函数getMonoid返回Array<string>的Semigroup。实际上它返回的不仅仅是一个半群：一个单子。

那么什么是单子呢？在下一篇文章中，我将讨论单子。