Re: from array update algorithm to nice Haskell code

Hi Wolfgang, I think that you are mixing up worst case bounds O(..) with some specific case. I guess that you mean by "O(1) elements" a known and constant number of elements. I mean a constant maximum number of elements. An example would be that the set b is guaranteed to have not more than one e

Re: from array update algorithm to nice Haskell code

Am Freitag, 9. Januar 2004 23:45 schrieb Daan Leijen: > > Now assume that I have a set a with O(n) elements and a set b with O(1) > > elements. > > You can't have "O(1) elements" ... (A bound like O(..) talks about the worst > case time/space of an operation.) Well, the O calculus isn't bound to r

Re: from array update algorithm to nice Haskell code

Now assume that I have a set a with O(n) elements and a set b with O(1) elements. You can't have "O(1) elements" ... (A bound like O(..) talks about the worst case time/space of an operation.) a `minusSet` b would take O(n) time and so would a `intersect` b. If I'd use foldr (flip delFromSet) a

Re: from array update algorithm to nice Haskell code

Am Mittwoch, 31. Dezember 2003 00:06 schrieb Daan Leijen: > Hi Wolfgang, > > > is there some documentation about the complexity of the FiniteMap and Set > > operations? > [...] > Also, all DData functions have their complexity listed in the documentation. > > See:

Re: from array update algorithm to nice Haskell code

On Wed, 31 Dec 2003 12:35:23 +0100, Wolfgang Jeltsch <[EMAIL PROTECTED]> wrote: The documentation of DData.Map states the following as an advantage of DData.Map over Data.FiniteMap: It uses the efficient hedge algorithm for both union and difference [...]. Does this mean that the Data.FiniteMa

Re: from array update algorithm to nice Haskell code

Am Mittwoch, 31. Dezember 2003 00:06 schrieb Daan Leijen: > Hi Wolfgang, > > > is there some documentation about the complexity of the FiniteMap and Set > > operations? > [...] > The operations in the "Data.FiniteMap" library in Ghc have the same > complexity of the operations in the "DData.Map"

Re: from array update algorithm to nice Haskell code

> On Tue, 30 Dec 2003 23:14:05 +0100, Wolfgang Jeltsch > <[EMAIL PROTECTED]> wrote: [replying indirectly because the original email doesn't seem to have gotten here yet] > > I have an algorithm which updates one or more arrays in a loop. The > > update operations depend on the (old) contents of

Re: from array update algorithm to nice Haskell code

Hi Wolfgang, is there some documentation about the complexity of the FiniteMap and Set operations? My DData library gives some useful links to papers about this subject, also take a look at the "IntSet" and "IntMap" libraries as they have an interesting complexity class. Also, all DData functions