sequenceA without Traversable - Haskell

is there a typeclass with the operation almostLikeSequenceA :: Alternative f => t (f a) -> f (t a)?

or the opposite: f (t a) -> t (f a)

All Alternatives are Applicative, so I don't understand why you need a separate typeclass for this.

Are you looking for a typeclass on t?

what's wrong with traversable?

@Sandy Maguire Yes, I'm looking for a typeclass on t

@Vaibhav Sagar I think it's an accident that Applicative occurs anywhere in the superclass hierarchy of Alternative. If you restrict the interface of Alternative to empty and <|> (or talk about some other typeclass Alternative' that only consists of those operations), neither the laws nor the operations have anything to do with any applicative instance(s) the type may have

to put this another way, a more appropriate relationship between Applicative and Alternative is that of siblings; they both model monoidal functors between different pairs of tensors

at any rate, suppose I was talking about the class:

class Functor f => Alternative' f
  where
  empty :: f a
  (<|>) :: f a -> f a -> f a

I'm looking for a class Wat such that Wat is to Alternative' what Traversable is to Applicative

Here's a way to make more obvious the analogy between Applicative and Alternative' on which we need to pattern the analogy between Traversable and Wat. Applicative and Alternative' are equivalent to the following classes, respectively:

class Functor f => Applicative f
  where
  pure :: () -> f ()
  zip :: (f a, f b) -> f (a, b)
-- + some laws amounting to demanding this really is a monoidal functor

class Functor f => Alternative' f
  where
  empty :: () -> f Void
  union :: (f a, f b) -> f (Either a b)
-- + some laws amounting to demanding this really is a monoidal functor

a particular type f could have any number of lawful implementations of Applicative, and any number of lawful implementations of Alternative', and none of them would necessarily have anything to do with each other

A good example is Map from Data.Map. I believe it's Alternative', because union :: Ord k => Map k a -> Map k a -> Map k a is associative (I think that follows from the associativity of set union, correct me if wrong), and unital wrt empty :: Map k a from the left and right.

(despite not being Applicative)

it is at least Apply via intersection I believe, but that's neither here nor there: the point is having Applicative f as a superclass of Alternative f is a mistake; it's just preventing useful instances for no reason other than to have some and many baked into the class.

What's an example of an Alternative' that isn't Applicative?

Otherwise it seems like you're looking for Alt

Yup, looks like Alt is one half of Alternative'. So what's the analog of Traversable for that plus empty :: f a?

Regarding an example of Alternative' that isn't Applicative, I just gave you one: Map.

Set is another example, for a similar reason. You need infinite Maps and Sets to be able to give a lawful pure for intersection, which isn't possible (at least for the strict variants)

I don't think that's right, because of the Ord constraint

@Vaibhav Sagar You mean for Set?

and also Map

IOW having the Ord constraint on union means it doesn't work as a valid (<|>)

I guess i need to try to compile it, but I don't see the problem:

class Functor f => Alt f
  where
  (<|>) :: f a -> f a -> f a

instance Ord k => Alt (Map k)
  (<|>) = union

it's not that it doesn't compile, it's that it's not valid

what makes it invalid?

it's the same reason Set doesn't have a functor instance

The reason Set doesn't have a functor instance is because you need to demand an Ord constraint on something the functor instance needs to be parametric with respect to

that isn't really an issue conceptually, it's just Haskell is hamstrung when it comes to talking about subcategories. but leaving that aside, I don't get how that objection applies to Map

yeah, that's true, I'll need to think about this some more

to put this another way, you need the Ord on a in Set a, but in Map k a you need it on k. Even with the limited facilities of Functor there's no problem when it comes to Map k, and with a little more finagling there's no problem for Set either

see: https://dorchard.blog/2011/10/18/subcategories-in-haskell-exofunctors/ for a nice discussion of the "Set is not a Functor" problem

silly question: how is what you are asking for different from a regular monoid?

you mean a monoid like forall a. Monoid (f a)?

I mean instance Monoid (Map k a)

right, which would discharge a constraint type IsThisAlternative f = forall a. Monoid (f a)

IOW why is it important that the type is a Functor

i think another way to state the question is: "is the Alternative' typeclass just type Alternative' f = forall a. Monoid (f a)"

And I think the answer is no, although having a lawful instance of Alternative' f gives you automatically a canonical forall a. Monoid (f a)

There are laws associated with Alternative, although they are somewhat controversial: https://wiki.haskell.org/Typeclassopedia#Laws_6

It's not obvious to me what the laws for Alternative' are, e.g. how do empty and (<|>) interact with fmap

the laws for Alternative' are given by the statement "an Alternative' f witnesses that f is a monoidal functor from Either to (,)"

i'll write out the three laws for a monoidal functor in a sec, but a more familiar class modeling monoidal functors is Applicative

for which the laws come from the statement that "an Applicative f witnesses that f is a monoidal functor from (,) to (,)"

I'm especially confused by f Void

the reason we're trying to recognize the analogy between Applicative and Alternative' is so that we can find the analog of Traversable (which is defined in terms of Applicative)

well, think about some Alternative

let's say lists

what terms inhabit [Void]?

[]?

similarly, what terms inhabit Map k Void

fromList []?

yup, right again. there's some kind of pattern here

Set Void, Maybe Void, etc.

it's all the "empty" terms, the ones that don't contain or vary with respect to the functor's argument type

if you think about the zip :: (f a, f b) -> f (a, b) from Applicative as representing a way to stitch together the "intersection" of the structures, then the union :: (f a, f b) -> f (Either a b) represents a way to stitch together the "superposition" of the structures

I don't follow, isn't the first operation more like a union?

well if you have parts that are missing in the first f a or the second f b, how can we expect to produce an (a, b) in the final f (a, b)?

the f (a, b) that we get can only contain things arising from shared parts of the structure of the original f a and f b

oh, here we go: MonoidalAlt seems like what your are looking for

yeah, that's pretty close. unfortunately that again has Applicative as a superclass of Alternative

if you reduce the class constraint to just Functor that's it though

where are you seeing that?

it has a Monoidal constraint but I don't see any Applicative constraint

Monoidal is equivalent to Applicative

ah, I see

Although to be clear, what I'm actually looking for is a Traversable analog for that class, not the class itself

you don't think it's weird that the exact typeclass you're looking for, with the same type signatures you specified, requires an Applicative constraint?

I'm not saying that something's definitely off, but it smells funny

It is weird, but it's not surprising to me given that the Alternative typeclass also demands Applicative as a constraint. I still think it's a mistake

it's just a consistent mistake

also I'm not seeing the connection between Traversable and Alternative

Traversable and Applicative, sure, but not Alternative

The connection is between Traversable and Applicative, but I'm trying to find (if it exists) some mystery class ? that is to Alternative what Traversable is to Applicative

the shape of it is fairly straightforward at least

the laws not so much

have you read https://people.cs.kuleuven.be/~tom.schrijvers/Research/papers/ppdp2015.pdf?

I think part of the issue is that the behaviour of Alternative isn't well specified

e.g. for lists it accumulates but for Maybe it returns the first Just value it finds

I haven't finished reading it but I've got some of the way through it

the problem i think is people use Alternative to mean way more than a basic useful definition would supply

some things are just lax monoidal functors. other things are strong monoidal functors. yet other things are monoidal functors that interact in a "distributive" way with other monoidal functors

mashing it all together in a class makes it a little confusing to reason about it without appealing to concrete use cases

just having empty and union gives you a pretty simple (non trivial) set of laws, if you interpret the class as representing monoidal functors

You can have laws-only subclasses to describe the interaction between Alternative and Applicative if something is both

btw, if "well-specified" here means "uniquely specified", Monoid isn't well specified either, and neither is Applicative

nor is Monad, etc. etc.

the requirement that a type be associated with precisely one instance of a class is a Haskell-ism, the concepts the classes are modeling themselves have no qualms about admitting multiple instances for a given type constructor

I'm aware of that, but it does complicate things when talking about what laws your hypothetical class is supposed to obey, especially when it is based on yet another hypothetical class

I would have thought it simplifies things. The hypothetical class Alternative' corresponds more directly to Applicative than Alternative

the Monoidal -> MonoidalAlt hierarchy you linked to doesn't actually have any basis in the definition of monoidal functors btw

there's just lax monoidal functors, and the laws for them. Traversable is defined with respect to a particular instantiation of this concept (Applicative), so it would make sense that there's a similar concept for other instantiations of monoidal functors (e.g. Alternative)