@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
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.
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.
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)
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
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
In my previous post I discussed the new constraint kinds extension to GHC, which provides a way to get type-indexed constraint families in GHC/Haskell. The extension provides some very useful expre…
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)
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
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?
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
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
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
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)
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
Alternative
s areApplicative
, 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 ofAlternative
. If you restrict the interface ofAlternative
toempty
and<|>
(or talk about some other typeclassAlternative'
that only consists of those operations), neither the laws nor the operations have anything to do with any applicative instance(s) the type may haveto put this another way, a more appropriate relationship between
Applicative
andAlternative
is that of siblings; they both model monoidal functors between different pairs of tensorsat any rate, suppose I was talking about the class:
I'm looking for a class
Wat
such thatWat
is toAlternative'
whatTraversable
is toApplicative
Here's a way to make more obvious the analogy between
Applicative
andAlternative'
on which we need to pattern the analogy betweenTraversable
andWat
.Applicative
andAlternative'
are equivalent to the following classes, respectively:a particular type
f
could have any number of lawful implementations ofApplicative
, and any number of lawful implementations ofAlternative'
, and none of them would necessarily have anything to do with each otherA good example is
Map
fromData.Map
. I believe it'sAlternative'
, becauseunion :: 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 wrtempty :: Map k a
from the left and right.(despite not being
Applicative
)it is at least
Apply
viaintersection
I believe, but that's neither here nor there: the point is havingApplicative f
as a superclass ofAlternative f
is a mistake; it's just preventing useful instances for no reason other than to havesome
andmany
baked into the class.What's an example of an
Alternative'
that isn'tApplicative
?Otherwise it seems like you're looking for
Alt
Yup, looks like
Alt
is one half ofAlternative'
. So what's the analog ofTraversable
for that plusempty :: f a
?Regarding an example of
Alternative'
that isn'tApplicative
, I just gave you one:Map
.Set
is another example, for a similar reason. You need infiniteMap
s andSet
s to be able to give a lawfulpure
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 onunion
means it doesn't work as a valid(<|>)
I guess i need to try to compile it, but I don't see the problem:
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 instanceThe reason
Set
doesn't have a functor instance is because you need to demand anOrd
constraint on something the functor instance needs to be parametric with respect tothat 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
ona
inSet a
, but inMap k a
you need it onk
. Even with the limited facilities ofFunctor
there's no problem when it comes toMap k
, and with a little more finagling there's no problem forSet
eithersee: https://dorchard.blog/2011/10/18/subcategories-in-haskell-exofunctors/ for a nice discussion of the "
Set
is not aFunctor
" problemsilly 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 justtype 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 canonicalforall a. Monoid (f a)
There are laws associated with
Alternative
, although they are somewhat controversial: https://wiki.haskell.org/Typeclassopedia#Laws_6It's not obvious to me what the laws for
Alternative'
are, e.g. how doempty
and(<|>)
interact withfmap
the laws for
Alternative'
are given by the statement "anAlternative' f
witnesses thatf
is a monoidal functor fromEither
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 thatf
is a monoidal functor from(,)
to(,)
"I'm especially confused by
f Void
the reason we're trying to recognize the analogy between
Applicative
andAlternative'
is so that we can find the analog ofTraversable
(which is defined in terms ofApplicative
)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)
fromApplicative
as representing a way to stitch together the "intersection" of the structures, then theunion :: (f a, f b) -> f (Either a b)
represents a way to stitch together the "superposition" of the structuresI 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 secondf b
, how can we expect to produce an(a, b)
in the finalf (a, b)
?the
f (a, b)
that we get can only contain things arising from shared parts of the structure of the originalf a
andf b
oh, here we go:
MonoidalAlt
seems like what your are looking foryeah, that's pretty close. unfortunately that again has
Applicative
as a superclass ofAlternative
if you reduce the class constraint to just
Functor
that's it thoughwhere are you seeing that?
it has a
Monoidal
constraint but I don't see anyApplicative
constraintMonoidal
is equivalent toApplicative
ah, I see
Although to be clear, what I'm actually looking for is a
Traversable
analog for that class, not the class itselfyou 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 demandsApplicative
as a constraint. I still think it's a mistakeit's just a consistent mistake
also I'm not seeing the connection between
Traversable
andAlternative
Traversable
andApplicative
, sure, but notAlternative
The connection is between
Traversable
andApplicative
, but I'm trying to find (if it exists) some mystery class?
that is toAlternative
whatTraversable
is toApplicative
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 specifiede.g. for lists it accumulates but for
Maybe
it returns the firstJust
value it findsI 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 supplysome 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
andunion
gives you a pretty simple (non trivial) set of laws, if you interpret the class as representing monoidal functorsYou can have laws-only subclasses to describe the interaction between
Alternative
andApplicative
if something is bothbtw, if "well-specified" here means "uniquely specified",
Monoid
isn't well specified either, and neither isApplicative
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 toApplicative
thanAlternative
the
Monoidal
->MonoidalAlt
hierarchy you linked to doesn't actually have any basis in the definition of monoidal functors btwthere'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
)