tags:

views:

145

answers:

4

Suppose I'm writing a function that takes a list of integers and returns only those integers in the list that are less than 5.2. I might do something like this:

belowThreshold = filter (< 5.2)

Easy enough, right? But now I want to constrain this function to only work with input lists of type [Int] for design reasons of my own. This seems like a reasonable request. Alas, no. A declaration that constraints the types as so:

belowThreshold :: [Integer] -> [Integer]
belowThreshold = filter (< 5.2)

Causes a type error. So what's the story here? Why does doing filter (< 5.2) seem to convert my input list into Doubles? How can I make a version of this function that only accepts integer lists and only returns integer lists? Why does the type system hate me?

+3  A: 

You are trying to compare an Integer to a double (5.2). Haskell doesn't like that. Try using

filter (< 6)
Turtle
I guess this is the correct answer in the real world. In a perfect world, I could narrow a function's signature without needing to change implementation details.
Derek Thurn
Really? A change in the type usually implies a change in the implementation: http://en.wikipedia.org/wiki/Curry–Howard_correspondence
Nathan Sanders
@thurn: I would not claim that changing a type from Double to Integer is "narrowing". Integer is not a subtype of Double at all, the structure of their elements is different, they obey different axioms and theorems, etc. etc.Also, there are more canonical Integers than canonical Doubles.
fishlips
@thurn: You didn't narrow it, you changed it to something else entirely. You changed the argument type from a list of Fractionals (or more specifically from a list of as, where `Fractional a`) to a list of Ints. Since Int is not an instance of Fractional, that's not narrowing. Before you changed it, it was not possible to pass a list of Ints as an argument to your function.
sepp2k
@thurn: The syntax 5.2 is valid for any Fractional. Int is not an instance of Fractional, nor can or should it be. Double is. Your expectation is driven by the presence of implicit coercions in many languages. However, those come with a cost. You have to _manually_ ensure that the entire system of coercions is confluent. Haskell does not do this, choosing instead to let numeric literal syntax leverage the type system. To convert between them you need to use fromIntegral to make explicit the need for coercion, this avoids relying on confluence and allows programmers to define new numeric types.
Edward Kmett
+1  A: 

If you must use a double (let's say it is an argument), I would use ceiling:

filter (< (ceiling 5.2))

Now if you want a function that takes in the bounding value as 'any' (relevant) numeric value, you can make your own type class to ceiling the number for you.

class Ceilingable a where
  ceil :: (Integral b) => a -> b

instance (RealFrac a) => Ceilingable a where
  ceil = ceiling

instance (Integral a) => Ceilingable a where
  ceil = fromIntegral

belowThreshold :: (Ceilingable a) => a -> [Integer] -> [Integer]
belowThreshold threshold = filter (< ceil threshold)
trinithis
+7  A: 

Check the inferred type of belowThreshold in ghci before adding your annoatation:

> :t belowThreshold
belowThreshold :: [Double] -> [Double]

It sounds like you expected Num a => [a] -> [a] when you said "constrain this function". You are actually changing the type of the function when you add the [Integer] -> [Integer] annotation.

To make this work, use an explicit conversion:

belowThreshold = filter ((< 5.2) . fromIntegral)

Now belowThreshold :: [Integer] -> [Integer] like you wanted. But the integers are converted to doubles before comparison to 5.2.

So why do you need the conversion? The type error probably misled you: the list of Integers wasn't being converted to Doubles by comparison to 5.2, the real problem is that only Doubles can be compared to Doubles, so you must pass a list of Doubles to belowThreshold. Haskell has no implicit conversions, not even between numbers. If you want conversions, you have to write them yourself.

I want to constrain this function to only work with input lists of type [Int] for design reasons of my own. This seems like a reasonable request.

Well, from the perspective of the type system, no. Is this reasonable code?

'c' < "foo"

What about this?

12 < "bar"

All of these values are instances of Ord, but you can't use them together with (<). Haskell has no implicit conversions. So even if two values are both instances of Num as well as Ord, you won't be able to compare them with (<) if they are of different types.

Nathan Sanders
Actually Haskell has one bit of implicit conversion for numeric literals. "x = 5" is equivalent to "x = fromIntegral 5".
Paul Johnson
I think you have it backwards. At ghci, `:t 5` gives `(Num t) => t` and `:t fromIntegral` gives `(Integral a, Num b) => a -> b`. So `fromIntegral 5` doesn't change the type at all.However, `let x = 5` then `:t x` gives `Integer`. What happened is that a variable must have a type, so ghci just chooses Integer. That's not a conversion, it's a 'narrowing' in the sense that the OP thought was happening in the original code--from `Num t` to `Integer`.
Nathan Sanders
+1  A: 

The syntax 5.2 is valid for any Fractional. Int is not an instance of Fractional, nor can or should it be. As what to do when converting an arbitrary Rational to an Int is underspecified.

The conversion to a Double from an arbitrary fraction, however makes perfectly good sense (within the range of the type).

Your expectation is driven by the presence of implicit coercions in many languages.

However, those come with a cost. You have to manually ensure that the entire system of coercions is confluent. Haskell does not do this, choosing instead to let numeric literal syntax leverage the type system. To convert between them you need to use fromIntegral to make explicit the need for coercion, this avoids relying on confluence and allows programmers to define new numeric types.

belowThreshold = filter (\x -> fromIntegral x < 5.2) 

This is analogous to using an explicit conversion in C++, like ((double)x < 5.2). Although, this statement only works because of defaulting, because 5.2 could be used as a member of any Fractional, and the result of 'fromIntegral x' is any Num, a superclass of Fractional, so fromIntegral x < 5.2 is underspecified, it merely knows that it needs to compare two Fractional values of the same type and it chooses Double as a reasonable default, based on a 'default' statement.

Also note that Int is not the only Integral type, so the above method works on any list of Integral values:

belowThreshold :: Integral a => [a] -> [a]
Edward Kmett