# Selective functor paper example - Haskell

Welcome to the Functional Programming Zulip Chat Archive. You can join the chat here. 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:

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 is overly eager in what it reports --- aka the entire call graph possible 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 `(,)` i.e. you need no more than `fmap` and the characteristics of `(,)` to implement that 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
``` 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 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 I would stop capitalizing `Monoidal` here (unless `Monoidal` is an extremely general typeclass that I doubt it is) 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? 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 `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-L40

Various monoidal categories, monoidal functors, and monoid objects - monoidal.hs 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 `Applicative`s are lax monoidal functors from the monoidal category `(->, (,), ())` to itself, and `Decisive`s 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 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
``` 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".