3

What I mean is a device like a list:

mempty = [ ]
lift x = [x]
mappend = (++)

Is it merely IsList?

duplode
  • 33,731
  • 7
  • 79
  • 150
Ignat Insarov
  • 4,660
  • 18
  • 37

2 Answers2

6

Given the framing of your question, I would be inclined to characterise your lift...

(:[]) :: a -> [a]

... as reflecting how lists are an encoding of the free monoid for Haskell types. In particular, the universal property (illustrated by the diagram at the end of the Category Theory for Programmers chapter linked to above) implies that:

-- q is an arbitrary a -> m function, with m being an arbitrary monoid.
foldMap q . (:[]) = q

As far as the types go, Alternative might seem to also express what you are looking for: empty and (<|>) are generally expected to be monoidal operations, and pure from Applicative could be taken as your lift. However, I'm not sure if there is any connection that might be drawn between pure and the Alternative methods that would clarify the role of pure in such a construction. (On this latter point, you might find this tangentially related question which discusses the relationship between Alternative and Applicative interesting.)

duplode
  • 33,731
  • 7
  • 79
  • 150
  • 1
    Isn't there a little more to the universal property? For one thing, `foldMap f x <> foldMap f y = foldMap f (x <> y)` and `foldMap f mempty = mempty` (`foldMap` is a monoid morphism). But there's one more piece: uniqueness of `foldMap`. That basically says that *every* `f a` can be formed using `pure` and `Monoid` operations. – dfeuer Aug 07 '19 at 23:53
  • 1
    @dfeuer Yup, there is more to it. I wasn't, and I still am not, entirely sure about how to wire that to the context of this question; in the meantime, I have changed "means that" to "implies that" to better suggest it doesn't end there. – duplode Aug 08 '19 at 00:02
  • I do not actually think it necessarily has to be a free monoid. Since I am not requiring a projection to any other monoid, it may conflate elements as it wills. – Ignat Insarov Aug 08 '19 at 13:43
  • Also, actually I would like to have a class for free monoids indeed, but Alternative is usually lossy: it acts like `const`: `x <|> y = x` — in most all instances I have been dealing with so far, be it applicative parsers _(where this operator makes asymmetric choice)_ or monads _(where it is used when trying actions until the first successful)_. I propose instead that `IsList` is what we should consider the free monoid class, as it witnesses the isomorphism inbetween all the instances _(through List)_. – Ignat Insarov Aug 08 '19 at 17:12
  • @IgnatInsarov (1) If your lift is fully polymorphic on the element type (`a -> M a`), I don't think you can do any collapsing with it, except for sending everything to some `empty`. (2a) I don't feel there are enough noteworthy encodings of the free monoid to justify a separate type class. What we do have is `Foldable`, which says something broader: "this can be converted to the free monoid" (through either `toList` or `flip foldMap`). (2b) `Alternative` is indeed something quite different from the other possibilities we are considering. – duplode Aug 08 '19 at 20:24
2

You are talking about Alternative as @Robin Zigmond said:

instance Alternative [] where
    empty = []
    (<|>) = (++)

And if you want to know, it is also a MonadPlus: 

instance MonadPlus []
amalloy
  • 89,153
  • 8
  • 140
  • 205
developer_hatch
  • 15,898
  • 3
  • 42
  • 75
  • For the sake of completeness, I should mention that I *think* there is something of an analogy between `lift` from `MonadTrans` and the free monoid I mention in my answer, in that transformers often are free constructions of some sort. I didn't mention it in my answer because that is a remote connection, and I haven't made it sufficiently clear to myself yet in order to be able to explain it well. – duplode Aug 07 '19 at 23:19