Type-classes for Prepend (Cons) and Append (Snoc) operations

Much as I disapprove of overusing Ed Kmett's name like a magic totem to justify a decision, he eloquently makes the case for Prepend and Append type-classes in this 2009 slide deck.

He calls them Reducers, and the operations Cons and Snoc, but the idea is the same. He positions them as optimizations from Monoidal combine on the left and right:

A +: M[A] => M[A]  //prepend
M[A] :+ A => M[A]   //append
M |+| M.pure(a) => M[A]  //can be done via Monoid combine, but less efficiently since we lift the `a` into a container only to throw it away

It's not a huge difference, but it adds up in a hot loop. new is the new slow, so I hear.

It is now 2023 and we still need this. We see tutorials for WriterT (or Validation) where people are emitting Chain[String] rather than String so that they can monoidally combine the incoming data.

Another definition of Cons/Snoc typeclasses, again from Mr Kmett, is found in the Haskell Lens package.

I admit I've already asked for this before, but that issue got a bit distracted by another unrelated idea.

Start with the earlier Cats issue #1360, then read the linked slide deck and Haskell Lens Cons documentation. Determine the intended Prepend and Append type-class scope and how it should differ from the ideas discussed previously; done means the design and implementation boundaries are agreed.