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

Bulat Ziganshin bulat.ziganshin at gmail.com
Mon Aug 21 04:03:42 EDT 2006

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

> 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

More information about the Haskell-Cafe mailing list