[Haskell-cafe] Ix, Random, and overlapping instances
bulat.ziganshin at gmail.com
Mon Aug 21 04:03:42 EDT 2006
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
>> (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
Bulat mailto:Bulat.Ziganshin at gmail.com
More information about the Haskell-Cafe