Efficient SelectiveDo and binary search

#1

I’m surprised there is no more talk about a SelectiveDo proposal. It should be possible to use selective to desugar e.g. the following:

main = do
  n <- readLn
  if n > 23
    then putStrLn "Too large"
    else putStrLn "Fine"

The desugared code should be equivalent to main = ifS ((> 23) <$> readLn) (putStrLn "Too large") (putStrLn "Fine"). Crucially, it doesn’t need a Monad instance, only Selective! It would be great to be able to use syntax like that e.g. in parser combinators or libraries with parallelizable effects. Case analysis should work as well.

There was a brief discussion about this on Reddit, and the upshot was:

  • It’s not just a straightforward RebindableSyntax, because Selective doesn’t have a straightforward bind operator. So directly desugaring if and case would bring something novel.
  • There is a very inefficient bindS operator that only works on Bounded types and basically makes a branch for every single value. This is of course horrible for larger types:
> return (10000 :: Int) `bindS` print
*** Exception: stack overflow

To work around this issue, I’m working on a type class Bisect a which has a method bisect :: a -> a -> a to make the branching logarithmic in the size of the type, using binary search. But that type class then has to be derived or written for every single datatype, which is still not as nice as a new desugaring.

So, long story short: Why is there not more buzz around a SelectiveDo proposal?

6 Likes
#2

I’m not aware of a SelectiveDo proposal and I can’t find it in the list of proposals. EDIT: Oh, it does not exist yet, I misread. I guess nobody has put in the work to write up a proposal.

1 Like
#3

Yes, it’s a lot of work to write such a proposal in high quality, and a commitment to an implementation. But I would have expected that at least there would have been a blog post about this.

#4

I have also not used selective personally and it seems that not many other project do either. It is still rather niche. I think now library writers need to start using selective and then when users start using those libraries they start to desire a SelectiveDo extension.

1 Like
#5

See https://github.com/snowleopard/selective/issues/40 for upstream discussion

#6

As suggested by Andrei, a GHC plugin could be the most efficient way forward to test this proposal. I suggest this directory https://mpickering.github.io/plugins.html for inspiration

1 Like
#7

Even simpler: One could write a QuasiQuoter like https://hackage.haskell.org/package/arrowp-qq