Selective functor paper example - Haskell

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 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?

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 is overly eager in what it reports --- aka the entire call graph possible

there 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, 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

What can you say about Strong Functors relation with Selective functors??

lstr :: Strong f => (b, f a) -> f (b, a)
rstr :: Strong f => (f a, b) -> f (a, b)

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

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

What 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 that

Yes 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

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

are 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:

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)

@Bolt When I try to compile:

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

Interesting, 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:

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

because 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

Maybe not an instance but there's an isomorphism between them

If you mean there's an isomorphism between Applicative and Selective somehow, then no, we're getting confused

Here is the actual MonoidalFunctor class you should be looking at if you want to see the way in which all Applicatives are monoidal functors of one kind and all Selectives are monoidal functors of another kind: https://gist.github.com/masaeedu/9706a06969e5ce127753cb55c622ae77#file-monoidal-hs-L40

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

The 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 it

My Monoidal is actually the MonoidalFunctor you linked :P

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

If 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:

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₁

so then:

type Applicative = MonoidalFunctor (->) (,) () (->) (,) ()
type Decisive = MonoidalFunctor (Op (->)) Either Void (Op (->)) Either Void

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!