[Haskell-cafe] ANNOUNCE: set-monad
dave at zednenem.com
Sat Jun 16 19:03:20 CEST 2012
On Sat, Jun 16, 2012 at 3:57 AM, Tillmann Rendel
<rendel at informatik.uni-marburg.de> wrote:
> 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 <dave at zednenem.com>
More information about the Haskell-Cafe