# Proposal: Make Semigroup as a superclass of Monoid

Edward Kmett ekmett at gmail.com
Mon May 4 20:17:43 UTC 2015

The issue with a LiquidHaskell solution in this space, aside from the fact
that it is an experiment that isn't part of the compiler or the language
that we have, and uses assumptions about the way numbers work that don't
hold for the ones we have, is that it is terribly invasive.

In order to use it everything that ever wants to work with your shiny new
non-empty list type needs to be written in LiquidHaskell to prove the
non-empty invariant still holds. Refinement types are notoriously hard to
use. On the other-hand a type like NonEmpty satisfies that invariant
trivially: There is no empty constructor.

The price of this is that it is a different data type, with different
operations.

I love LiquidHaskell, but I'd be very hesitant to do anything or rather to
not do anything predicated on its existence.

-Edward

On Mon, May 4, 2015 at 2:37 PM, Reid Barton <rwbarton at gmail.com> wrote:

> On Mon, May 4, 2015 at 12:58 PM, David Feuer <david.feuer at gmail.com>
> wrote:
>
>> abstract? Then something like Liquid Haskell could be used to define it
>> better.
>>
> There are (at least) two possible designs for a "non-empty list type".
>
> 1. A refinement type (as in LiquidHaskell) of [t] whose values include
> only the non-empty lists. Call it NonEmptyLiquid t. You can pass a
> NonEmptyLiquid t to a function that expects a [t], and you can pass a [t]
> to a function that expects a NonEmptyLiquid [t] if the compiler can prove
> that your [t] is nonempty. If it can't then you can add a runtime test for
> emptiness and in the non-empty case, the compiler will know the list is
> non-empty.
>
> 2. A new type NonEmptySolid t that is totally unrelated to [t] like you
> can define in Haskell today. The advantage is that NonEmptySolid is a
> full-fledged type constructor that can have instances, be passed to other
> type constructors and so on. The disadvantage is that you need to
> explicitly convert in your program (and possibly do a runtime conversion
> also) in either direction between [t] and NonEmptySolid t.
>
> I think most people who want a "non-empty list type" want 1, not 2. Option
> 2 is bad for API design because it forces the users of your library to care
> exactly as much as you do about non-emptiness. If you imagine adding other
> sorts of lists like infinite lists, fixed-length or bounded-length lists,
> lists of even length etc. then it quickly becomes clear that having such an
> array of incompatible list types is not the way to go. We just want lists
> to be lists, but we also want the compiler to make sure we don't try to
> take the head of an empty list.
>
> Those who use a NonEmpty type prefer option 2 over option 0 "type
> NonEmptyGas t = [t] -- and just hope"; but that doesn't mean they prefer
> option 2 over option 1. Those who really want option 2 can also define it
> as a newtype wrapper on option 1, as you noted.
>
> So, to answer your question, no, it wouldn't really make a difference if
> the NonEmpty type was abstract. That would just smooth the transition to a
> design that I think people don't really want.
>
> Finally, let me reiterate that there seem to be no advantages to moving a
> NonEmpty type into base rather than into its own small package. We don't
> need base to swallow up every small popular package.
>
> Regards,
> Reid Barton
>
> _______________________________________________
> Libraries mailing list