Numbers

London Haskell User Group, 26th February 2014

Ben Clifford
benc@cqx.ltd.uk

Whats a number?

From school you get some intuitive feel for what a number is.

1 -- 2 -- 3 -- 4 -- 5 -- ...

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 typeclass

Num 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 ...

Counting

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

Ring Algebra

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.

Complex numbers

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 Nums

Conversely, complex numbers don't have an ordering, so Complex Float is not an instance of Ord - another intuition that breaks.

Applicative Functors

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

Applicative Functors as Numbers: the guts/1

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)

Applicative Functors as Numbers: the guts/2

[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] ]

Applicative Functors as Numbers: IO

[] 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)

Applicative Functors as Numbers: What doesn't work

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.

Pebbles: Unary counting numbers

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

Pebbles: Adding

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?

Pebbles: How long is a list?

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' ]
[(),(),(),(),()]

Pebbles: Lazy numbers/1

A list can be defined lazily, and so pebble numbers can be too.

Prelude> let infinity = P (repeat ())

Pebbles: Lazy numbers/2

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

Automatic Differentiation

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)

Automatic Differentiation: Combining rules

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

Automatic differentiation: Num instance

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

Also...

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

- fin -

Automatic differentiation

http://augustss.blogspot.co.uk/2007/04/overloading-haskell-numbers-part-2.html + automatic-like differention - there's an impl of this in haskell somewhere - slides - differentiate x^2+x or something simple that people might still understand the differentiation of but still shows the operators being used. A "Number" not only carries with it is value but also its derivative which is a bit weird to grasp. (and for me to explain...) the derivative is how much that number changes with respect to the input variable (so constant 5 doesn't change at all so (5,0), but x (when x = 5) is (5,1) because the slope of x at that position is 5) So we can write out expression in pretty much usual numeric notation. We can even use things like if statements which are awkward to differentiate in other ways. (and this is a bit dodgy, from a strictly mathematical perspective)

Patriot missile failure at Dhahran

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

Spacecraft integer overflows

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

Distinguishing between +0 and -0 :: Float

(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...