Set & Int

[Serge D. Mechveliani]

Date: Thu, 02 Jun 2005 10:29:03 -0400
People discussed the Map implementation in GHC:

  data Set a =   Tip
               | Bin {-# UNPACK #-} !Size a !(Set a) !(Set a)

  type Size = Int
  ...

I do not think that these strict fields can do a real harm, 
because they effect only a single level of data construction.
And even if it was a strict language, operating with large sets
would be all right. 
Still, I would prefer to remove `!' and UNPACK, in order to preserve 
a pure language.
 
But what I really do not understand is: why not `Integer'?
What difficulties may cause the design with

  size :: Set a -> Natural
  type Natural = Integer 

What will be the difference?
With each  insert  envokation, recomputing  size  costs  O(log n),
the next call for  size  costs  O(1).
Right?
Everything looks like for `Int' -- except that `Int' is a bug.
"v :: Int"  is a bug, if  v  can occur large.
For example, we could imagine (there may appear, there may exist) 
a machine capable to process in a real time the number of cells much 
greater than  maximal_Int.
This depends on hardware architecture specifics.
For such sets  sS,  size sS :: Int  returns incorrect result.

Regards,

-----------------
Serge Mechveliani
mechvel at botik.ru