ethanresnick · January 20, 2020 09:12
diff --git a/src.ts b/src.ts
 /**
 * This is a monoid over _all elements in the JS programming language_.
 * It's not really useful on its own, and it's a bit of a hack, but it's valid
 * and maybe kinda cool. Here's how it works:
 *
 * 1) it lifts non-lists into a list, like:
 *
 *      1234 `mappend` { a: true } === [1234, { a: true }]
 *
 * 2) then, if given a list, it extracts the items from the list before adding
 *    them to a returned/concatted list (i.e. it does a concat + flatten):
 *
 *      ([1,2] `mappend` 3) == (1 `mappend` [2, 3]) == ([1,2] `mappend` [3]) == [1,2,3]
 *
 *    It has to do that flattening because, if it simply wrapped the two items
 *    in a list unconditionally, it wouldn't be associative, i.e. we'd get: 
 * 
 *      (a `mappend` b) `mappend` c == [[a, b], c]
 *
 *    whereas the other grouping would produce:
 *
 *      (a `mappend` (b `mappend` c)) === [a, [b, c]].
 *
 * 3) finally, if one input is the empty list, it doesn't do the normal wrapping
 *    of the extracted items into a list. I.e., 
 *    
 *      (4 `mappend` []) == ([] `mappend` 4) == 4
 *
 *      (4 `mappend` []) != [4] // key
 *    
 *    The reason for this quirk is that we need an identity element. Another 
 *    valid choice would've been to just invent an identity element out of thin
 *    air by defining a custom symbol, but I'm not sure if that variant is more
 *    ergonomic or less. The advantage is that it makes `mappend`'s behavior
 *    with lists more consistent and explicable: "if one operand is a list, its
 *    items are extracted and added to a new list along with the value of the
 *    other operand (or the values extracted from it, if it's also a list).
 *    That new list is then returned." However, it's disadvantage is that it 
 *    introduces a new value that callers have to know about and get access to,
 *    and still does create another case: "If either operand is the empty 
 *    symbol, return the other operand [even if it's also the empty symbol]."
 * 
 * The reason to have a monoid like this is that it might let you produce the 
 * final output value you want just by `mappending`, whereas other monoids are
 * more limited in the values they contain. E.g., the list monoid will only 
 * contain lists, but this holds all JS values. However, in practice, I find 
 * that the behaviors that this `mappend` has to resort to -- sometimes lifting
 * its operands up into a list; sometimes extracting its arguments from a list;
 * and sometimes (when given an identity operand) doing neither -- are too weird
 * to make it worth using. The mental model that it requires on the programmer
 * is just confusing/hard to get right.
 */
 export const mempty = []
 export const mappend = <T extends unknown, U extends unknown>(a: T, b: U) =>
  (a === mempty ? b : b === mempty ? a : [a, b].flat()) as Concat<T, U>

 export const foldList = (list: unknown[]) => list.reduce(mappend, mempty)

 // prettier-ignore
 export type Concat<A, B> =
  (A extends typeof mempty
    ? B
    : (B extends typeof mempty
      ? A
      : (A extends any[]
          ? (B extends any[]
              ? (A[number] | B[number])[]
              : (A[number] | B)[])
          : (B extends any[]
              ? (A | B[number])[]
              : (A | B)[]))))
diff --git a/test.ts b/test.ts
 import fc = require('fast-check')
 import { expect } from 'chai'
 import * as Concat from '.....'

 describe('Concat monoid', () => {
  describe('mappend', () => {
    it('should be associative', async () => {
      fc.assert(
        fc.property(fc.anything(), fc.anything(), fc.anything(), (a, b, c) => {
          const leftAssociate = Concat.mappend(Concat.mappend(a, b), c)
          const rightAssociate = Concat.mappend(a, Concat.mappend(b, c))
          expect(rightAssociate).to.deep.eq(leftAssociate)
        })
      )
    })
  })

  describe('mempty', () => {
    it('should be a left and right identity for mappend', () => {
      fc.assert(
        fc.property(fc.anything(), (it) => {
          const leftId = Concat.mappend(Concat.mempty, it)
          const rightId = Concat.mappend(it, Concat.mempty)
          expect(leftId).to.deep.eq(rightId)
          expect(rightId).to.deep.eq(it)
        })
      )
    })
  })
 })
	/**
	* This is a monoid over _all elements in the JS programming language_.
	* It's not really useful on its own, and it's a bit of a hack, but it's valid
	* and maybe kinda cool. Here's how it works:
	*
	* 1) it lifts non-lists into a list, like:
	*
	* 1234 `mappend` { a: true } === [1234, { a: true }]
	*
	* 2) then, if given a list, it extracts the items from the list before adding
	* them to a returned/concatted list (i.e. it does a concat + flatten):
	*
	* ([1,2] `mappend` 3) == (1 `mappend` [2, 3]) == ([1,2] `mappend` [3]) == [1,2,3]
	*
	* It has to do that flattening because, if it simply wrapped the two items
	* in a list unconditionally, it wouldn't be associative, i.e. we'd get:
	*
	* (a `mappend` b) `mappend` c == [[a, b], c]
	*
	* whereas the other grouping would produce:
	*
	* (a `mappend` (b `mappend` c)) === [a, [b, c]].
	*
	* 3) finally, if one input is the empty list, it doesn't do the normal wrapping
	* of the extracted items into a list. I.e.,
	*
	* (4 `mappend` []) == ([] `mappend` 4) == 4
	*
	* (4 `mappend` []) != [4] // key
	*
	* The reason for this quirk is that we need an identity element. Another
	* valid choice would've been to just invent an identity element out of thin
	* air by defining a custom symbol, but I'm not sure if that variant is more
	* ergonomic or less. The advantage is that it makes `mappend`'s behavior
	* with lists more consistent and explicable: "if one operand is a list, its
	* items are extracted and added to a new list along with the value of the
	* other operand (or the values extracted from it, if it's also a list).
	* That new list is then returned." However, it's disadvantage is that it
	* introduces a new value that callers have to know about and get access to,
	* and still does create another case: "If either operand is the empty
	* symbol, return the other operand [even if it's also the empty symbol]."
	*
	* The reason to have a monoid like this is that it might let you produce the
	* final output value you want just by `mappending`, whereas other monoids are
	* more limited in the values they contain. E.g., the list monoid will only
	* contain lists, but this holds all JS values. However, in practice, I find
	* that the behaviors that this `mappend` has to resort to -- sometimes lifting
	* its operands up into a list; sometimes extracting its arguments from a list;
	* and sometimes (when given an identity operand) doing neither -- are too weird
	* to make it worth using. The mental model that it requires on the programmer
	* is just confusing/hard to get right.
	*/
	export const mempty = []
	export const mappend = <T extends unknown, U extends unknown>(a: T, b: U) =>
	(a === mempty ? b : b === mempty ? a : [a, b].flat()) as Concat<T, U>

	export const foldList = (list: unknown[]) => list.reduce(mappend, mempty)

	// prettier-ignore
	export type Concat<A, B> =
	(A extends typeof mempty
	? B
	: (B extends typeof mempty
	? A
	: (A extends any[]
	? (B extends any[]
	? (A[number] \| B[number])[]
	: (A[number] \| B)[])
	: (B extends any[]
	? (A \| B[number])[]
	: (A \| B)[]))))
	import fc = require('fast-check')
	import { expect } from 'chai'
	import * as Concat from '.....'

	describe('Concat monoid', () => {
	describe('mappend', () => {
	it('should be associative', async () => {
	fc.assert(
	fc.property(fc.anything(), fc.anything(), fc.anything(), (a, b, c) => {
	const leftAssociate = Concat.mappend(Concat.mappend(a, b), c)
	const rightAssociate = Concat.mappend(a, Concat.mappend(b, c))
	expect(rightAssociate).to.deep.eq(leftAssociate)
	})
	)
	})
	})

	describe('mempty', () => {
	it('should be a left and right identity for mappend', () => {
	fc.assert(
	fc.property(fc.anything(), (it) => {
	const leftId = Concat.mappend(Concat.mempty, it)
	const rightId = Concat.mappend(it, Concat.mempty)
	expect(leftId).to.deep.eq(rightId)
	expect(rightId).to.deep.eq(it)
	})
	)
	})
	})
	})