Hey all, I was wondering: Has anyone attempted to ...

# arrow

[Nathan Bedell]

Hey all, I was wondering: Has anyone attempted to write a monad "effect" implementation for the Sequence monad (which I think would be similar to the List monad in Haskell), or any other similar non-deterministic monad using Arrow-style comprehension notation using coroutines?

I know there are examples of "result type" comprehensions in arrow core (e.x. Either), and I've been able on my own to figure out how to build a monad comprehension syntax for a ReaderT IO
-like monad (this was actually pretty easy) -- but I can't for the life of me figure out how to encode a non-deterministic monad like Sequence using the methods of Arrow.

Has anyone attempted this, or have any working examples? As I understand, the problem is basically to encode the monad as a sub-monad of the continuation monad (i.e the whole "continuations are the mother of all monads" thing) -- but I'm not experienced enough with continuations be able to grok that yet.

[Jannis]

The problem is that we have only single shot continuations so we cannot encode such monad instances with kotlin suspension. In short the problem is that a continuation in kotlin can only be resumed once whereas a sequence binding would need to call it for each element. We had this previously with HKT encodings but there we used a jvm reflection hack to deep copy the continuation

[Jannis]

There are some hacky ways to emulate multi shot continuations in arrow-continuations but (even though I wrote them) I would not recommend using them

[Jannis]

To make this work (properly without bad hacks) we need either compiler plugins or kotlin language changes

[Nathan Bedell]

Ahh, that makes sense. That's unfortunate.

Although, after looking up "multi-shot continuations", a result came up where Elizarov actually commented with a paper saying that it is in fact possible to implement backtracking with one-shot continuations -- so still not a Sequence monad, but still interesting.

[Jannis]

I'd be very interested in that. All examples I have seen so far either emulate the behavior or copy the continuation using reflection (or similar)

[Nathan Bedell]

On a related note: I know that arrow no longer has Free, but for a concrete instance of a free monad, would it be possible to implement it via coroutines keeping within the one-shot restriction?

If so, it seems to me like that might be another workaround -- encode some "non-deterministic" methods like choose: (List<A>) -> M<A> in your free monad, build up your Free instance with coroutines, and then interpret those methods in terms of the methods of the "actual" non-deterministic monad in question.

[Nathan Bedell]

discuss.kotlinlang.org/t/first-class-continuations is the thread I found by the way.