如何fold/reduce一张地图？

Question

我希望能够 fold/reduce 一个 Map，就像我可以使用 Array 和 Set 一样。我看到的最接近的是一个叫做 getFoldableWithIndex 的东西，但我不知道如何使用它或让它与 Typescript 一起编译。我觉得烦人的一件事是它需要一个 ORD。也许这是使函数更具确定性所必需的，但排序对于许多 folding/reducing 任务并不重要并且会降低性能。我的解决方法是离开 fp-ts，生成一个数组或可迭代的 [key,value] 对，然后对其进行简单的 reduce 以找到年龄最大的人。

import { map as MAP, ord as ORD } from "fp-ts"

type Person = string;
type Age = number;

const oldestPerson = (ps:Map<Person, Age>) =>
  pipe(ps, MAP.getFoldableWithIndex<Person>(ORD.fromCompare<Person>((a,b)=>0)))......

刚注意到最近未发布的版本支持 reduce。仍然不知道为什么需要 ORD 或如何使用 getFolderableWithIndex 或何时发布新版本。

https://github.com/gcanti/fp-ts/blob/2.11/src/ReadonlyMap.ts

Answer 1

您可以：

import { ordNumber } from 'fp-ts/Ord'

type Name = string
type Age = number
type Persons = Map<Name, Age>
const persons: Persons = new Map()

persons.set('Joao', 13)
persons.set('Roberto', 20)

const sorted = new Map(
  [...persons.entries()].sort((a, b) => ordNumber.compare(b[1], a[1]))
)

但是，请务必注意，在此示例中，您通过调用 .set.

来改变 persons 变量

更纯粹的函数式方法是：

import { ordNumber } from 'fp-ts/Ord'
import { Eq as StringEq } from 'fp-ts/string'
import * as F from 'fp-ts/function'
import * as M from 'fp-ts/Map'

type Name = string
type Age = number
const insertIntoPersons = M.upsertAt(StringEq)

const persons = F.pipe(
  new Map<Name, Age>(),
  insertIntoPersons('Joao', 13),
  insertIntoPersons('Roberto', 20)
)

const sorted = new Map(
  [...persons.entries()].sort((a, b) => ordNumber.compare(b[1], a[1]))
)

Answer 2

如果您想留在“fp-ts 内”，您可以执行以下操作：

import { flow, pipe, tuple } from "fp-ts/function"
import * as Mn from "fp-ts/Monoid"
import * as N from "fp-ts/number"
import * as O from "fp-ts/Option"
import * as Ord from "fp-ts/Ord"
import * as RM from "fp-ts/ReadonlyMap"
import * as RT from "fp-ts/ReadonlyTuple"
import * as Sg from "fp-ts/Semigroup"
import * as S from "fp-ts/string"

type Person = string
type Age = number
type PersonAge = readonly [Person, Age]

const ordByAge: Ord.Ord<PersonAge> = pipe(N.Ord, Ord.contramap(RT.snd))

const monoidMaxByAge: Mn.Monoid<O.Option<PersonAge>> = pipe(
  ordByAge,
  Sg.max,
  O.getMonoid
)

const oldestPerson = (ps: ReadonlyMap<Person, Age>) =>
  pipe(
    ps,
    RM.foldMapWithIndex(S.Ord)(monoidMaxByAge)(flow(tuple, O.some)),
    O.map(RT.fst)
  )

这很冗长，没有解决您对性能的担忧。

One thing I find annoying is that it requires an ORD. Maybe this is required to make the function more deterministic but sorting is not important for many folding/reducing tasks and decreases performance.

你说得对，这是关于决定论的。本机 JS Map 按插入顺序存储条目，因此如果没有 Ord 键实例，此 oldestPerson 函数可能会为两个给定的 Map 产生不同的结果除了广告订单。我会认为这是意外行为。

这是我希望持有的内容：

import * as assert from "assert"

const aliceBob: ReadonlyMap<Person, Age> = new Map([
  ["Alice", 25],
  ["Bob", 25],
])

const bobAlice: ReadonlyMap<Person, Age> = new Map([
  ["Bob", 25],
  ["Alice", 25],
])

const emptyMap: ReadonlyMap<Person, Age> = new Map([])

assert.deepStrictEqual(oldestPerson(aliceBob), oldestPerson(bobAlice))
assert.deepStrictEqual(oldestPerson(emptyMap), O.none)

我同意 fp-ts/ReadonlyMap 中的很多函数都不是很有效，我认为它们只是本机数据结构的最小“功能性 API”包装器这与不变性和确定性并不能很好地发挥作用。如果性能更受关注，我可能会像您一样使用本机方法。

something called getFoldableWithIndex but I don't know how to use it or get it to compile with Typescript.

getFoldableWithIndex 将 return 一个 FoldableWithIndex 类型的 class 实例，它在这里对您没有用。这是一个 value ，您可以将其作为参数传递给需要 FoldableWithIndex 实例的函数，我什至不确定是否有一个很好的例子。在 fp-ts/FoldableWithIndex 中有一个 traverse_ in fp-ts/Foldable which takes a Foldable instance, but no corresponding traverseWithIndex_, though that hypothetical function would take a FoldableWithIndex instance. There are some functions，但那些是关于 将两个 FoldableWithIndex 实例组合成另一个实例（这在这里没有用）。

您可以直接使用 FoldableWithIndex：类型 class 实例是一个带有 uncurried foldMapWithIndex 方法的对象，所以如果您想使原始片段 更加冗长 ，您可以这样做：

const oldestPerson = (ps: ReadonlyMap<Person, Age>) => pipe( RM.getFoldableWithIndex(S.Ord).foldMapWithIndex(monoidMaxByAge)( ps, flow(tuple, O.some) ), O.map(RT.fst) )

但这些实例并不是真的要直接在 pipe 中使用，这就是为什么我会使用顶级 RM.foldMapWithIndex。有关 classes in fp-ts 的工作原理的更多信息 here.

如何fold/reduce一张地图？

How to fold/reduce a map?

fp-ts