How to idomatically reduce an Array into a Map

[edalex-ian]

Hey All,

Still relatively new to fp-ts and indeed a good number of its FP paradigms. But from what I understand, I have this itch that what I've written below can possibly make use of Monoids and Foldables to become more elegant.

What I have is a function which given an array will produce a map which summarises the number of occurrences of each value in the array. For example if I had an array of [1, 2, 3, 2, 3, 2, 4] I'd receive a map of:

• 1 -> 1
• 2 -> 3
• 3 -> 2
• 4 -> 1

The code is:

/**
 * Produces a `Map` summarising the number of occurrences in an array identified by keys generated
 * with `by`.
 */
const countBy =
  <T, K>(eq: Eq<K>, by: (a: T) => K) =>
  (as: T[]): Map<K, number> =>
    pipe(
      as,
      A.map(by),
      A.reduce<K, Map<K, number>>(new Map(), (m, k: K) => {
        const count: number = pipe(
          m,
          M.lookup(eq)(k),
          O.map((n) => n + 1),
          O.getOrElse<number>(() => 1)
        );

        return pipe(m, M.upsertAt(eq)(k, count));
      })
    );

Usage in the above example is:

const occurrences: Map<number, number> = pipe(
  vals,
  groupBy<number, number>(N.Eq, identity)
);

(Obviously in that simple case by seems redundant, but that supports also having arrays of objects etc.)

The thing is, that pipe in the middle producing count looks to me to almost fit the bill of a Monoid. Something like:

{
  concat: (x, y) => x + 1; // but is that even valid to ignore y
  empty: 1;
}

But as far as I currently understand, using a Monoid in any kind of fold has to go from type A -> A. But seeing I want to fold over an Array and go to a Map I need to go from A -> B. Do I need to do some kind of lifting?

Well, as hopefully you can see, I'm confused. Is anyone able to point me to the idiomatic approach for this? I'm hoping in doing so you'll lift me up a level in understanding the next bit on my FP journey.

Cheers.

[mlegenhausen]

I would recommend to take a look at the groupBy function from ReadonlyNonEmptyArray and adapt it to the use with Map. Then you can simply map over all grouped values and determine the array size of each entry.

You should also think about if you really need a Map cause a look up or modification is more expensive as for example for a Record. If you would consider using a Record your example can be reduced to this:

import { pipe } from 'fp-ts/function'
import * as RNEA from 'fp-ts/ReadonlyNonEmptyArray'
import * as RA from 'fp-ts/ReadonlyArray'
import * as RR from 'fp-ts/ReadonlyRecord'

pipe([1, 2, 3, 2, 3, 2, 4], RNEA.groupBy(String), RR.map(RA.size)) // { '1': 1, '2': 3, '3': 2, '4': 1 }

There is also a discussion in the issue tracker about Map vs Record in fp-ts.

If you really want to use a Monoid to accomplish the same you could use fromFoldableMap and do the following:

import * as RA from 'fp-ts/ReadonlyArray'
import * as RR from 'fp-ts/ReadonlyRecord'
import * as n from 'fp-ts/number'

RR.fromFoldableMap(n.MonoidSum, RA.Foldable)([1, 2, 3, 2, 3, 2, 4], n => [String(n), 1])

There is also a version for Map that looks like this:

import { pipe, tuple } from 'fp-ts/function'
import * as n from 'fp-ts/number'
import * as RA from 'fp-ts/ReadonlyArray'
import * as MR from 'fp-ts/ReadonlyMap'

const a = pipe(
  [1, 2, 3, 2, 3, 2, 4],
  RA.map(n => tuple(n, 1)),
  MR.fromFoldable(n.Eq, n.MonoidSum, RA.Foldable)
)

[edalex-ian]

What an excellent answer. Thank-you very much for the thought out code blocks, and especially for both addressing my interest in understanding the use of Monoids and Foldables, while still providing a more succinct approach.

I did take the time to read the link regarding Map vs Record and will look more into the use of fp-ts utilities in that area. And it was great to see another use of tuple as it's one of those entries in function that lack any doco but I see it thrown around a lot.

Lastly you raise questions around the use of ReadonlyXyz, but I think I'll capture that in another stand-alone discussion.

Thanks heaps! 🎉