Exponentiation in Haskell

Question

Can someone tell me why the Haskell Prelude defines two separate functions for exponentiation (i.e. ^ and **)? I thought the type system was supposed to eliminate this kind of duplication.

Prelude> 2^2
4
Prelude> 4**0.5
2.0

Solution 1

There are actually three exponentiation operators: (^), (^^) and (**). ^ is non-negative integral exponentiation, ^^ is integer exponentiation, and ** is floating-point exponentiation:

(^) :: (Num a, Integral b) => a -> b -> a
(^^) :: (Fractional a, Integral b) => a -> b -> a
(**) :: Floating a => a -> a -> a

The reason is type safety: results of numerical operations generally have the same type as the input argument(s). But you can't raise an Int to a floating-point power and get a result of type Int. And so the type system prevents you from doing this: (1::Int) ** 0.5 produces a type error. The same goes for (1::Int) ^^ (-1).

Another way to put this: Num types are closed under ^ (they are not required to have a multiplicative inverse), Fractional types are closed under ^^, Floating types are closed under **. Since there is no Fractional instance for Int, you can't raise it to a negative power.

Ideally, the second argument of ^ would be statically constrained to be non-negative (currently, 1 ^ (-2) throws a run-time exception). But there is no type for natural numbers in the Prelude.

Solution 2

Haskell's type system isn't powerful enough to express the three exponentiation operators as one. What you'd really want is something like this:

class Exp a b where (^) :: a -> b -> a
instance (Num a,        Integral b) => Exp a b where ... -- current ^
instance (Fractional a, Integral b) => Exp a b where ... -- current ^^
instance (Floating a,   Floating b) => Exp a b where ... -- current **

This doesn't really work even if you turn on the multi-parameter type class extension, because the instance selection needs to be more clever than Haskell currently allows.

Solution 3

It doesn't define two operators -- it defines three! From the Report:

There are three two-argument exponentiation operations: (^) raises any number to a nonnegative integer power, (^^) raises a fractional number to any integer power, and (**) takes two floating-point arguments. The value of x^0 or x^^0 is 1 for any x, including zero; 0**y is undefined.

This means there are three different algorithms, two of which give exact results (^ and ^^), while ** gives approximate results. By choosing which operator to use, you choose which algorithm to invoke.

Solution 4

^ requires its second argument to be an Integral. If I'm not mistaken, the implementation can be more efficient if you know you are working with an integral exponent. Also, if you want something like 2 ^ (1.234), even though your base is an integral, 2, your result will obviously be fractional. You have more options so that you can have more tight control over what types are going in and out of your exponentiation function.

Haskell's type system does not have the same goal as other type systems, such as C's, Python's, or Lisp's. Duck typing is (nearly) the opposite of the Haskell mindset.

View more solutions

Comments

[augustss]

I don't totally agree that Haskell type mindset is the opposite of duck typing. Haskell type classes are quite a lot like duck typing. class Duck a where quack :: a -> Quack defines what we expect of a duck, and then each instance specifies something that can behave like a duck.

[Dan Burton]

@augustss I see where you're coming from. But the informal motto behind duck typing is "if it looks like a duck, acts like a duck, and quacks like a duck, then it's a duck." In Haskell it's not a duck unless it is declared an instance of Duck.

[augustss]

That's true, but that's what I'd expect from Haskell. You can make anything you want a duck, but you have to be explicit about it. We don't want to mistake something we didn't ask for to be a duck.

[RussellStewart]

Is the statement about this not being implementable still true? IIRC, haskell has an option for the second parameter of a multi-parameter type class to be determined strictly by the first parameter. Is there another problem beyond this that can't be solved?

[augustss]

@singular It's still true. The first argument doesn't determine the second, for instance, you want the exponent to be both Int and Integer. To be able to have those three instance declarations the instance resolution has to use backtracking, and no Haskell compiler implements that.

[Erik Kaplun]

Does the "type system isn't powerful enough" argument still hold as of March 2015?

[augustss]

You certainly can't write it the way I suggest, but there could be some way to encode it.

[Martin Capodici]

@ErikAllik probably does for standard Haskell, as no new Haskell Report has come out since 2010.

[augustss]

It also holds for ghc Haskell.

[mmachenry]

There is a more specific difference between the Haskell way of doing things and duck typing. Yes, you can give any type the Duck class but it is not a Duck. It's capable of quacking, sure but it's still, concretely, whatever type it was. You still can't have a list of Ducks. A function that accepts a list of Ducks and mixing and matching various types of class Duck will not work. In this respect Haskell does not allow you to just say "If it quacks like a duck, then it's a duck." In Haskell, all of your Ducks must be Quackers of the same type. This is quite different from duck typing indeed.

[Bolpat]

You can have a list of mixed ducks, but you need the extension of Existential Quantification.