It seems like that would pick only one of the two given f as, and not both (specifically, the first when the f Bool contains a True). Am I just misunderstanding something?

@Sandy Maguire I remember you were explaining something about the paper to me a while back, so I know you've gone through it. Can you maybe what I'm missing?

Yes Over over-approximates the the effects. So you have both effects on the ifS I very much like the applicability on build systems as it helps to build an intuition!

For instance, in this particular example one branch of the if could need one dependency and the other another different dependency. Then over approximating the effects would give info about which dependencies should be needed in total!

Btw @Asad Saeeduddin I read your draft README on the selectivemonoidal repository and caught my attention, is there really the concept of Decisive in CT being the dual of a Monoidal functor?

@Bolt That's very close. Decisive isn't the dual of a monoidal functor, it is a kind of monoidal functor, just as Applicative is a kind of monoidal functor. The concept of a monoidal functor is "parametrized" by a source and a target "monoidal category", which in turn is a concept consisting of a category + a "monoidal structure". You get a Decisive functor by taking an Applicative lax monoidal functor and replacing both the category and the monoidal structure with their duals

Btw, I figured out how to "break" things to get the same results as in the paper: I just have to derive branch from select instead of the other way around. I think having Over "abcdef" and Under "acde" is actually more correct than Over "abdef" and Under "ade", but I've explained more in the comments

i.e. you need no more than fmap and the characteristics of (,) to implement that

And this is interesting right? The fact that you only need this (a Strong Functor) to derive select and the fact that every functor in Set is Strong might be useful

In Set the product is (,) but for example in Mat (the matrix category) the product is the Kronecker product. I do not know if it is trivial to have a strong functor in other categories

It's not super clear to me what Strong has to do with Monoidal in this context (note that I have no idea what Monoidal classes are out there, they may or may not have anything to do with the concept of a lax monoidal functor), but here for example is the lax monoidal functor representation of Applicative:

class Functor f => Applicative' f
where
zip :: (->) (f a, f b) f (a, b)
husk :: (->) () (f ())

Compare and contrast with:

class Functor f => Decisive f
where
decide :: Op (->) (Either (f a) (f b)) (f (Either a b))
guarantee :: Op (->) Void (f Void)

rstr :: Functor f => (f a, b) -> f (a, b)
rstr (fa, b) = fmap (, b) fa
select' :: Functor f => f (a -> b) -> f (Either a b) -> f b
select' = curry (fmap h . rstr)
where h (f,x) = either f id x

I get:

[typecheck] [E] /mnt/data/depot/git/haskell/experiments/selectivemonoidal/src/Main.hs:57:11: error:
• Occurs check: cannot construct the infinite type: b ~ Either a b
Expected type: f (a -> b) -> f (Either a b) -> f b
Actual type: f (a -> b) -> Either a b -> f b
• In the expression: curry (fmap h . rstr)
In an equation for ‘select'’:
select'
= curry (fmap h . rstr)
where
h (f, x) = either f id x
• Relevant bindings include
select' :: f (a -> b) -> f (Either a b) -> f b
(bound at /mnt/data/depot/git/haskell/experiments/selectivemonoidal/src/Main.hs:57:1)

At any rate I've updated the repo, so you can play around with a variant of branch and ifS that exactly replicate the results from the selective functors paper (although I think the results that differ are "more correct"). It all flows down from Decisive regardless of which seems more correct to you

It's interesting to see the difference between the implementations of branch and select! But I think I prefer the semantics where ifS gives every effect. I'm not sure which approach is more flexible since you cannot encode a SelectiveOver instance that gives the more intuitive result with ifS and neither can you encode a DecideOver instance that gives the results seen in the paper. But since the Decide class brings out the different interactions when implementing select as branch and vice-versa I think your approach wins in that respect

@Bolt I'm not sure I fully understand the comment about flexibility, but starting from an instance of Decide we can obtain either implementation of ifS. We can get the one from the paper, or a different one that actually behaves like if _ else _ then _

The flexibility I am talking about is basically the ability of changing the semantics of Over wrt to its instance implementation. If such an instance could exist then we'd have 2 newtype wrappers around Over one for each semantic!

With Decide you can have that but is not very straightforward, is more like exploiting a hidden behaviour. Although it is able to do it is not very elegant, but it still is better than Selective which does not allow that (I think)

In the repo, we have both Over and Under. The select operation on Over unconditionally executes both the f (Either a b) and the f (a -> b) (just as in the paper), and the select operation on Under never executes the f (a -> b) (just as in the paper). Similarly, what the paper calls branch and I call branch' (but probably should call something like fallthrough) will for Over execute all three of the effects given to it, and for Under will only execute the first effect. This also aligns with the paper.

The only new thing is that now there are two extra operations actuallyBranch and actuallyIfS, that actually branch and behave like if else. The actuallyBranch is the primitive "unadulterated" operation from which you can derive select and fallthrough and everything else, and of course you can use it itself as an operation that is not available in the paper.

You can't change the semantics of select for Over or the semantics of select for Under, those are just part of the instance. You can't really change any of their semantics to resemble each other in fact. None of the operations for Over behave like the operations for Under, and vice versa. Over just has a new pair of operations actuallyBranch and actuallyIfS (which always evaluate the first two effects, having no actual boolean to branch on), and so does Under (which instead always chooses the first and third ones).

No, you can only go in the other direction. You can get the select from the paper out of actuallyBranch, but if you start with select you can never get actuallyBranch

F is an applicative functor
F is a decisive functor

From my understanding a Decisive functor is a concrete instance of a Monoidal functor just as Applicative is, shouldn't this hypotheses be something more fundamental? I dont know if what I'm saying makes sense

Here's the formal definition of a lax monoidal functor: https://en.wikipedia.org/wiki/Monoidal_functor, although you should probably first look at the definition of a monoidal category

Applicatives are lax monoidal functors from the monoidal category (->, (,), ()) to itself, and Decisives are lax monoidal functors from (<-, Either, Void) to itself

In that case there is an isomorphism between Applicative and a particular instantiation of MonoidalFunctor. Specifically, its instantiation at → = ->, ⊗ = (,) and I = () for both categories

There's other interesting examples as well, although they're irrelevant to selectives. E.g. if we instead instantiate the first category at → = ->, ⊗ = Either and I = Void and the second at → = ->, ⊗ = (,) and I = (), we end up with Alternative

the most explicit way I can think of to write out the class is:

class
(SemigroupalCategory (→₁) (⊗₁), SemigroupalCategory (→₂) (⊗₂), Functor (→₁) (→₂) f)
=>
SemigroupalFunctor (→₁) (⊗₁) (→₂) (⊗₂) f
where
zip :: f a ⊗₂ f b →₂ f (a ⊗₁ b)
class
(MonoidalCategory (→₁) (⊗₁) (I₁), MonoidalCategory (→₂) (⊗₂) (I₂), SemigroupalFunctor (→₁) (→₂) f)
=>
MonoidalFunctor (→₁) (⊗₁) (I₁) (→₂) (⊗₂) (I₂) f
where
pure :: I₂ →₂ f I₁

Yes. That's the critical idea. The cartesian product and unit are just one special case of the more general concept of a "monoidal structure". There are often lots of different monoidal structures on the same category. To understand what the rules are, look up "monoidal category".

I'm a little bit confused about one of the examples in the selective functors paper:

pasted image

I don't get why the output isn't "abdef", given that

`ifS`

is defined as:pasted image

It seems like that would pick only one of the two given

`f a`

s, and not both (specifically, the first when the`f Bool`

contains a`True`

). Am I just misunderstanding something?@Sandy Maguire I remember you were explaining something about the paper to me a while back, so I know you've gone through it. Can you maybe what I'm missing?

been a while since i read it, but IIRC, selectives are not required to perform the untaken branches, but may if they choose to

the

`Over`

selective isoverly eager in what it reports --- aka the entire call graph possiblethere is also

`Under`

which i think will give you`Under "abdef"`

(or maybe even less!)

actually i think it will give you

`Under "ade"`

Yes

`Over`

over-approximates the the effects. So you have both effects on the`ifS`

I very much like the applicability on build systems as it helps to build an intuition!For instance, in this particular example one branch of the if could need one dependency and the other another different dependency. Then over approximating the effects would give info about which dependencies should be needed in total!

Btw @Asad Saeeduddin I read your draft README on the selectivemonoidal repository and caught my attention, is there really the concept of

`Decisive`

in CT being the dual of a`Monoidal`

functor?@Bolt That's very close.

`Decisive`

isn't the dual of a monoidal functor, itisa kind of monoidal functor, just as`Applicative`

is a kind of monoidal functor. The concept of a monoidal functor is "parametrized" by a source and a target "monoidal category", which in turn is a concept consisting of a category + a "monoidal structure". You get a`Decisive`

functor by taking an`Applicative`

lax monoidal functor and replacing both the category and the monoidal structure with their dualsWhat can you say about Strong Functors relation with Selective functors??

Btw, I figured out how to "break" things to get the same results as in the paper: I just have to derive

`branch`

from`select`

instead of the other way around. I think having`Over "abcdef"`

and`Under "acde"`

is actually more correct than`Over "abdef"`

and`Under "ade"`

, but I've explained more in the commentsWhat exactly is

`Strong`

? Strength is with respect to a particular tensor, and every endofunctor on Hask is strong with respect to`(,)`

Strong is a typeclass with

`lstr`

and`rstr`

That typeclass can be instantiated for every functor

i.e. you need no more than

`fmap`

and the characteristics of`(,)`

to implement thatYes I think that is because every functor in Set is strong, I know very little about it

But I asked this because they also fit in the whole Monoidal functor thing you have going

And this is interesting right? The fact that you only need this (a Strong Functor) to derive

`select`

and the fact that every functor in Set is Strong might be usefulIn Set the product is

`(,)`

but for example in Mat (the matrix category) the product is the Kronecker product. I do not know if it is trivial to have a strong functor in other categoriesare you sure that the

`select`

derived from`Strong`

typechecks? I'm not sure how that's working without relying on`Applicative`

all

`lstr`

and`rstr`

are is`lstr (b, fa) = fmap (b, ) fa`

and`rstr (fa, b) = fmap (, b) fa`

It's not super clear to me what

`Strong`

has to do with`Monoidal`

in this context (note that I have no idea what`Monoidal`

classes are out there, they may or may not have anything to do with the concept of a lax monoidal functor), but here for example is the lax monoidal functor representation of`Applicative`

:Compare and contrast with:

@Bolt When I try to compile:

I get:

At any rate I've updated the repo, so you can play around with a variant of

`branch`

and`ifS`

that exactly replicate the results from the selective functors paper (although I think the results that differ are "more correct"). It all flows down from`Decisive`

regardless of which seems more correct to youInteresting, I'll read it!

I probably misspelled something because I'm on my phone, let me try again :slight_smile:

@Asad Saeeduddin No, you are right it is needed the Applicative instance, that's unfortunate :P But was a nice exercise!

It's interesting to see the difference between the implementations of branch and select! But I think I prefer the semantics where

`ifS`

gives every effect. I'm not sure which approach is more flexible since you cannot encode a`Selective`

`Over`

instance that gives the more intuitive result with`ifS`

and neither can you encode a`Decide`

`Over`

instance that gives the results seen in the paper. But since the`Decide`

class brings out the different interactions when implementing`select`

as`branch`

and vice-versa I think your approach wins in that respect@Bolt I'm not sure I fully understand the comment about flexibility, but starting from an instance of

`Decide`

we can obtain either implementation of`ifS`

. We can get the one from the paper, or a different one that actually behaves like if _ else _ then _The flexibility I am talking about is basically the ability of changing the semantics of

`Over`

wrt to its instance implementation. If such an instance could exist then we'd have 2 newtype wrappers around`Over`

one for each semantic!With

`Decide`

you can have that but is not very straightforward, is more like exploiting a hidden behaviour. Although it is able to do it is not very elegant, but it still is better than`Selective`

which does not allow that (I think)In the repo, we have both

`Over`

and`Under`

. The`select`

operation on`Over`

unconditionally executes both the`f (Either a b)`

and the`f (a -> b)`

(just as in the paper), and the`select`

operation on`Under`

never executes the`f (a -> b)`

(just as in the paper). Similarly, what the paper calls`branch`

and I call`branch'`

(but probably should call something like`fallthrough`

) will for`Over`

execute all three of the effects given to it, and for`Under`

will only execute the first effect. This also aligns with the paper.The only new thing is that now there are two extra operations

`actuallyBranch`

and`actuallyIfS`

, that actually branch and behave like if else. The`actuallyBranch`

is the primitive "unadulterated" operation from which you can derive`select`

and`fallthrough`

and everything else, and of course you can use it itself as an operation that is not available in the paper.Right! But can you have

`actuallyBranch`

and`actuallyIfS`

by using only the`select`

from the paper?You can't change the semantics of

`select`

for`Over`

or the semantics of`select`

for`Under`

, those are just part of the instance. You can't really change any of their semantics to resemble each other in fact. None of the operations for`Over`

behave like the operations for`Under`

, and vice versa.`Over`

just has a new pair of operations`actuallyBranch`

and`actuallyIfS`

(which always evaluate the first two effects, having no actual boolean to branch on), and so does`Under`

(which instead always chooses the first and third ones).No, you can only go in the other direction. You can get the

`select`

from the paper out of`actuallyBranch`

, but if you start with`select`

you can never get`actuallyBranch`

Also:

From my understanding a

`Decisive`

functor is a concrete instance of a`Monoidal`

functor just as`Applicative`

is, shouldn't this hypotheses be something more fundamental? I dont know if what I'm saying makes sensebecause it muddles up different operations so that you can't separate them again

I would stop capitalizing

`Monoidal`

here (unless`Monoidal`

is an extremely general typeclass that I doubt it is)Maybe not an instance but there's an isomorphism between them

Also this does suggest the claim that a Selective functor can be seen as the composition of an applicative functor with the

`Either`

monad, right?I guess where I'm trying to get at is some kind of formal ground where this can all be eventually proved

If you mean there's an isomorphism between

`Applicative`

and`Selective`

somehow, then no, we're getting confusedHere is the actual

`MonoidalFunctor`

class you should be looking at if you want to see the way in which all`Applicative`

s are monoidal functors of one kind and all`Selective`

s are monoidal functors of another kind: https://gist.github.com/masaeedu/9706a06969e5ce127753cb55c622ae77#file-monoidal-hs-L40Here's the formal definition of a lax monoidal functor: https://en.wikipedia.org/wiki/Monoidal_functor, although you should probably first look at the definition of a monoidal category

`Applicative`

s are lax monoidal functors from the monoidal category`(->, (,), ())`

to itself, and`Decisive`

s are lax monoidal functors from`(<-, Either, Void)`

to itselfThe isomorphism I was talking about was between

`Applicative`

and`Monoidal`

!But that's some nice info about the subject, I sometimes get confused! Thanks

Ah. Well what is

`Monoidal`

? I forget if you already linked itMy

`Monoidal`

is actually the`MonoidalFunctor`

you linked :PIn that case there is an isomorphism between

`Applicative`

and a particularinstantiationof`MonoidalFunctor`

. Specifically, its instantiation at`→ = ->`

,`⊗ = (,)`

and`I = ()`

for both categoriesIf we instead instantiate it at

`→ = <-`

,`⊗ = Either`

and`I = Void`

for both categories instead, we end up with`Decisive`

There's other interesting examples as well, although they're irrelevant to selectives. E.g. if we instead instantiate the first category at

`→ = ->`

,`⊗ = Either`

and`I = Void`

and the second at`→ = ->`

,`⊗ = (,)`

and`I = ()`

, we end up with`Alternative`

the most explicit way I can think of to write out the class is:

so then:

Both of kind

`(* -> *) -> Constraint`

The laws you can read off the three diagrams on the Wikipedia page: https://en.wikipedia.org/wiki/Monoidal_functor

Awesome! Thank you for this!

no worries

I have one question tho, is it correct to instantiate the product as

`Either`

?Yes. That's the critical idea. The cartesian product and unit are just one special case of the more general concept of a "monoidal structure". There are often lots of different monoidal structures on the same category. To understand what the rules are, look up "monoidal category".

Super interesting!