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