[Haskell-cafe] Hit a wall with the type system

[Stefan O'Rear]

On Wed, Nov 28, 2007 at 09:02:20PM -0700, Chris Smith wrote:
> I was talking to a few people about this on #haskell, and it was 
> suggested I ask here.  I should say that I'm playing around here; don't 
> mistake this for an urgent request or a serious problem.
> 
> Suppose I wanted to implement automatic differentiation of simple 
> functions on real numbers; then I'd take the operations from Num, 
> Fractional, and Floating, and define how to perform them on pairs of 
> values and their differentials, and then I'd write a differentiate 
> function... but finding an appropriate type for that function seems to 
> be a challenge.
> 
> We have:
> 
> 1. Differentiating a function of the most general type (Num a => a -> a) 
> should produce a result of type (Num a => a -> a).
> 
> 2. Differentiating a function of the more specific type (Fractional a => 
> a -> a) should produce a result of that type (Fractional a => a -> a).
> 
> 3. Differentiating a function of the most specific type (Floating a => a 
> -> a) should produce a result of type (Floating a => a -> a).
> 
> 4. BUT, differentiating a function which is of a more specific type than 
> (Floating a => a -> a) is not, in general, possible.
> 
> So differentiate should have type A a => (forall b. A b => b -> b) -> a 
> -> a, but ONLY if the type class A is a superclass of Floating.
> 
> Two partial solutions are: I can just define the differentiate function 
> for Floating; but that means if I differentiate (\x -> x + 1), the 
> result is a function only on floating point numbers, which is less than 
> desirable.  Or, I can define several functions: say, diffNum, 
> diffFractional, and diffFloating... all of which have precisely the same 
> implementation, but different types and require copy/paste to make them 
> work.
> 
> Any thoughts?

You can get all the features you want if you are willing to weaken the
problem in the encapsulation dimension.

diffAnything :: (AD a a -> AD a a) -> a -> a
diffAnything f x = case (f (AD x 1)) of AD _ d -> d

Now, you can handle all of the above cases transparently, at the cost of
needing to export the AD type constructor (but not the data
constructor).  And it's H98 to boot.

Stefan
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20071128/96e0e007/attachment.bin