[Haskell-cafe] ANNOUNCE: set-monad

[Tillmann Rendel]

Hi George,

thanks for your detailed reply.

George Giorgidze wrote:
> The key to the approach used in set-monad is to make progress with the
> evaluation of the unconstrained constructors (i.e., Return, Bind, Zero
> and Plus) without using constrained set-specific operations. It turns
> out that for several cases one can progress with the evaluation
> without duplicating f (evaluation relies on monoid laws, Plus is
> associative and Zero is left and right identity of Plus). I have
> pushed those optimisations to the repo. These optimisations also cover
> your example.

Cool.

> In your email, you have also asked:
>
>> I suspect that I can achieve similar results by using the list monad and
>> converting to a set in the very end. In what situations can I benefit from
>> set-monad?
>
> Sometimes set is a more appropriate data structure than list. [...]

Of course. But I was wondering whether something like set-monad could be 
implemented with

   newtype Set a = Set [a]

instead of

   data Set a = Prim ... | Return ... | Bind ... | ...


Both approaches can offer the same interface, but now I think I see two 
reasons why the latter is more efficient than the former: (1) It allows 
to use set-operations when an Ord is known, for example, when the user 
calls union, and (2) It allows optimizations like you describe above.

   Tillmann