On Sat, Jun 16, 2012 at 3:57 AM, Tillmann Rendel
George Giorgidze wrote:
I would like to announce the first release of the set-monad library.
On Hackage: http://hackage.haskell.org/package/set-monad
Very cool. Seems to work fine. But I am wondering about the impact of using your package on asymptotic complexity (and thereby, on performance).
For programs using only the Monad/MonadPlus interface, I would expect it to have the same asymptotic complexity as [] or Cont (S.Set a). As you noticed, you can get somewhat better performance by using the combinators that convert to S.Set internally, because they eliminate redundant computations later on.
(Why is unioned faster then numbers? Is union doing some rebalancing? Can I trigger that effect directly?)
It's because mplus a b >>= f turns into mplus (a >>= f) (b >>= f),
whereas unioned takes the union before calling f.
You can force this by defining:
simplify :: (Ord a) => Set a -> Set a
simplify = Prim . run
Unfortunately, there doesn't seem to be any equivalent of Prim in the
exported interface. I guess doing simplify = union empty would work.
--
Dave Menendez