Monday, May 07, 2007

I was asked if my fixed number module (Data.Number.Fixed) which has the precision built into the type could be used with a dynamic epsilon, i.e., one that is not know at compile time. The answer is, yes. It only takes a fraction of an oleg to do. A recap: The idea with the Fixed type was that, e.g., Fixed Eps1, is the type where computation happens with an epsilon of 1. To get the epsilon for a type I have a class
class Epsilon e where
    eps :: e -> Rational
instance Epsilon Eps1 where eps _ = 1
...
So what do we do if we need an epsilon of say, 0.01? Well, there's another instance for the type constructor EpsDiv10:
instance (Epsilon e) => Epsilon (EpsDiv10 e) where
    eps x = eps x / 10
So the type EpsDiv10 (EpsDiv10 Eps1) will have an epsilon of 0.01. Similarly, with the right set of primitive types and type constructors you could build any epsilon you want. To simplify a little the function below only finds an epsilon within a factor of 10 from the requested one.
dynamicEps :: forall a . Rational ->
             (forall e . Epsilon e => Fixed e -> a) ->
             (Rational -> a)
dynamicEps r f v = loop (undefined :: Eps1)
 where loop :: forall x . (Epsilon x) => x -> a
       loop e = if eps e <= r then f (fromRational v :: Fixed x)
                else loop (undefined :: EpsDiv10 x)
This function takes a desired (rational) epsilon, r, and a function, f, and returns a function that behaves like f, but that will round its argument to the desired epsilon and compute with that.
Main> putStrLn $ dynamicEps 1e-40 (show . sin) 1
0.8414709848078965066525023216302989996226
How does it work? It's starts by passing something of type Eps1 to loop, and then the loop uses that epsilon if it is small enough, otherwise it will pass something that have an epsilon that is a tenth to the next iteration of the loop. There are two "tricks" here, first the loop function recurses with an argument of a different type than it was given. So it needs polymorphic recursion, and thus needs a type signature. Second, the function, f, has a rank two type. This way the function can work with any epsilon it is given; otherwise we would not know that. Note how the argument to loop is actually never ysed, so undefined works great. All we need is the right type. And with scoped type variables this is easy to do. There are some improvements that should be made to this function: it is inefficient and it doesn't give you the exact epsilon back. But it has the right general idea.

Labels: ,

2 Comments:

Blogger Saizan said...

I think you have a little but deadly bug in your instance:
instance (Epsilon e) => Epsilon (EpsDiv10 e) where
eps x = eps x / 10

here the call to (eps x) is resolved for the same type instead of recursing on e.
so the right implementation would be
eps x = eps (undefined :: e) / 10
if i understand correctly how this work..

Thursday, May 10, 2007 at 12:06:00 AM GMT+1  
Blogger augustss said...

You are right. That's what you get for typing things from memory.
It's correct in the darcs repo.

Tuesday, May 22, 2007 at 2:28:00 AM GMT+1  

Post a Comment

<< Home