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

[Adrian Hey]

On Sunday 01 Jan 2006 3:28 pm, Jean-Philippe Bernardy wrote:
> 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).

Actually I was wondering whether or not the term "left-biasing" was
particularly useful. It could be misleading for some functions.

For example..
-- | /O(n*log n)/. Create a set from a list of elements.
fromList :: Ord a => [a] -> Set a 
fromList xs = foldlStrict ins empty xs
  where ins t x = insert x t

My interpretation of left biasing would be that if the input list contains
multiple occurences of "equal" values then the first occurence is the one
which is inserted in the Set and the rest are discarded. But AFAICS the
this is not the case with the current Data.Set implementation (or with the
clone I just produced). Both are right biased (at least according to my
intuitive understanding of the term).

I think to get left biasing we need to either..
 Use foldr (instead of foldl) with insert as it is.
or..
 Use foldl but with a "right biased" insert function
 (I.E. One which prefers to retain existing elements).

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).
But I guess this is in effect assuming equality implies
structural equality so others may not like it. Sigh.. 

<whine>
I really wish this whole issue of how to properly deal with "things
that are equal but may still be different somehow" would just go
away :-) It's hard to be precise about what choice you've made, and
whatever choice you do make usually seems arbitrary. Even when
it doesn't make any semantic difference, the choice you make may
well have an observable effect on space and time behavior.
</whine>

In the toy FPL I implemented a while ago I actually had combining
comparison hardwired into the rts. This tested for structural
equality and if two values (acyclic graphs) were equal it replaced
the "new" one with an indirection node pointing to the "old" one
(I could tell their relative age by the addresses).

But I still can't quite decide if this was an elegant solution
or an evil hack :-)

Regards
--
Adrian Hey