# Lazy Arithmetic in Haskell

We don’t usually give much thought to Numeric data types beyond whether we want to work with integers or decimal numbers. And that is a shame! In this post I’ll look at how we can actually do arithmetic operations lazily, and in the process hopefully reveal a bit about haskell’s numeric classes.

```
module LazyArithmetic
where
```

We will be using
Lennart Augustsson’s `numbers`

library which can be
installed from hackage with
cabal-install:

```
$ cabal install numbers
```

import these libs:

```
import Data.Number.Natural
import Data.List(genericLength)
```

Consider two functions: the Prelude function `sum`

and `genericLength`

from
the List library:

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

…two simple functions that have the potential to be very expensive, depending on the length of the list and the values of the elements. Say for instance that all we want is to use:

```
sumLengths = sum . map genericLength
checkLengths as n = (sumLengths as `div` n) > 2
```

The `checkLengths`

function above has to count every element of every element
of every sub-list in order to return a `Bool`

value, and if any of those lists
are infinite our program will never terminate:

```
hopeless = checkLengths [['a'..'z'], ['0'], repeat 'Z'] 99
```

*…or so we might think!*

### Lazy Natural Numbers

It turns out we can solve our seemingly hopeless situation with a type signature:

```
sumLengths :: [[b]] -> Natural
```

And suddenly, as if by magic:

```
*LazyArithmetic> hopeless True
```

What’s going on here? Well it turns out the problem is that Haskell’s built-in numeric types are boring, old-fashioned and (in some cases) just plain wrong. But let’s step behind the curtain and look at how the Data.Numbers library defines the Natural type internally:

```
data Natural = Z | S Natural
```

We see that we’re using an abstract data type to represent non-negative
integers, and it looks nearly identical to our list type `[]`

. The upshot of
that is we gain, in our numeric type and arithmetic operations, the same type
of laziness that lists afford us!

So in the above example, `hopeless`

, we need only carry out the operations far
enough to see that the result is `> 2`

.

The numeric type in `Data.List.Natural`

are actually known as
Peano numbers. They are
essentially just lists of units and, as you might imagine, are not the most
efficient way to represent an integer.

But they are exactly what we want for this application. If we failed to realize that we could solve our problem with an appropriate numeric representation, we might try to rig up something like this:

```
checkLengthsUnclear as n = not $ null $ drop (n*2) $ concat as
```

…which works identically to `checkLengths`

with Peano Numbers, but
completely obfuscates the intention of the function. As usual laziness gives
us *expressive power* rather than an efficiency boost.

### Limitations, Haskell’s Numeric Type Classes, and the Numeric Prelude

The `Data.Number.Natural`

library is convenient because it provides Num and
Integral instances so we can use the the Natural type with any function that
is polymorphic on those classes.

The problem is the Num instance is incomplete
and error-prone: and that’s because a
natural number type *shouldn’t be an
instance of Num*! We can’t negate a Natural, which in turn makes subtraction
dangerous, etc.

```
*LazyArithmetic> let x = 1 :: Natural; y = 2 in x - y
*** Exception: Natural: (-)
```

We might wish that haskell’s Numeric type classes were more expressive, allowing for more abstract numeric types. For example it might be more “haskelly” for the length function to be defined with the type:

```
length :: Natural n => [a] -> n
```

After all we don’t use integers for boolean values as in C; we have the
abstract type `Bool`

. So why return an Int when a Natural type (or class)
might be more expressive? The answer of course is that that gets really
complicated really fast.

For one approach at making haskell’s numeric class hierarchy more expressive and flexible, check out the Numeric Prelude. It’s haddock documentation is very thorough and an interesting read, and you can see the sheer number of design decisions necessary for such an undertaking.

For some other approaches and links, see here.