[Haskell-cafe] ANNOUNCE: set-monad

[David Menendez]

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>
<http://www.eyrie.org/~zednenem/>