Selective Functors

From Andrey Mokhov's twitter feed:

Is there any intermediate abstraction between applicative functors and monads? And if yes, what is it? In a new paper with @geo2A, @simonmar and @dimenix we explore "selective functors", which are essentially applicative functors with branching: https://www.staff.ncl.ac.uk/andrey.mokhov/selective-functors.pdf

We've implemented selective functors in Haskell: https://github.com/snowleopard/selective, OCaml: https://github.com/snowleopard/selective-ocaml, and even Coq: https://github.com/tuura/selective-theory-coq (the Coq repository contains some proofs of correctness that our selective instances are lawful). And there is also a PureScript fork!

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

better bases for Selective

I feel that the abstraction for `branch` is a better basis for selective functions than `select`.

select : f (a + b) → f (a → b) → f b
branch : f (a + b) → f (a → c) → f (b → c) → f c

In the Selective laws, the option to perform effects of `f (a → b)` independent of the selector seems awkward to me. And the lack of symmetric handling for the left-right cases seems equally awkward.

Of course, there are merits to favoring binary operators. A useful variation to explore would borrow inspiration from the `left` operator of ArrowChoice:

class (Applicative f) ⇒ Selective f with
    fmapl : f (a + b) → f (a → a') → f (a' + b)
    fmapr : f (a + b) → f (b → b') → f (a + b')
    fmapr src onr = mirror <$> fmapl (mirror <$> src) onr
mirror : (a + b) → (b + a)

We can use `fmap` and `fmapl` to cover branching. We can specialize `fmapr` to avoid intermediate allocations, if our optimizer isn't good enough.

Also, I feel the `<*?` notation is awkward when we consider the symmetric `?*>`, which gives the impression that evaluation of the left operand should be optional. Whatever notation we use should provide a visual hint about whether we're selecting on the left or right 'branch' of a provided input:

(<+?>) = fmapr
(<?+>) = fmapl

Well, that's my 2 cents.