F

fp-ts入门：半群

2025-06-05

fp-ts入门：半群

由于半群是函数式编程的基本抽象，因此这篇博文将比平时更长。

一般定义

半群是一对，(A, *)其中A是非空集，并且是上的*二元结合A运算，即以的两个元素A作为输入并返回的元素A作为输出的函数……

*: (x: A, y: A) => A
Enter fullscreen mode Exit fullscreen mode

... 而结合律意味着方程

(x * y) * z = x * (y * z)
Enter fullscreen mode Exit fullscreen mode

对中的所有x,y都成立。zA

结合律只是告诉我们，我们不必担心表达式的括号，可以写成x * y * z。

半群抓住了可并行运算的本质

有很多半群的例子：

  • (number, *)*通常的数字乘法在哪里
  • (string, +)+通常的字符串连接在哪里
  • (boolean, &&)&&通常的连词在哪里

等等。

类型类定义

与模块中包含的fp-ts类型类一样，它以 TypeScript 的形式实现，其中操作名为Semigroupfp-ts/Semigroupinterface*concat

interface Semigroup<A> {
  concat: (x: A, y: A) => A
}
Enter fullscreen mode Exit fullscreen mode

下列定律必须成立

  • 结合律：，concat(concat(x, y), z) = concat(x, concat(y, z))对所有x，，在yzA

这个名字concat对于数组来说有特殊的意义（见下文），但是，根据上下文和A我们实现实例的类型，半群运算可以用不同的含义来解释

  • “级联”
  • “合并”
  • “融合”
  • “选择”
  • “添加”
  • “替代”

等等。

实例

这就是我们如何实现半群(number, *)

/** number `Semigroup` under multiplication */
const semigroupProduct: Semigroup<number> = {
  concat: (x, y) => x * y
}
Enter fullscreen mode Exit fullscreen mode

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

/** number `Semigroup` under addition */
const semigroupSum: Semigroup<number> = {
  concat: (x, y) => x + y
}
Enter fullscreen mode Exit fullscreen mode

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

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

我找不到实例！

如果给定一个类型A，你找不到 的结合运算怎么办A？你可以为每个类型创建一个（平凡的）半群实例，只需使用以下构造

/** Always return the first argument */
function getFirstSemigroup<A = never>(): Semigroup<A> {
  return { concat: (x, y) => x }
}

/** Always return the second argument */
function getLastSemigroup<A = never>(): Semigroup<A> {
  return { concat: (x, y) => y }
}
Enter fullscreen mode Exit fullscreen mode

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

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

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

function of<A>(a: A): Array<A> {
  return [a]
}
Enter fullscreen mode Exit fullscreen mode

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

注意：这concat是本机数组方法，它解释了操作名称的初始选择Semigroup。

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

源自Ord

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

实际上两个可能的半群

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

/** Takes the minimum of two values */
const semigroupMin: Semigroup<number> = getMeetSemigroup(ordNumber)

/** Takes the maximum of two values  */
const semigroupMax: Semigroup<number> = getJoinSemigroup(ordNumber)

semigroupMin.concat(2, 1) // 1
semigroupMax.concat(2, 1) // 2
Enter fullscreen mode Exit fullscreen mode

让我们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)
  })
}
Enter fullscreen mode Exit fullscreen mode

不过，这基本上只是样板代码。好消息是，我们可以Semigroup为结构体构建一个实例，就像为每个字段Point提供一个实例一样。Semigroup

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

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

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

我们可以继续使用getStructSemigroup刚刚定义的实例

type Vector = {
  from: Point
  to: Point
}

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

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

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

/** `semigroupAll` is the boolean semigroup under conjunction */
const semigroupPredicate: Semigroup<(p: Point) => boolean> = getFunctionSemigroup(
  semigroupAll
)<Point>()
Enter fullscreen mode Exit fullscreen mode

现在我们可以“合并” Points上的两个谓词

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
Enter fullscreen mode Exit fullscreen mode

折叠式的

根据定义，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
Enter fullscreen mode Exit fullscreen mode

类型构造函数的半群

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

x y 连接（x，y）
没有任何 没有任何 没有任何
一些 没有任何 没有任何
没有任何 一些 没有任何
一些 一些(b) ？

最后一个有问题，我们需要一些东西来“合并”两个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)
Enter fullscreen mode Exit fullscreen mode

附录

我们已经看到，当我们想要“连接”、“合并”或“组合”（无论哪个词给你最好的直觉）多个数据成一个时，半群都能帮助我们。

让我们用最后一个例子来总结一下（改编自Fantas、Eel 和规范 4：半群）

假设您正在构建一个系统来存储如下所示的客户记录：

interface Customer {
  name: string
  favouriteThings: Array<string>
  registeredAt: number // since epoch
  lastUpdatedAt: number // since epoch
  hasMadePurchase: boolean
}
Enter fullscreen mode Exit fullscreen mode

无论出于何种原因，你最终可能会得到同一个人的重复记录。我们需要的是一个合并策略。这就是半群的意义所在

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({
  // keep the longer name
  name: getJoinSemigroup(contramap((s: string) => s.length)(ordNumber)),
  // accumulate things
  favouriteThings: getMonoid<string>(), // <= getMonoid returns a Semigroup for `Array<string>` see later
  // keep the least recent date
  registeredAt: getMeetSemigroup(ordNumber),
  // keep the most recent date
  lastUpdatedAt: getJoinSemigroup(ordNumber),
  // Boolean semigroup under disjunction
  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 }
*/
Enter fullscreen mode Exit fullscreen mode

该函数getMonoid返回一个Semigroupfor Array<string>。实际上，它返回的不仅仅是一个半群：一个幺半群。

那么什么是幺半群？下一篇文章我会讨论幺半群

文章来源：https://dev.to/gcanti/getting-started-with-fp-ts-semigroup-2mf7
Devto 翻译
PREV
开始使用 fp-ts：Eq
NEXT
开始使用 fp-ts：函子函数作为程序其中约束 B = F<C> 导致函子函子 fp-ts 中的函子一般问题解决了吗？