Implementing a custom Alt instance for a datatype to be used with Run

My effect algebra for a Run datatype looks something like this:

data Thing a
  = Async (Array Int) (Aff (...) a)
  | Alt a a

I want to implement non-deterministic choice for this but I’m stuck. The implementation for Alt should race the two Affs but also concat the arrays (could probably have ParAff there directly instead of Aff). I looked at the Choose effect type but it seems it doesn’t allow me to peel off the layers and have access to all the data in the algebra. That is I don’t have direct access to the array and Aff – it only allows me to interpret the data into some other datatype with an Alt instance.

I thought that by adding the Alt case into my own algebra (instead of using the Choose algebra) would allow me to accomplish what I’m doing, and maybe it does – but I would need to peel off both of the sides at the same time when interpreting and I’m not sure how to do that.

The benefit of using the built-in Choose would be that I could use the Alt instance.

1 Like

It’s hard to say specifically without seeing how your interpreter works. The Choose effect though is “just” a continuation where you give it true to get the lhs and false to get the rhs. You probably just don’t want to use runChoose. For example, at work we use Choose effect to run the two execution paths in “parallel”, and when combined with runCont it’s as simple as:

runContChoose :: forall eff. Choose (Eff eff Unit) -> Eff eff Unit
runContChoose = case _ of
  Choose k -> do
    k true
    k false
  Empty -> pure unit

I still didn’t figure out how to do this because writing the interpreters is not trivial here, but that type signature you showed gave me some ideas on how to do this. In particular, I think this can be done with Choose, I just need to unpack my own algebra so that it can be consumed by the interpreter I write for Choose. So maybe the signature for the custom Choose interpreter should look something like

runChoose' :: forall eff r. Run (choose :: CHOOSE | r) (Tuple (Array Int) (Aff eff a)) -> Eff eff Unit

The Tuple corresponding to the Async data constructor. As a note to myself: it helps if you try to think how the data should flow through the interpreter stack. In this case: what should the input be for the Choose interpreter.