On Thu, Dec 29, 2005 at 04:24:02PM +0100, Jean-Philippe Bernardy wrote:

On 12/29/05, David Roundy wrote:

...

On Thu, Dec 29, 2005 at 01:42:29PM +0100, Christian Maeder wrote:

...

...

...

stats elems = foldl add_elem Map.empty elems add_elem m x = Map.insertWith (+) x 1 m

...

main = print $ stats $ take 1000000 $ repeat 1

This program has a space leak and runs out of stack space. I'm guessing that I'm being bit here by an unnatural amount of laziness in Map.insertWith, but I can't see how to fix this. :( I'm sure it's something elementary...

David Roundy wrote: try:

stats = foldl' add_elem Map.empty add_elem m x = myinsertWith (+) x 1 m

myinsertWith f k v m = case Map.lookup k m of Nothing -> Map.insert k v m Just w -> let r = f v w in r `seq` Map.insert k r m

Thanks, that does it! I had tried something like that, but without the foldl', and had tried foldl', but without the myinsertWith. The reason I didn't spend much time using this implementation is that for large maps, it will take twice as long as Map.insertWith, so I assumed (incorrectly) that Map.insertWith should be written so that it behaves in a non-leaky manner.

I'm not sure I understand this ... Do you say that the leaky program is faster than the non-leaky one ?

No, what I mean is that Map.insertWith only traverses the Map once, while myinsertWith has to traverse it twice, so for a large map, each call to myinsertWith will take twice as long as Map.insertWith. Or to put it a different way, if myinsertWith were part of the Map module, it could be twice as fast.

...

Should the Map modules have an additional Map.insertWith' that behaves strictly, or might it be the case that you always want strict behavior when using insertWith?

IMO, there is always a possibility for needing the lazy version. I also have to say that making a strict version for each "...With" does not fill my heart with joy. :) Such cases call for cheapness analysis, or optimistic evaluation, or some other kind of solution implemented at the compiler level, IMHO.

I agree, there is a possibility for wanting the lazy version. If you only want to provite one insertWith, I suppose you'd want to figure out whether the lazy or strict version is more commonly needed (or "safer"), and make people wanting the other version implement it themselves. In my opinion, the strict version seems nicer, largely because HNF is cheap for most "large" computations I do, so strictness wouldn't cost much. On the subject of excessive functions, what are the uses of insertWithKey? It seems like anything you do with insertWithKey you could just as efficiently do with insertWith... it seems pretty trivial to write insertWithKey f k x = insertWith (f k) k x There may be a use to all the WithKey variants, but I'd much rather have strict varients... -- David Roundy http://www.darcs.net

Jean-Philippe Bernardy wrote:

...

insertWithKey f k x = insertWith (f k) k x

This is the case if the key type has structural equality. Otherwise, the key passed to the combining function, which comes from the map, can have a different value. Not that I support this style of coding,

I don't think, that we need to consider old and new keys (different but yielding EQ).

It's a change to consider. We might want to deprecate the withKey variants (and implicitly the non-structural-equalilty types for keys).

At least {fold,map,filter,partition}WithKey functions are (I think) more useful than {insert,adjust,update}WithKey, so there will be no general rule for withKey-variants. (I've never used {union,difference,intersection]WithKey, how important are these?) I would not impose an implicit requirement for strong structural equality/order on the keys. But it would suffice to document which of two "equal" keys is dropped or kept. Maybe it is even possible to keep "Set a" somehow in sync with "Map a ()" or an identity "Map a a". (And "Set (MapEntryPair a b)" to "Map a b") On the other hand, if we would forget about biasing also for sets than insertion could be optimized to do nothing with sets that contain already the element. (Maybe that should even be changed so in Data.Set for efficiency reasons. An extra function might do the job of actually replacing an equal element.) Christian P.S. left-biasing for Set.intersection still needs to be checked in (I've sent a patch some time ago)

On 30/12/05, Adrian Hey wrote:

As for the structural equality issue, I have always assumed that if (==) returned True or `compare` returned EQ this implied structural equality. But I'm not sure that's documented anywhere, and as it happens it's not true for the Eq and Ord instances defined AVL trees. This is something that had been worrying me (maybe I should remove these instances).

This isn't even quite true for all the prelude types. In particular -0.0 and 0.0 are distinct Float values structurally, but will compare equal, though one might make exceptions here due to floating point values being thought of as some approximation of real numbers where the laws are satisfied. However, I think it's safe to only require that (==) be a suitable equivalence relation on the values of a type. This is especially true when the representation is hidden, so that no stronger tests for comparison could be constructed by the library user. It seems like it would usually be handy to have instances of Eq not differentiate between values which "represent the same thing" in different ways. Earlyish versions of Miranda had 'laws' which would be applied automatically to normalise values of a particular type, so as to get a type which wasn't freely generated by its constructors. They were quite strong, and one could easily enforce a variety of invariants, like keeping lists sorted and trees balanced. At some point they were removed, but I haven't seen a really good explanation as to why this happened. I suppose that there are other ways to achieve those effects, but it's neat to be able to use pattern matching on what would otherwise have to be an abstract data type. - Cale

Yes, union suffers from the same problem; both in Set and Map as well. The testing code can now detect problems of left-biasing in presence of non-structural equality. (That's what I wanted to implement before applying the fix). On 12/31/05, Adrian Hey wrote:

On Friday 30 Dec 2005 10:33 am, Christian Maeder wrote:

...

P.S. left-biasing for Set.intersection still needs to be checked in (I've sent a patch some time ago)

Perhaps I'm missing something, but union seems to have the same problem. Maybe someone should review all this code to see if implementations are consistent with the Haddock (preferably someone who understands more about how it works than I do :-).

Regards -- Adrian Hey

On Mon, Jan 02, 2006 at 05:28:39PM +0000, Adrian Hey wrote:

BTW, I think I would prefer the default behaviour of insert to be to retain existing elements because this allows the optimisation of not updating the data structure representing the set at all (which should help keep heap burn rate down).

I hope you don't propose this for Map. It would break some nice uses, like representing variable scopes in an interpreter. The "replacing" insert allows you to easily implement hiding variables in outer scopes. Best regards Tomasz -- I am searching for a programmer who is good at least in some of [Haskell, ML, C++, Linux, FreeBSD, math] for work in Warsaw, Poland

Adrian Hey wrote:

On Monday 02 Jan 2006 7:42 pm, Tomasz Zielonka wrote:

...

I hope you don't propose this for Map. It would break some nice uses, like representing variable scopes in an interpreter. The "replacing" insert allows you to easily implement hiding variables in outer scopes.

You mean am I proposing that Maps should retain old association values and discard the new ones? If so the answer is no, of course not.

Actually, for maps it makes (even more) sense to have an additional "insert-only-if-not-member" function, and be it only for (defining) "fromList". Maybe such a function should simply be called "add" to encourage its use. {- | insert pair only if key is not a member yet (left-biased) leave map unchanged otherwise. -} add :: Ord a => Map a b -> a -> b -> Map a b Properties: insert k v m = add (delete k m) k v add m k v = if member k m then m else insert k v m (On sets "add" and "insert" could be used interchangeably) For maps I could also imagine that it is possible to supply a more efficient implementation based on arrays if pairs are inserted at most once (by only "adding" and never deleting). (To really avoid array duplication then, the changing key sets would need to be kept separately apart from further requirements on the keys for array access) Cheers Christian

On Tue, Jan 03, 2006 at 12:03:06AM +0000, Adrian Hey wrote:

On Monday 02 Jan 2006 7:42 pm, Tomasz Zielonka wrote:

...

I hope you don't propose this for Map. It would break some nice uses, like representing variable scopes in an interpreter. The "replacing" insert allows you to easily implement hiding variables in outer scopes.

You mean am I proposing that Maps should retain old association values and discard the new ones? If so the answer is no, of course not.

Good. I was pretty sure that you are not proposing it, but I wanted to be sure.

But I see no reason why they shouldn't do this with keys, which are "equal" according to the instance of Ord. (If this is any way dangerous then the key type should not be an instance of Ord IMO.)

No objections here. Best regards Tomasz -- I am searching for a programmer who is good at least in some of [Haskell, ML, C++, Linux, FreeBSD, math] for work in Warsaw, Poland

Adrian Hey wrote:

On Friday 30 Dec 2005 10:33 am, Christian Maeder wrote:

...

P.S. left-biasing for Set.intersection still needs to be checked in (I've sent a patch some time ago)

Perhaps I'm missing something, but union seems to have the same problem. Maybe someone should review all this code to see if implementations are consistent with the Haddock (preferably someone who understands more about how it works than I do :-).

Yes, you're right! union is not left-biased although that is explicitly documented so in the header. Either we give up the control of biasing or fix union, too. (I've found no other function were biasing would matter, unions will be ok if union is.) I could supply a patch for union if needed. Cheers Christian

On 12/29/05, Udo Stenzel wrote: ***snipped a bunch of use case specific stuff**

and if two versions of every function are deemed too much of a burden, I'd rather get rid of the lazy version.

Huh, then why use haskell, there are strict purely functional languages? /snarky philosophical comment -David Mercer Tucson, AZ