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

[benhutchison]

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.

[armanbilge]

We have prependK and appendK on Alternative with those signatures. Sergey has optimized their implementations for standard collections in #4052 and #4055. Does that address your usecase? Thanks!

cats/core/src/main/scala/cats/NonEmptyAlternative.scala

Lines 26 to 46 in ba48b63

	/**
	* Lift `a` into `F[_]` and prepend it to `fa`.
	*
	* Example:
	* {{{
	* scala> NonEmptyAlternative[List].prependK(1, List(2, 3, 4))
	* res0: List[Int] = List(1, 2, 3, 4)
	* }}}
	*/
	def prependK[A](a: A, fa: F[A]): F[A] = combineK(pure(a), fa)
	/**
	* Lift `a` into `F[_]` and append it to `fa`.
	*
	* Example:
	* {{{
	* scala> NonEmptyAlternative[List].appendK(List(1, 2, 3), 4)
	* res0: List[Int] = List(1, 2, 3, 4)
	* }}}
	*/
	def appendK[A](fa: F[A], a: A): F[A] = combineK(fa, pure(a))

[benhutchison]

Oh that's nice, didn't notice, thanks to @satorg 🙏

That seems to address my wish list above, and the intent of #1360 ✅

While on this topic, what about the co-operations to pull items out of containers, perhaps called "uncons" and "unsnoc", F[A] => (F[A], A)?

I see we have an implementation for Chain, but no abstraction for it afaict.

[armanbilge]

While on this topic, what about the co-operations to pull items out of containers

You can use Comonad#extract to e.g. get the head of a NonEmptyList. But off the top of my head I'm not aware of any operations for getting the tail, or the (init, last).

[satorg]

Also, perhaps as a work-around, there's Foldable#toIterable that can provide access to head and tail, but the latter will be just Iterable of course, not F[_] anymore.

[benhutchison]

• When I tried rewriting code written in terms of List to M: Alternative, I got stuck where the lists (used as stacks) get destructured to remove the head. Naturally Foldable#toIterable doesn't express the efficient destructure of List/Chain -like containers.

• I do think the complimentary co- operations Uncons and Unsnoc are valuable in some contexts, but should I create a separate issue as its drifted from the title?

• What would be the correct type-class for destructuring duals to prependK & appendK?

  Comonad seems too specific. Would a CoSemigroupK define some splitK dual to combineK? And CoNonEmptyAlternative define a unprependK and unappendK (perhaps with aliases uncons and unsnoc)?