# Efficient SelectiveDo and binary search

**URL:** <https://discourse.haskell.org/t/efficient-selectivedo-and-binary-search/1657>\
**Category:** Uncategorized\
**Created:** [December 14, 2020, 11:03am UTC](https://discourse.haskell.org/t/efficient-selectivedo-and-binary-search/1657 "2020-12-14T11:03:21Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![turion](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/turion/32/989_2.png) [@turion](https://discourse.haskell.org/u/turion)\
**Post date:** [December 14, 2020, 11:03am UTC](https://discourse.haskell.org/t/efficient-selectivedo-and-binary-search/1657/1 "2020-12-14T11:03:21Z")

</div>

I’m surprised there is no more talk about a `SelectiveDo` proposal. It should be possible to use [`selective`](https://hackage.haskell.org/package/selective) to desugar e.g. the following:

```haskell
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:

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

---

<div class="post-metadata">

**Author:** ![jaror](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/jaror/32/3271_2.png) [@jaror](https://discourse.haskell.org/u/jaror)\
**Post date:** [December 14, 2020, 4:06pm UTC](https://discourse.haskell.org/t/efficient-selectivedo-and-binary-search/1657/2 "2020-12-14T16:06:45Z")

</div>

I’m not aware of a `SelectiveDo` proposal and I can’t find it in [the list of proposals](https://github.com/ghc-proposals/ghc-proposals/pulls?q=is%3Apr+is%3Aopen). EDIT: Oh, it does not exist yet, I misread. I guess nobody has put in the work to write up a proposal.

---

<div class="post-metadata">

**Author:** ![turion](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/turion/32/989_2.png) [@turion](https://discourse.haskell.org/u/turion)\
**Post date:** [December 14, 2020, 4:18pm UTC](https://discourse.haskell.org/t/efficient-selectivedo-and-binary-search/1657/3 "2020-12-14T16:18:35Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![jaror](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/jaror/32/3271_2.png) [@jaror](https://discourse.haskell.org/u/jaror)\
**Post date:** [December 14, 2020, 4:22pm UTC](https://discourse.haskell.org/t/efficient-selectivedo-and-binary-search/1657/4 "2020-12-14T16:22:51Z")

</div>

I have also not used selective personally and it seems that [not many other project do either](https://packdeps.haskellers.com/reverse/selective). 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.

---

<div class="post-metadata">

**Author:** ![turion](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/turion/32/989_2.png) [@turion](https://discourse.haskell.org/u/turion)\
**Post date:** [July 5, 2021, 11:30am UTC](https://discourse.haskell.org/t/efficient-selectivedo-and-binary-search/1657/5 "2021-07-05T11:30:46Z")

</div>

See [https://github.com/snowleopard/selective/issues/40](https://github.com/snowleopard/selective/issues/40) for upstream discussion

---

<div class="post-metadata">

**Author:** ![ocramz](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/ocramz/32/3713_2.png) [@ocramz](https://discourse.haskell.org/u/ocramz)\
**Post date:** [July 8, 2021, 8:20am UTC](https://discourse.haskell.org/t/efficient-selectivedo-and-binary-search/1657/6 "2021-07-08T08:20:00Z")

</div>

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](https://mpickering.github.io/plugins.html) for inspiration

---

<div class="post-metadata">

**Author:** ![turion](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.haskell.org/turion/32/989_2.png) [@turion](https://discourse.haskell.org/u/turion)\
**Post date:** [July 8, 2021, 8:56am UTC](https://discourse.haskell.org/t/efficient-selectivedo-and-binary-search/1657/7 "2021-07-08T08:56:01Z")

</div>

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