Haskell types frustrating a simple 'average' function

Question

I'm playing around with beginner Haskell, and I wanted to write an average function. It seemed like the simplest thing in the world, right?

Wrong.

It seems like Haskell's type system forbids average from working on a generic numeric type - I can get it to work on a list of Integrals, or an list of Fractionals, but not both.

I want:

average :: (Num a, Fractional b) => [a] -> b
average xs = ...

But I can only get:

averageInt :: (Integral a, Fractional b) => [a] -> b
averageInt xs = fromIntegral (sum xs) / fromIntegral (length xs)

or

averageFrac :: (Fractional a) => [a] -> a
averageFrac xs = sum xs / fromIntegral (length xs)

and the second one seems to work. Until I try to pass a variable.

*Main> averageFrac [1,2,3]
2.0
*Main> let x = [1,2,3]
*Main> :t x
x :: [Integer]
*Main> averageFrac x

<interactive>:1:0:
    No instance for (Fractional Integer)
      arising from a use of `averageFrac ' at <interactive>:1:0-8
    Possible fix: add an instance declaration for (Fractional Integer)
    In the expression: average x
    In the definition of `it': it = averageFrac x

Apparently, Haskell is really picky about its types. That makes sense. But not when they could both be [Num]

Am I missing an obvious application of RealFrac?

Is there way to coerce Integrals into Fractionals that doesn't choke when it gets a Fractional input?

Is there some way to use Either and either to make some sort of polymorphic average function that would work on any sort of numeric array?

Does Haskell's type system outright forbid this function from ever existing?

Learning Haskell is like learning Calculus. It's really complicated and based on mountains of theory, and sometimes the problem is so mindbogglingly complex that I don't even know enough to phrase the question correctly, so any insight will be warmly accepted.

(Also, footnote: this is based off a homework problem. Everybody agrees that averageFrac, above, gets full points, but I have a sneaking suspicion that there is a way to make it work on both Integral AND Fractional arrays)

Answer 1

I'm amazed that after all of these years, no one has pointed out that Don Stewart's average doesn't work with complex numbers, while OP's averageFrac does work with complex numbers. Neither one is unambiguously superior to the other.

The fundamental reason why you can't write

average :: (Num a, Fractional b) => [a] -> b

is that it can be instantiated at a type like

average :: [Complex Double] -> Double

Haskell's numeric classes support conversions that are a little bit lossy, like Rational to Double, Double to Float, and Integer to Int, but don't support extremely lossy conversions like complex to real, or fractional to integral. You can't convert Complex Double to Double without explicitly taking (e.g.) the real part of it, which is not something that average should be doing. Therefore, you can't write average :: [Complex Double] -> Double. Therefore, you can't write average with any type that can be specialized to [Complex Double] -> Double.

The most Haskellish type for average is probably OP's averageFrac. Generally, functions that aren't dedicated to type conversion should be leaving the type conversion to the caller as much as possible. averageFrac will work with practically any numeric type, either directly or after coercion of the input list. The caller, being closer to the source of the data, is more likely to know whether it needs to be coerced or not (and if it doesn't know, it can leave the decision to its caller). In contrast, Don Stewart's average just doesn't support complex numbers, even with coercion. You'd either have to rewrite it from scratch or else call it twice with the real and imaginary projections of the list (and then write another wrapper for quaternions that calls it four times, etc.).

Answer 2

The question has been very well answered by Dons, I thought I might add something.

When calculating the average this way :

average xs = realToFrac (sum xs) / genericLength xs

What your code will do is to traverse the list twice, once to calculate the sum of its elements, and once to get its length. As far as I know, GHC isn't able yet to optimize this and compute both the sum and length in a single pass.

It doesn't hurt even as a beginner to think about it and about possible solutions, for example the average function might be written using a fold that computes both the sum and length; on ghci :

:set -XBangPatterns

import Data.List

let avg l=let (t,n) = foldl' (\(!b,!c) a -> (a+b,c+1)) (0,0) l in realToFrac(t)/realToFrac(n)

avg ([1,2,3,4]::[Int])
2.5
avg ([1,2,3,4]::[Double])
2.5

The function doesn't look as elegant, but the performance is better.

More information on Dons blog:

http://donsbot.wordpress.com/2008/06/04/haskell-as-fast-as-c-working-at-a-high-altitude-for-low-level-performance/

Answer 3

:m Data.List
let list = [1..10]
let average = div (sum list) (genericLength list)
average

Answer 4

Since dons has done such a good job at answering your question, I'll work on questioning your question....

For example, in your question, where you first run an average on a given list, getting a good answer. Then, you take what looks like the exact same list, assign it to a variable, then use the function the variable...which then blows up.

What you've run into here is a set-up in the compiler, called the DMR: the D readed M onomorphic R estriction. When you passed the list straight into the function, the compiler made no assumption about which type the numbers were, it just inferred what types it could be based on usage, and then picked one once it couldn't narrow the field down any more. It's kind of like the direct opposite of duck-typing, there.

Anyway, when you assigned the list to a variable, the DMR kicked in. Since you've put the list in a variable, but given no hints on how you want to use it, the DMR made the compiler pick a type, in this case, it picked one that matched the form and seemed to fit: Integer. Since your function couldn't use an Integer in its / operation (it needs a type in the Fractional class), it makes that very complaint: there's no instance of Integer in the Fractional class. There are options you can set in GHC so that it doesn't force your values into a single form ("mono-morphic", get it?) until it needs to, but it makes any error messages slightly tougher to figure out.

Now, on another note, you had a reply to dons' answer that caught my eye:

I was mislead by the chart on the last page of cs.ut.ee/~varmo/MFP2004/PreludeTour.pdf that shows Floating NOT inheriting properties from Real, and I then assumed that they would share no types in common.

Haskell does types differently from what you're used to. Real and Floating are type classes, which work more like interfaces than object classes. They tell you what you can do with a type that's in that class, but it doesn't mean that some type can't do other things, any more than having one interface means that a(n OO-style) class can't have any others.

Learning Haskell is like learning Calculus

I'd say learning Haskell is like learning Swedish - there are lots of little, simple things (letters, numbers) that look and work the same, but there are also words that look like they should mean one thing, when they actually mean something else. But once you get fluent in it, your regular friends will be amazed at how you can spout off this oddball stuff that makes gorgeous beauties do amazing tricks. Curiously, there are many folks involved in Haskell from the beginnings, who also know Swedish. Maybe that metaphor is more than just a metaphor...

Answer 5

So fundamentally, you're constrained by the type of (/):

(/) :: (Fractional a) => a -> a -> a

BTW, you also want Data.List.genericLength

genericLength :: (Num i) => [b] -> i

So how about removing the fromIntegral for something more general:

import Data.List

average xs = realToFrac (sum xs) / genericLength xs

which has only a Real constraint (Int, Integer, Float, Double)...

average :: (Real a, Fractional b) => [a] -> b

So that'll take any Real into any Fractional.

And note all the posters getting caught by the polymorphic numeric literals in Haskell. 1 is not an integer, it is any number.

The Real class provides only one method: the ability to turn a value in class Num to a rational. Which is exactly what we need here.

And thus,

Prelude> average ([1 .. 10] :: [Double])
5.5
Prelude> average ([1 .. 10] :: [Int])
5.5
Prelude> average ([1 .. 10] :: [Float])
5.5
Prelude> average ([1 .. 10] :: [Data.Word.Word8])
5.5

Answer 6

Yeah, Haskell's type system is very picky. The problem here is the type of fromIntegral:

Prelude> :t fromIntegral
fromIntegral :: (Integral a, Num b) => a -> b

fromIntegral will only accept an Integral as a, not any other kind of Num. (/), on the other hand only accepts fractional. How do you go about making the two work together?

Well, the sum function is a good start:

Prelude> :t sum
sum :: (Num a) => [a] -> a

Sum takes a list of any Num and returns a Num.

Your next problem is the length of the list. The length is an Int:

Prelude> :t length
length :: [a] -> Int

You need to convert that Int into a Num as well. That's what fromIntegral does.

So now you've got a function that returns a Num and another function that returns a Num. There are some rules for type promotion of numbers you can look up, but basically at this point you're good to go:

Prelude> let average xs = (sum xs) / (fromIntegral (length xs))
Prelude> :t average
average :: (Fractional a) => [a] -> a

Let's give it a trial run:

Prelude> average [1,2,3,4,5]
3.0
Prelude> average [1.2,3.4,5.6,7.8,9.0]
5.4
Prelude> average [1.2,3,4.5,6,7.8,9]
5.25