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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
