Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Using Haskell ranges: Why would mapping a floating point function across a range cause it to return an extra element?

I know that floats can lead to odd behavior in ranges due to their imprecise nature. I would expect the possibility of imprecise values. For instance: [0.1,0.3..1] might give [0.1,0.3,0.5,0.7,0.8999999999999999] instead of [0.1,0.3,0.5,0.7,0.9]

In addition to the precision loss, however, I get an extra element:

ghci> [0.1,0.3..1]
[0.1,0.3,0.5,0.7,0.8999999999999999,1.0999999999999999]

This is weird, but explained here. I could work around it like this, I suppose:

ghci> [0.1,0.3..0.99]
[0.1,0.3,0.5,0.7,0.8999999999999999]

But that's kind of gross. Maybe there's a cleaner way. For this simple example, of course, I could just use the range [0.1,0.3..0.9] and everything is fine.

But in a more complex example, I may not quickly know (or care to figure out, if I'm lazy) the exact upper bound I should use. So, I'll just make a range of integers and then divide by 10, right? Nope:

ghci> map (/10) [1,3..10]
[0.1,0.3,0.5,0.7,0.9,1.1]

Any floating point function seems to cause this behavior:

ghci> map (*1.0) [1,3..10]
[1.0,3.0,5.0,7.0,9.0,11.0]

Whereas a non-floating function doesn't:

ghci> map (*1) [1,3..10]
[1,3,5,7,9]

While it seems unlikely, I thought that maybe some lazy evaluation was at play, and tried to force evaluation of the range first:

ghci> let list = [1,3..10] in seq list (map (*1.0) list)
[1.0,3.0,5.0,7.0,9.0,11.0]

Obviously, using the literal list instead of the range works fine:

ghci> map (*1.0) [1,3,5,7,9]
[1.0,3.0,5.0,7.0,9.0]

ghci> let list = [1,3,5,7,9] in seq list (map (*1.0) list)
[1.0,3.0,5.0,7.0,9.0]

It isn't just mapping either:

ghci> last [1,3..10]
9

ghci> 1.0 * (last [1,3..10])
11.0

How does applying a function to the result of a range can impact the actual evaluated result of that range?

like image 690
zivarah Avatar asked Apr 07 '14 00:04

zivarah


1 Answers

I answered this for myself as I was writing it.

Haskell uses type inference, so when it sees a floating point function being mapped over a list (or used on an element of that list, as in my example using last), it is going to infer the type of that list to be floating point and therefore evaluate the range as if it were [1,3..10] :: [Float] instead of what I was intending, which is [1,3..10] :: [Int]

At this point, it uses the Float rules for enumerating, as described in the post that I linked to in the question.

The expected behavior can be forced like this:

ghci> map (\x -> (fromIntegral x) / 10) ([1,3..10]::[Int])
[0.1,0.3,0.5,0.7,0.9]

Relying on Haskell's type inference, we can drop the ::[Int] since fromIntegral causes our lambda expression to have the correct type:

ghci> :t (\x -> (fromIntegral x) / 10)
(\x -> (fromIntegral x) / 10)
  :: (Fractional a, Integral a1) => a1 -> a
like image 82
zivarah Avatar answered Oct 30 '22 21:10

zivarah