type classes and generality

Fergus Henderson fjh@cs.mu.oz.au
Tue, 10 Jul 2001 11:00:44 +1000

On 09-Jul-2001, Norman Ramsey <nr@eecs.harvard.edu> wrote:
>  > On 09-Jul-2001, Norman Ramsey <nr@eecs.harvard.edu> wrote:
>  > > I'm trying to model probability and leave the
>  > > representation of probability unspecified other than
>  > > it must be class Real.  But I'm having trouble with
>  > > random numbers; how can I show that if a type has class Real,
>  > > it also has class Random.Random?  Is there a way to accomplish
>  > > this goal other than by changing the library?
>  > 
>  > I'm not sure if I fully understand your goal.
>  > But one thing you can do is to define a wrapper type
>  > 
>  > 	newtype WrapReal r = WrapReal r
>  > 
>  > and make the wrapper an instance of Random.Random
>  > if the underlying type is an instance of Real
>  > 
>  > 	instance Real r => Random.Random (WrapReal r) where
>  > 		...
>  > 
>  > Then you can use the wrapper type whenever you want to get a random number.
> The problem is that without intensional type analysis, I wouldn't know
> how to fill in the instance methods in the `...'

How about like so?

	import Random

	newtype WrapReal r = WrapReal r
	wrap r = WrapReal r
	unwrap (WrapReal r) = r

	instance Real r => Random (WrapReal r) where
		random = randomR (wrap 0, wrap 1)
		randomR (min, max) gen0 = (wrap (fromInteger r), gen) where
			(r, gen) = randomR (imin, imax) gen0
			imin = ceiling (toRational (unwrap min))
			imax = floor (toRational (unwrap max))

Ah, now I think I understand your problem.  You want to `random' to
generate random numbers that span all the possible values of the type
within the range [0, 1], or at least a substantial subset, but the "Real"
class doesn't let you generate any numbers other than integers.
The above approach will give you random numbers from `random', but they
will only ever be 0 or 1, so maybe they are not as random as you needed! ;-)

The proof that you can only generate integers values of the real type
(by which I mean values of the real type for which toRational returns
an integer) is that the only methods of class Real which return values
of the type are "fromInteger", and the operators ("+", "*", "-",
"negate", "abs", and "signum"), which are all integer-preserving --
when given integers they will always return other integers.
So by induction you can't generate any non-integers.

I'd advise you to  add an extra "Random t" class constraint to those
parts of your application that rely on generating random numbers.
If you find yourself using `Real t, Random t' frequently, you can
use a derived class for that:

	class (Random t, Real t) => RandomReal a where
		-- no methods

Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.