[Haskell-cafe] strange stack overflow with Data.Map

[Christian Maeder]

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