[Haskell-cafe] ANNOUNCE: set-monad

David Menendez 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 mailing list