[Haskell-cafe] Ix, Random, and overlapping instances

[Bulat Ziganshin]

Hello Lambda,

Monday, August 21, 2006, 1:20:26 AM, you wrote:

> Greetings Haskellers,

> I have recently found myself in a situation where I was needing to  
> general tuples of randomized things; in my case, two coordinates and  
> a custom data type, Direction.  As it is always better to generalize,
> I decided to try to write some code which would generalize randomR to
> any type which is Ix-able:

 >> instance Ix i => Random i where
 >>    random = error "No supported instance for random"
 >>    randomR r g
 >>        = let
 >>          r' = range r
 >>          (i, g') = randomR (0,length r'-1) g
 >>          in
 >>          (r' !! i, g')

 using of (!!) is very inefficient. i don't think that GHC will
 optimize such code to just arithmetic operations


> This works splendidly; with my given example above, I could do:

 >> data Dir = N | NE | E | SE | S | SW | W | NW deriving (Eq, Ord,  
> Show, Ix)

>      ghci> newStdGen >>= print . take 10 . randomRs ((1,1,N),(10,10,NW))

>      [(5,4,S), (3,10,SE), (6,5,N), (6,6,NW), (10,8,SE), (3,10,W),  
> (10,3,E), (1,6,NE), (10,10,SE), (3,3,S)]

> As you can see, this results in random tuple(s) of these indexable  
> types.  My implementation required -fallow-overlapping-instances and -
> fallow-undecidable-instances for the code to compile.

> A few questions:

> 1) How does the compiler determine how to choose a particular  
> instance for those cases where they overlap?

it selects most specific instance, preferring concrete types over type
classes. but it don't take into account hierarchy of classes. afair,
chapter 7 of GHC user's guide considers type system extensions


> I noticed that if I  
> tried to generate a random :: Int, I was getting the error message  
> defined in the above instance, indicating that the compiler was  
> choosing my implementation over the default for Int (obviously  
> because Int is an instance of Ix).  Is there some way to exclude  
> classes in the class qualifier, or to provide an instance as a  
> default case without resorting to -fallow-overlapping-instances?

it's better to show your complete code. as one possible workaround i
can suggest the following:

class Ix i => Random i ....

instance Random Int ...
instance Random (Int,Int)  -- default definitions will be used


> 2) Is there a logical overlap between class Ix and class Bounded?  It
> seems that we could use the ranges of data types of Bounded to  
> generate a reasonably sane `random` implementation for all Ix, if we  
> can guarantee that all Ix instances are Bounded.  Would adding an  
> additional class constraint be sufficient to catch the major cases?   
> i.e., instance (HasBounds i, Ix i) => Random i where ...

btw, how about the following:

instance (Enum i, Bounded i) => Random i where ...

and then defining instances for tuples? it will be efficient and
overlappings-free


> 3) Is there some reason that Ix is restricted to the Int datatype?   
> Is there anything preventing us from moving to a genericIx,or  
> something along those lines which support any integral type (say  
> Integer), or is it merely for performance reasons that we use Int?   
> Is the expectation that if you are using spaces larger than what an  
> Int can accommodate, you should be using a different mechanism?

i think that this just because Ix was introduced solely for array
indexing which 1) should be fast, 2) almost don't require indexes
larger than Int can hold


-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin at gmail.com