London Haskell User Group, 26th February 2014
Ben Clifford
benc@cqx.ltd.uk
From school you get some intuitive feel for what a number is.
But it turns out to be a bit fuzzy - those intuitions sometimes break.
You get to choose what breaks and how by using different
instances of the Num
typeclass, and various
related typeclasses.
Num
typeclassNum
from base: (different in the Haskell report)
class Num a where (+), (-), (*) :: a -> a -> a negate :: a -> a abs :: a -> a signum :: a -> a -- abs x * signum x == x fromInteger :: Integer -> a
Not much in the way of rules about how these are meant to behave! Just this one rule about absolute values.
No casting, except fromInteger. You can't add a Float
and a Word8
, for example.
Other type classes add more features: Real
, Integral
, Fractional
, Floating
, RealFrace
, RealFloat
.
Also might expect: Eq
, Ord
, Show
...
What rules might we expect numbers to follow?
We can always add 1 to a number. And we always get a bigger number by doing that.
Prelude> 1 + 1 2 Prelude> 2 + 1 3 Prelude> 3 + 1 4 Prelude> 4 + 1 5 ... Prelude> 2147483647 + 1 :: Int -2147483648
So the Int
type can't even count, and doesn't even tell us when it does the "wrong" thing. But Int
still OK for a lot of uses.
All the fixed width integer types, signed or unsigned, behave like this. eg Word8
But not Integer
- more expensive
Using the ring laws:
x + 1 - x = x - x + 1 = 0 + 1 = 1
but ...
> quickCheck (\(x :: Float) -> (x + 1 - x == 1)) *** Failed! Falsifiable (after 2 tests): 1.299421
... and it only took 2 tries to break.
First WTF-weird number things at A-Level.
Loads of stuff breaks here. Numbers aren't even on the number line - you draw then off sideways and measure angles and all sorts. So they aren't ordered.
I was surprised to find Haskell has Data.Complex
in base.
So we've got Euler's identity (xkcd 179):
let pi = 3.14 :+ 0 :: Complex Float let i = 0 :+ 1 :: Complex Float > exp (-i * pi) + 1 1.2516975e-6 :+ (-1.592548e-3)
Not quite 0, but almost... and you shouldn't be expecting anything to work by now.
exp
comes from the Floating
typeclass, which basically is a typeclass with trigonometry, logs and exponentials in it - functions which don't make sense for arbitrary Num
s
Conversely, complex numbers don't have an ordering, so Complex Float
is not an instance of Ord
- another intuition that breaks.
Some maths packages let you write expressions like this:
10 * [2,3,4] > [20,30,40]
Can this work in Haskell?
instance (Applicative a, Num n) => Num (a n) where x * y = (*) <$> x <*> y fromInteger i = pure (fromInteger i) ...
These two definitions are sufficient for the above.
link: r/haskell comments
So what happens inside?
10 * [2,3,4] > [20,30,40]
First, the 10. That's not a list. Right? ...
Integer literals desugar into fromInteger 10
.
:type 10 10 :: Num a => a
That's how 10
can be any Num instance - eg Integer or Float, or in our case, an Applicative.
10 = fromInteger 10 (by Haskell desugaring) = pure 10 (by our Applicative => Num definition) = [10] (by Applicative List instance)
[10] * [1,2,3]
The Applicative Num instance defines a*b
as
(*) <$> a <*> b
In this list case, this multiples each element of the first list with each element of the second element. As a list comprehension:
[x * y | x <- [10], y <- [1,2,3] ]
[] is one of the standard Applicatives (or Monads). An other is
IO
.
So what do "IO numbers" look like?
*AppNum> readLn + 1 100 101 *AppNum> readLn + readLn 3 4 7 *AppNum> :t (readLn + readLn) (readLn + readLn) :: (Num a, Read a) => IO a *AppNum>
(my motivating case was netwire, from ocharles' previous talk)
Num
operations always yield a value in the Num
type (RHS always a), so in the Applicative.
For example:
* :: a -> a -> a fromInteger :: Integer -> a
But this isn't true for some of the other numeric typeclasses.
eg. Ord
.
compare :: Ord a => a -> a -> Ordering
You can't extract a value out of a monad. This is that problem.
eg. What does it mean to ask:
readLn > readLn :: Ordering
This makes sense:
c' :: IO Int -> IO Int -> IO Ordering
... but that isn't Ord
.
Caveman style counting sheep. Every time you let a sheep out into the field you put a pebble in a bag. Or, lazy peano numbers.
LISP and dependent type people like counting this way.
data Number = Zero | Successor Number
Slightly different definition:
data [a] = [] | a : [a]
...and use lists of units, [()]
.
Values look like:
[] -- empty bag [ () ] -- one pebble [ (), () ] -- two pebbles [ (), (), () ] -- three pebbles
Lets add [ (), () ] and [ () ]
Prelude> [ (), () ] ++ [ () ] [(),(),()]
+ is ++
newtype P = P [()] instance Num P where (P a) + (P b) = P (a ++ b)
Ask the audience: How you might define *
?
And what does tail
mean? And when does it fail?
A list contains its own length in this mechanism:
How long is [ 'h', 'e', 'l', 'l', o' ]
in pebble numbers?
It is [ (), (), (), (), () ]
long.
All we have to do is forget the values in the list, but keep the backbone...
Prelude> map (const ()) [ 'h', 'e', 'l', 'l', o' ] [(),(),(),(),()]
A list can be defined lazily, and so pebble numbers can be too.
Prelude> let infinity = P (repeat ())
We can have partially defined numbers:
let argh = P $ error "ARGH!!!" let n = 4 + argh
What do we know about this number n
?
With appropriate Ord
instance:
*Main> (4 + argh) > 2 True *Main> (4 + argh) > 10 *** Exception: ARGH!!! *Main> infinity < 8 False
Given a formula f x = x^2 + x, I want to know the gradient of the function at some point, say x=5.
*Main> let f x = x^2 + x *Main> diff f 5 11
Numbers that carry their own derivative... (sort of)
From A-levels, we know:
f x = 3 diff f _ = 0 -- (always)
f x = x diff f _ = 1 -- (always)
Adding two functions:
diff (\x -> f x + g x) v = diff f x + diff g x
diff (\x -> f x * g x) v = (diff f v) * g v + (diff g v) * f v
So, what's diff (\x -> x*x) at 3?
diff (\x -> x * x) 3 = ? (\x -> x) 3 = 3 diff (\x -> x) 3 = 1 apply product rule and... x*x = 3 * 3 = 9 diff (\x -> x*x) 3 = 3 * 1 + 1 * 3 = 6
In this code:
diff (\x -> x*x) 3
x has type: Numeric.AD.Internal.Types.AD s Float
which carries round both a Float and its derivative as a pair of Floats.
+, * are as previous slide: addition and product rules.
fromInteger is a constant, with 0 derivative.
x, the variable we are differentiating with respect to,
gets constructed and passed in by diff
.
Other stuff like sin and cos implemented too! Because dual numbers are
also instances of Floating
type class, which provides
pi, cos, sqrt, sin, cos, etc
Lots of structures behave unexpectedly quite like intuitive numbers.
Lots of structures that you think of as numbers don't behave quite like numbers.
Other things:
Clock arithmetic, Interval Arithmetic, Fuzzy numbers, Probability Distributions, Polynomials,
Foreign.C, numbers
package, LogFloat
On 25 February 1991, an Iraqi Scud hit the barracks in Dhahran, Saudi Arabia, killing 28 soldiers from the U.S. Army's 14th Quartermaster Detachment. [...] [...] The radar system had successfully detected the Scud and predicted where to look for it next, but because of the time error, looked in the wrong part of the sky and found no missile. With no missile, the initial detection was a ssumed to be a spurious track and the missile was removed from the system. No interception was attempted, and the missile impacted on a makeshift barracks in an Al Khobar warehouse, killing 28 soldiers.
More info on wikipedia and http://sydney.edu.au/engineering/it/~alum/patriot_bug.html
Time measured in 10ths of a second, which is not a "round number" in binary floating point, because it has a non-terminating binary expansion. (like 1/3 does in decimal, as 0.33333....)
As we add 10ths of a second we drift away from actual time.
Do this for 100 hours...
Some numbers: speed of a scud: 1.7km/sec x 1/3rd sec timing error: difference about 500 metres
wikipedia: Cluster (spacecraft)
The launch, which took place on Tuesday, 4 June 1996, ended in failure due to an error in the software design caused by assertions having been turned off, which in turn caused inadequate protection from integer overflow. This resulted in the rocket veering off its flight path 37 seconds after launch, beginning to disintegrate under high aerodynamic forces, and finally self-destructing by its automated flight termination system. The failure has become known as one of the most infamous and expensive software bugs in history
conversion from the 64 bit float to 16 bit unsigned integer is not protected.
and ... if you're a static analysis fan:
The subsequent automated analysis of the Ariane code was the first example of large-scale static code analysis
(0 :: Float) == (-0 :: Float)
but...
(show $ (0 :: Float)) == (show $ (-0 :: Float)) => False
Maybe you'd expect
a == b => show a == show b
which is roughly:
If we show the same thing, we get the same output.
http://www.cs.berkeley.edu/~wkahan/JAVAhurt.pdf - lots of bits.
Also comment that there are NaNs and infinities and floating point exceptions, and reordering has a bit of a similar feel to undefined and strictness in Haskell... see paras 3,4 of p80 of that JAVAhurt pdf and can change where rounding errors happen...