[Haskell-cafe] ANNOUNCE: set-monad

[David Menendez]

On Sun, Jun 17, 2012 at 2:26 AM, Tillmann Rendel
<rendel at informatik.uni-marburg.de> wrote:
> Hi,
>
>
> David Menendez wrote:
>>
>> 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.
>
> "Somewhat better"? My example was three times faster, and I guess that the
> fast variant is O(n) and the slow variant is O(n²). So I expect that for
> some applications, the Set interface is more than fast enough and the
> MonadPlus-interface is much too slow.

Yes, that should have been "significantly better".

>>> (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.
>
> Here, you compare mplused to unioned, but in the parentheses, I asked about
> numbers and unioned (from my last email).

You're right. That may have been caused by the time to compute numbers
itself; I saw that numbers `times` numbers was faster than unioned
`times` unioned the second time I ran it.



Additionally, I haven't done any serious performance testing, but
there also seems to be a speedup when the following lines are added to
run:

run (Bind (Plus (Prim sa) mb) f) = run (Bind (S.union sa (run mb)) f)
run (Bind (Plus ma (Prim sb)) f) = run (Bind (S.union (run ma) sb) f)



-- 
Dave Menendez <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>