User:Davjam2/Numbers

Note

This is a draft of a new page to add to the Haskell Wikibook.

I think (hope) it's worth writing. I was very confused when I first tried to do any numerical stuff in Haskell, even though I had be programming in Haskell for a few years by then and was already quite comfortable with types and typeclasses.

I do have some concerns:

• is it too long? (should it be divided, or some sections separated out)?
• there is overlap/duplication with existing content
• is it too GHC specific?
• is unsafePerformIO OK as used? It looks controversial (e.g. here). Is there a better way to catch the errors without it than my monadic mess putOpTableE?

Quite a bit is said about numbers in the Type basics II and Classes and types pages. Those pages use the numeric types and classes in Haskell to illustrate the Haskell type system. This page is more focussed on numbers themselves: how to do different types of numeric computations using the Haskell types and classes.

Numbers

Subsets of Numbers

Mathematically, numbers can be classified into different sets, such as the integers ($\mathbb {Z}$), the rational numbers ($\mathbb {Q}$) and the real numbers ($\mathbb {R}$). It is common to say that the integers are a subset of the rational numbers, and that the rational number 5 "is an integer". Some operations, such as division, are only possible within certain sets of numbers: there is no solution to $2x=5$ amongst the integers, but there is amongst the rational numbers. Rational numbers are said to be closed under division (excluding division by zero), but integers are not.

No programming language (not even Haskell) has a way of representing "any number". Generally, a language will have different numeric types, each representing (possibly a subset of) the numbers in one of the classification sets. In Haskell, there are types such as Integer, Rational and Float that closely represent $\mathbb {Z}$, $\mathbb {Q}$ and a subset of $\mathbb {R}$. Prelude provides a number of these types, and more are available in other modules. None of these types is perfect in all situations: for example, none of the standard types can represent ${\sqrt {2}}$ or $\pi$ precisely.

In Haskell, the 5 :: Integer and 5 :: Rational are definitely not the same thing. It's not even possible to compare them directly using (==), since (==) can only compare values of the same type. Many programming languages allow operations on numbers of different types (such as adding the integer 5 to the number 3.14). They usually do this by quietly "upgrading" one of the numbers so that they are both of the same types before applying the operation. Haskell does not directly allow addition of different types of number, nor does it quietly "upgrade" numbers to different types. It does, however, allow explicit conversion between types.

Most standard numeric operations are defined as class methods, so that they work on all of the relevant numeric types. For example: (+) (addition) is defined to work on all numeric types; (/) (division, which can find the solution to $2x=5$) is not available for integer types; and sin (finding the sine of an angle) will work on types representing (as well as they can) real numbers. A smaller number of mathematical operations (e.g. gcd) are defined as functions (which call the class methods). Many of the numerical functions (class methods or not) are partial, and will throw exceptions for certain parameters (for example division by zero, for some types). You should either ensure your code avoids such parameters, or handles the exceptions that may occur.

Numeric Types

Some of the Haskell numeric types are:

Set		Type	Module	Values	Example
$\mathbb {N} _{0}$	$\equiv$	Natural	Numeric.Natural	unbounded unsigned integers	2158269056624017538838
	$\supset$	Word8, Word16, etc	Data.Word	unsigned integers that can be stored in 8, 16, etc, computer bits	252
	$\supset$	Word		unsigned integers, based on the size of the computer's register	4294967242
$\mathbb {Z}$	$\equiv$	Integer		unbounded signed integers	2158269056624017538838
	$\supset$	Int8, Int16, etc	Data.Int	signed integers that can be stored in 8, 16, etc, computer bits	126
	$\supset$	Int		signed integers, based on the size of the computer's register	2147483621
$\mathbb {Q}$	$\equiv ^{+}$	Rational		a ratio of two Integers	2158269056624017538838 % 5
	$\supset ^{+}$	Ratio Int	Data.Ratio	a ratio of two Ints	22 % 7 (${\tfrac {22}{7}}$, or $3{\tfrac {1}{7}}$)
	$\supset$	Deci, Centi, Milli, etc	Data.Fixed	unbounded signed numbers with a fixed number of decimal places	271.20
$\mathbb {R}$	$\supset ^{+}$	Float		IEEE single-precision floating point numbers (about 8 significant digits)	3.1415927
	$\supset ^{+}$	Double		IEEE double-precision floating point numbers (about 16 significant digits)	3.141592653589793
$\mathbb {C}$	$\supset ^{+}$	Complex Float	Data.Complex	complex numbers whose real and imaginary parts are both represented by Floats.	3.29 :+ 2.5 ($3.29+2.5i$)

The set shown against a type is the "smallest" of those sets illustrated above that contains all of the numeric values of that type. The types Natural, Integer and Rational can represent all of the values in the corresponding sets, subject to the computer's memory and performance limits. The other types can represent only subsets of the corresponding sets, for example Int8 can only represent integers in the range -128 to 127, and Float can only represent those real numbers within the (approximate) range –3.4028235 × 10³⁸ to –3.4028235 × 10³⁸ that can be written with about 8 significant digits.

In mathematics, any value in a "smaller" set has an equivalent in a "larger" set. For example, $\mathbb {Z} \subset \mathbb {R}$, and all integers have an equivalent real number. In Haskell types, this relationship is only partially preserved: 5 :: Integer has an equivalent 5 :: Float, but 9876543210987654321 :: Integer does not have a corresponding value of type Float (since Float does not represent all real numbers).

The $^{+}$ indicates types that include values (such as "infinity" and "negative zero") in addition to those in the corresponding sets.

A blank in the Module column means the type is exported by Prelude.

Some of the numeric types (Ratio and Complex) are parametized types, i.e. you can't create a value of type Complex, but you can create a value of type Complex Float, Complex Double, etc.

There are some type-specific functions, for example numerator, which returns the numerator of a Ratio.

There are many more numeric types than listed in the table above, and the set of numeric types can be extended:

• you can create your own―something we will do later in this page; and
• you can search Hoogle for other libraries that provide types such as matrices, polynomials, etc.

Exercises

Consider which types would be appropriate to use for: an interior design website that stores measurements of room and furniture sizes calculating large prime numbers recording bank transactions and balances calculating a checksum of an ASCII file (based on summing all of the 8-bit ASCII codes and discarding any overflow) returning the length of the hypotenuse of a right angled triangle, given the lengths of the other two sides Write functions (including type signatures, and using only the (*) multiplication operator defined in the Num class) that: takes a number parameter of type Integer and returns the square of the number takes a number parameter of type Rational and returns the square of the number Write a function to calculate the area of a triangle given the length of two sides and the angle between them in radians. Use the formula $area={\tfrac {1}{2}}ab\sin {x}$. It should work for suitable value/result types, and to the maximum precision possible. Include the type signature. Use iterate to create a (constant) variable halvings whose value is a list containing the geometric sequence $[{\tfrac {1}{2}},{\tfrac {1}{4}},{\tfrac {1}{8}},...]$. Include the type signature. (To check the value, remember to do e.g. take 10 halvings!) You are disappointed that Haskell's floating point numbers are only approximations, and thinking of writing your own "unlimited precision" floating-point type. You start with data Unlim = Unlim Integer Integer, so that Unlim x y represents the value $x\times 10^{y}$. Is this a worthwhile thing to do? If not, what would be better?

What Numeric Means (The Num Class)

By "numeric", we mean that the types support some basic maths such as addition and multiplication. In Haskell, these basic maths operations are defined in the Num class. The types listed above all are instances of Num, and each provides an appropriate implementation for them.

Note the type of the addition operator:

GHCi> :t (+)
(+) :: Num a => a -> a -> a

As explained previously, this type signature shows that (+) is a function that takes two parameters (of the same type), and returns a value (of that same type). But the type can't be any of type (it can't be a Bool, for example), it has to be a type that's an instance of the class Num. Hence (+) is polymorphic: it can operate on different types (at different times; not in the same expression), subject to the Num constraint. (We will talk about how to calculate the sum of numbers of different types in the section on numeric conversions later.)

GHCi> (123 :: Integer) + (5 :: Integer)
128
GHCi> :t (123 :: Integer) + (5 :: Integer)
(123 :: Integer) + (5 :: Integer) :: Integer

Note

I've explicitly stated the types of both of the numbers in this example for clarity. This is not something you'd normally do (although you may have to or want to occasionally). If I had just typed 123 + 5 how would GHC know which type I meant? It could be any of the types in the table above. We'll see the answer in the sections on numeric literals and defaults later.

If I'd entered 123 + 5 :: Integer this would also imply that 123 and 5 are Integer values. This is because I'm declaring that the result of the (+) should be an Integer, which (by the type signature) would require the type of each of the arguments to be Integer as well. This is a little easier on the eye, and is what I will do in the following examples.

Num also includes functions for multiplication and subtraction (and some more; we will see the details later). It does not provide division. There are additional numeric classes that provide functions that are only suitable for a subset of the numeric types, for example:

• sin, which returns the sine of an angle, where it doesn't make sense to return any of the integral types; and
• (/) and div, which do different types of division suitable for different types of number.

Num also includes the function fromInteger, which creates a value of any numeric type from an integer (e.g. fromInteger 5 :: Complex Float gives 5.0 :+ 0.0). This is one of a number of type conversion functions discussed in more detail later. It is also used by the Haskell when compiling a numeric literal.

All of the numeric types above are instances of Eq, though this should be used with care with types representing approximations (e.g. Float). Many are also instances of other standard classes (Ord, Enum and Bounded), but there are nuances in their behaviour.

Exercises
Which types do you expect to be instances of Ord, Enum and Bounded? What do you think the difference between is between (/) and div. Which types support which? Generalise the "square" functions from the previous exercises, to a single function that works with value of any suitable numeric types. Include the type signature.

Comparison of Types

Accuracy and Precision

Some of these types (e.g. Integer) offer complete accuracy. You can multiply two 50-digit Integer values together and get a mathematically exact 100-digit result. Rational is also completely accurate.

Some of the types (e.g. Int8, Ratio Int) are completely accurate, provided the numbers stay within the range supported by the type. (Note that operations that cause overflow typically don't raise exceptions).

Some types (e.g. Float and Double) are used for recording approximations. Double offers greater precision that Float, but neither can represent the exact value of $\pi$, for example. They also suffer from rounding errors, e.g:

> 0.12 + 0.03 :: Float
0.14999999
> 0.12 + 0.03 == (1.15 :: Float)
False

As a result, for approximation types:

• it probably makes sense to round values as required prior to display to a user (i.e. don't use the result of show); and
• it probably doesn't make sense to compare them for equality.

Exercises

Write a function binaryParts, so that binaryParts x returns the subset of elements of halvings that sum to x. It need only work for Rational numbers greater than zero and less than one. E.g. binaryParts (11 % 16) should give [1 % 2,1 % 8,1 % 16]. (Hint: binaryParts x could use a recursive helper function that takes a list of (remaining) halvings to consider including, and a remaining value i.e. x less any halvings that we want to include in the result.) take 50 $ binaryParts (1 % 10) illustrates nicely why we get rounding errors using binary numbers for representations of decimal fractions.

Overflow

In general, mathematical operations in Haskell do not raise overflow exceptions. The actual behaviour differs amongst the types.

TODO: Fix the statements about modulo behaviour for integral types since they may not be correct. The Haskell report says the overflow behaviour is undefined, and it is possible that it is different in different implementations (e.g. on LLVM).

For bounded integral types, values "wrap" (i.e. the arithmetic is performed modulo 2ⁿ, where n is the number of bits in the type):

> 127 + 1 :: Int8
-128

If overflow is likely, you should consider the options, for example:

• use a different type (e.g. Integer instead of Int, where overflow is not possible); or
• if a different type is not possible (e.g. it's an integer that needs to be stored in some fixed size field in a database), maybe use a numeric type from a library that does raise exceptions on overflow (or use e.g. Integer but do validation prior to trying to store the result); or
• be happy that it's what you wanted (e.g. for calculating a checksum of a file).

Note that succ does raise an exception for a bounded integral type when exceeding a bound:

> succ 127 :: Int8
*** Exception: Enum.succ{Int8}: tried to take `succ' of maxBound

Natural can raise an exception during subtraction:

> 4 - 7 :: Natural
*** Exception: arithmetic underflow

When floating point types overflow, they take the value Infinity:

> 1.0e23 * 1.0e23 :: Float
Infinity

Exercises
Write a function w8Add :: Word8 -> Word8 -> (Bool, Word8) that adds the two parameters together, but also returns a flag indicating if overflow occurred. Write a function w8AddErr :: Word8 -> Word8 -> Word8 that adds the two parameters together, but gives an error on overflow. Write a similar functions for values of type Int8.

Division by Zero

Division by zero will raise an exception for some types, but for Float and Double, a value Infinity is returned:

> 6 / 0 :: Rational
*** Exception: Ratio has zero denominator
> 6 `div` 0 :: Integer
*** Exception: divide by zero
> 6 / 0 :: Float
Infinity

However, it is possible to create Rational values with zero denominators by directly using the (:%) constructor or utility functions:

> 5 :% 0 :: Ratio Word8
5 % 0
> infinity
1 % 0
> notANumber
0 % 0

Note that Float and Double also support negative infinity, negative zero, and NaN ("not a number"):

> let pinf = 6 / 0 :: Float
> let pz = 12 / pinf
> let ninf = -6 / 0 :: Float
> let nz = 12 / ninf
> ninf
-Infinity
> pz
0.0
> nz
-0.0
> pz == nz
True
> (nz + 1) - 1
0.0
> pz / pz
NaN
> pinf / pinf
NaN

They will also return NaN for e.g. sqrt (-1).

They support functions isInfinite and isNaN so you can check for potential errors.

Exercises
Write function isValidFloat. Write assertValidFloat, using assert from Control.Exception.

Enumerations

Many of the numeric types are instances of Enum, including fractional types. The Enum class includes methods toEnum and fromEnum for converting between values of the type and values of the (bounded) type Int. Most types (including most numeric types) will not have a 1:1 mapping with Int, leading to some interesting behaviour.

There is no requirement that toEnum n represents the numeric value n, though this is the case for many types:

> toEnum 127 :: Int8
127
> toEnum 127 :: Float
127.0
> toEnum 127 :: Centi
1.27

In some cases where n is out of bounds, fromIntegral n will cause "wrapping" but toEnum n will raise an exception:

> fromIntegral 128 :: Int8
-128
> toEnum 128 :: Int8
*** Exception: Enum.toEnum{Int8}: tag (128) is outside of bounds (-128,127)

fromEnum will have corresponding behaviour, and in some cases it truncates fractional parts:

> fromEnum (3.1415927 :: Float)
3
> fromEnum (22 % 7 :: Ratio Int)
3
> fromEnum (1.27 :: Centi)
127

Where the result is out of bounds for an Int, typically "wrapping" will occur without raising exceptions:

> fromEnum (2158269056624017538838 :: Integer)
-234
> fromEnum (3.1415927e22 :: Float)
1121396307215253504

succ and pred are consistent with the above. In many cases, succ has the same effect as adding 1 (but not for Deci etc). As mentioned above, succ may raise an exception when exceeding the bounds of a type. For some types succ will work correctly even though fromEnum "wraps":

> succ 2158269056624017538838 :: Integer
2158269056624017538839

For imprecise floating-point types, succ will make no difference to large values due to lost precision:

> succ 1.0e23 :: Float
1.0e23

Enum also includes methods enumFrom and variations. Haskell compiles [x..], [x,y..z], etc, into these.

Exercises

Write floatSuccLim :: Float that determines the greatest value of x such that succ x is equal to x + 1. (Hint: do a binary search between 0 and 1.0e23). How many variations on enumFrom do you expect to exist? What do you expect the evaluation of these to be: [1 .. 5] :: [Int8] [120 ..] :: [Int8] [120 ..] :: [Integer] [1 .. 5] :: [Float] [1.1 .. 5] :: [Float] [1, 1.1 .. 5] :: [Float] [1 .. 5] :: [Deci] Write a function enumerate :: (Enum a, Bounded a) => [a] that returns a list of all elements in a bounded enumeration. Does pred (succ x) always equal x? Does toEnum (fromEnum x) always equal x?

Internal Representation

Most numeric types provide functions that give access to their internal representations.

Some numeric types are made of separate components, for example Rational has two Integer components, and Complex Double has two Double components. Both types have functions e.g. numerator or realPart, that access these.

Complex exposes its infix constructor :+, which can be used for creating complex numbers, pattern matching, etc. Ratio does not expose its constructor (it's :%, hidden in GHC.Real). % is not a constructor, it's an operator that first reduces the ratio (e.g. ${\tfrac {3}{12}}$ to ${\tfrac {1}{4}}$) and then creates the Ratio. In addition, the show method displays %.

The bits representation of integers can be accessed via Data.Bits module, for example:

> finiteBitSize (0 :: Word8)
8
> bit 4 .|. bit 1 :: Word8
18
> countLeadingZeros (18 :: Word8)
3
> shift 18 1
36

There are also functions such as decodeFloat for accessing details of floating point numbers.

Exercises
write w8MultErr :: Word8 -> Word8 -> Word8 which returns the product of its two parameters, but gives an error if the result will overflow. Use countLeadingZeros on the two parameters to determine if overflow will occur. Look at decodeFloat for your result from floatSuccLim. How can succ work for this value?

Type Classes

As stated above, most standard numeric operations are defined as class methods, so that they can be applied to all appropriate types. The numeric type classes in Prelude are:

Class	Example Methods	Means	Doesn't mean
Num	(+), (*)	any numeric type (i.e. supporting basic mathematical operations)	A type that can only represent "numbers". For example, a type representing a matrix might be an instance
Fractional	(/), recip	a type that includes non-integral values	a type that can only be represented as a fraction (i.e. a rational number). For example, a type that could represent $\pi$ might be an instance
Floating	pi, sin	a Fractional type that approximates a numeric value to a certain precision	Only real numbers. For example, Complex Float is an instance.
Real		a type representing (a subset of) real (i.e. not complex) numbers. Real types must also be instances of Ord	a type that can represent any real number. (Most instances can't represent $\pi$)
RealFrac	round, floor	a type that's both Real and Fractional
RealFloat	isInfinite	a type that's both Real and Floating
Integral	div	a Real type that can represent only integer values. Integral types must also be instances of Enum	a type that can represent any integer value (many Integral types can only represent a certain range of integers)

The classes form a hierarchy (shown here), so that a type can't be an instance of, say Real if it's not also an instance of Num.

Exercises

Look at the numeric types listed above. What classes would you expect them to be instances of? Generalise the "triangle area" functions from exercises above, so that it works with any suitable numeric types. Include the type signature. Generalise the isValidFloat and assertValidFloat functions to appropriate class(es). If you build the following types, what classes would you make them instances of: a type that does arithmetic modulo 12 (so that e.g. 8 + 7 = 3) a type that represents Gaussian integers Is it possible to create a type that can represent $\pi$? What classes might it be an instance of? What other values should it be able to represent? Would it be of any use? Can any types be instances of both Integral and Fractional?

Numeric Conversions

Introduction

Suppose we want a function that can add any Integer value to $\pi$. Let's try:

nPlusPi :: Integer -> Float
nPlusPi n = n + pi

Oops - we get an error: Error: Couldn't match expected type ‘Float’ with actual type ‘Integer’. This makes sense: the definition of (+) requires both types to be the same.

How do we fix this? Using the fromInteger method on the Num class:

nPlusPi :: Integer -> Float
nPlusPi n = fromInteger n + pi

fromInteger is one of a number of numeric conversion functions that we'll look at.

However, before looking at them, note that there aren't separate floatFromInteger, doubleFromInteger, rationalFromInteger, etc, functions. Instead, fromInteger is a method on the class Num, and each instance provides its own implementation. When fromInteger is called, the function that calls it needs to be clear which type should be returned. In the above example, the required type was determined by type inference, based on the types of nPlusPi and (+).

Note

Many other languages allow addition of mixed numeric types, and will "quietly" convert them so that they can be added together. This can make it easier to write some code, but can also lead to subtle run-time errors.

Exercises
Generalise nPlusPi to return any suitable type. How does it know what type to return?

More Integral Conversions

Conversions between Haskell numeric types

The diagram on the right shows fromInteger in a class hierarchy diagram, along with a number of other conversion functions. It is a method on the Num class, so can create a value of any numeric type from a Integer value.

Another method shown is toInteger. This is a method on the Integral class, so any Integral type (e.g. Int, Word8, and even Integer itself) provides a method to create an Integer with the equivalent numeric value. Prelude also includes a function fromIntegral that combines toInteger and fromInteger, making it easy to convert from any Integral type to any numeric type.

Exercises
Generalise nPlusPi further, so that the parameter is of any integral type. Evaluating toInteger on an Integer value just returns the same value. Is this of any use?

Fractional Conversions

Two class methods support the majority of fractional conversions:

fromRational :: Fractional a => Rational -> a
toRational :: Real a => a -> Rational

fromRational is a method of the Fractional class, so it's possible to create a Fractional of any type from a Rational. As with fromInteger, the function that calls fromRational needs to be clear what type should be returned.

Just as with nPlusPi, we have a type problem if we try to write this:

xPlusApproxPi :: Float -> Rational
xPlusApproxPi x = x + 22%7

since we're trying to add a Float to a Rational.

toRational is a method of the Real class, so will work for e.g. Int, Integer, Float, etc, and even on Rational itself. Each type instance will define its own implementation, and is expected to return "the rational equivalent of its real argument with full precision". For approximate types (e.g. Float) the result should therefore be an exact equivalent of the approximate value.

There is also the function realToFrac, that is a combination of toRational and fromRational, which can convert any instance of Real to any instance of Fractional.

Note that, with Float and Double, toRational loses the negative of negative zeros and "rounds" infinities to large fractions. This impacts how realToFrac handles conversions between them. The functions floatToDouble and doubleToFloat in GHC.Float avoid these problems:

> realToFrac (-0.0 :: Float) :: Double
0.0
> float2Double (-0.0)
-0.0
> realToFrac (5 / 0 :: Float) :: Double
3.402823669209385e38
> float2Double (5 / 0)
Infinity

Exercises

fix xPlusApproxPi generalise xPlusApproxPi to all appropriate types. Dividing monetary amounts can be tricky. E.g. 4 / 3 :: Centi gives 1.33, with no indication of the lost penny (1.33 * 3 = 3.99). Write a function that, given 4 (of type Centi) and 3 will return both 1.33 and 0.01. Include the type signature. How does the function compare to divMod? Does it give sensible results for other types? Write a function sigDigs that takes a value of some numeric type and returns a value of the same type but rounded to a required number of significant digits. (e.g., to 3 significant digits, 56789 is 56800, 1.234566 is 1.23 and 99.99 is 100). What types should it work with? (Hint: you may want to use: log base 10 to determine the number of digits to the left of the decimal point, multiplication/division by 10 to "shift" the digits to the left or right, and round.) What's the maximum number of significant figures sigDigs can return? Modify it to give an error if a greater (or negative) number is requested. (Hint: floatDigits and floatRadix might be useful.)

Rounding

toInteger (and hence fromIntegral) will not work on, say, pi, since there is no way to return a value equivalent to pi as an Integer. However, there are functions such as round, ceiling, etc. These are methods on the RealFrac class that will return a value of any Integral type:

floor :: (RealFrac a, Integral b) => a -> b
ceiling :: (RealFrac a, Integral b) => a -> b

Since there's no integer that's a numeric equivalent of pi, these functions give different options for the conversion:

> floor pi
3
> ceiling pi
4

RealFrac also provides the method properFraction, which decomposes a number into an integral and fractional parts, e.g:

> properFraction pi
(3,0.14159265358979312)
> properFraction (22%7)
(3,1 % 7)

length, etc, and generic versions

Prelude includes functions such as length and take that return or take values only of type Int. You may think "well, I'd never need to use a huge number such as available in Integer, so Int is good enough." But remember there are other Integral types as well, such as Word8, etc, and it might sometimes be useful to get/give those as parameters.

Hence the module Data.List also exports "generic" versions of the functions:

genericLength :: Num i => [a] -> i
genericTake :: Integral i => i -> [a] -> [a]

Note that genericLength can return any Num, although it will always return a value equivalent to an integer (e.g. 12.0 :: Float).

Exercises
Write average, which takes a list of numbers and returns the average value of them.

Converting to/from Strings

There are a number of functions for converting numbers between numbers and strings. show and read are some, but they only provide limited behaviour and may well not be adequate for many purposes.

Some other functions include showIntAtBase (which can show an integer value in any base), and showEFloat (which has an option to specify the number of decimal places). These functions return a type ShowS, which makes them more efficient when building large strings.

> showIntAtBase 3 intToDigit 11 ""
"102"
showFFloat (Just 2) (pi*10000) ""
"31415.93"

There is also the function printf in the Text.Printf module which can make it easier to embed formatted numbers within longer strings, for example:

> printf "The values are %s, %d and %.4f.\n" "hello" 123 pi
The values are hello, 123 and 3.1416.

Beware that printf can't check that the parameter types against the format string at compile time, and will raise a run-time exception if they mismatch.

Exercises

The sigDigs exercise above was (hopefully) interesting in that it used a number of numeric conversions. Chances are, though, you'd only want to round to a number of significant digits when formatting a number for display to a user. So write showSigDigs, for suitable types, that returns a ShowS. Use floatToDigits. (Hint: first write a version that truncates to n significant digits, so showSigDigs 3 99.99 "" gives "99.9", then modify it to add the rounding logic as a second step).

Expression Syntax

Operators, Sections

Many mathematical functions are operators, which are often written in infix notation, e.g. 18/4, but can be written prefix, e.g. (/) 18 4. Non-operator functions are often written in prefix, e.g. div 18 4, but can be written infix, e.g. 18 `div` 4.

Operators can be used in sections, e.g. map (/4) [18, 20, 22], which is equal to [18/4, 20/4, 22/4], and map (4/) [18, 20, 22], which is equal to [4/18, 4/20, 4/22]. Functions written in infix can also be used as sections, e.g. map (`div` 4) [18, 20, 22] or map (400 `div`) [18, 20, 22].

Exercises
What do each of the following produce: map (/ 10) [10, 20] map (10 /) [10, 20] map ((/) 10) [10, 20] map (10 (/)) [10, 20] What do each of the following produce: map (`mod` 10) [5, 6, 7] map (10 `mod`) [5, 6, 7] map (mod 10) [5, 6, 7] map (10 mod) [5, 6, 7] map (flip mod 10) [5, 6, 7] What does the code map ((*2).(+1)) [10, 20] produce?

Fixity, Precedence

What is meant by the mathematical expression 5 + 3² × 4? There is a convention that we apply the operations in a certain order, like this: 5 + 3² × 4 = 5 + 9 × 4 = 5 + 36 = 41. The convention says that the exponentiation (raising to a power) operator has a higher precedence than multiplication, which in turn has a higher precedence than addition. If we wanted to add the 5 and 3 together first, we'd indicate it using brackets: (5 + 3)² × 4 = 8² × 4 = 64 × 4 = 256.

What about the expression 7 − 3 − 2? The convention is that subtraction associates to the left, like this: 7 − 3 − 2 = 4 − 2 = 2. . If we wanted the 3 − 2 to happen first, we'd also need to indicate it using brackets: 7 − (3 − 2) = 7 − 1 = 6.

Haskell is aware of the conventions and the use of brackets:

> 5 + 3 ^ 2 * 4
41
> (5 + 3) ^ 2 * 4
256
> 7 - 3 - 2
2
> 7 - (3 - 2)
6

In a Haskell program, the precedence and associativity of operators can be specified using "fixity" declarations. For example, (-) and (^) have these declarations:

infixl 6 -
infixr 8 ^

This shows that (^) has a higher precedence than (-), that (-) associates to the left and that (^) associates to the right. The standard mathematical operators follow the standard conventions, and are part of a precedence hierarchy that includes other operators, as shown here.

Fixity declarations can also be given for functions, and are used when those functions are written in infix style, e.g.:

infixl 7 `div`

Hence 3 + 50 `div` 3 `div` 2 means the same as 3 + ((50 `div` 3) `div` 2).

Note that prefix function application has the highest precedence, so succ 3 * 4 means (succ 3) * 4, not succ (3 * 4).

Exercises
Write an operator (**/), so that x **/ y gives the yth root of x. Include type and fixity declarations. Write an operator (~|), so that x ~| y returns True if and only if x divides y. Include type and fixity declarations.

- (negate) infix and prefix

The - operator can be used normally as an infix operator. However, uniquely, it can also be used as an (unbracketed) prefix operator, where it has the same meaning as negate. This can be very useful, but can also be a bit confusing at times.

These expressions are OK, and - has the two-parameter subtraction meaning:

• 8 - 5 (normal infix operator, giving 3)
• (-) 8 5 (normal prefix operator, giving 3)
• map (3 -) [1,2] (normal section, means [3-1,3-2]).
• 2 * 3 - 5 (means (2 * 3) - 5)
• 2 == 3 - 5 (means 2 == (3 - 5))

These expressions are OK, and - has the one-parameter negate meaning:

• 8 == - 3 (means 8 == (negate 3), since - has a higher precedence than ==)
• 8 + (- 3) (means 8 + (negate 3))
• - 2 ^ 2 (means negate (2 ^ 2)).
• - 2 == 2 (means (negate 2) == 2).
• succ (- 3) (means succ (negate 3))
• -(5 + 3) (means negate (5 + 3))

These are not OK:

• 8 * - 3 and 8 + - 3. These don't compile, since the negate operator has lower (or the same) precedence as the other operator.
• succ - 3. This means (succ negate) 3, since function application has highest precedence, which doesn't compile.
• map (- 3) [8,9]. Due the the special - prefix operator, (- 3) is not treated as a section. Instead it's interpreted as negate 3, which is not a function (and so can't be passed to map). However, you can use the subtract function instead: map (subtract 3) [8,9] which gives [5,6].

Note that removing spaces makes no difference. For example 8 * -3 fails in exactly the same way as 8 * - 3, despite it being "obvious to everyone that it should mean 8 * (-3)".

You may want to put brackets around any usage of - as a prefix operator for clarity. (And your own sanity).

Numeric Literals

Integer Literals

Suppose we want to define a Float variable with the value $1+\pi$. We can do this:

onePlusPi :: Float
onePlusPi = 1 + pi

OK, it only gives an approximation, but it's otherwise brilliant:

> onePlusPi
4.141593

But how does this work? Why don't we get a type error? onePlusPi is defined to return a Float. So (+) must return a Float. So each of the parameters to (+) must be a Float. pi is defined so it can be a value of any instance of Fractional, one of which is Float, so it's happy. 1 however looks like an integer, which is not a Float, so how does that work?

The answer is that the 1 actually compiles to fromInteger 1, so onePlusPi is essentially:

onePlusPi = fromInteger 1 + pi

fromInteger is has type signature:

fromInteger :: Num a => Integer -> a

which can create a value of any numeric type we want. And right now we want a Float (so we can add it to another Float giving a Float), so that's what we get.

We can see the effect of the usage of fromInteger here:

> :t fromInteger
fromInteger :: Num a => Integer -> a
> :t fromInteger 1
fromInteger 1 :: Num a => a
> :t 1
1 :: Num p => p

So now we see why a simple number (e.g. 1) has the weird type (Num p => p): because it can be any type of number you want it to be.

If you do the Mod3 exercise below, you should have created a fromInteger implementation for Mod3, so can do:

> 2 :: Mod3
Two

Note that just because Haskell can interpret a numeric literal in code, doesn't mean read will interpret it in the same way (or at all):

> read "2" :: Mod3
*** Exception: Prelude.read: no parse

Although it can if you also implement a Read instance.

Fractional Literals

Numeric literals containing decimal points or the e symbol are compiled using fromRational, so you can write:

halfPlusApproxPi :: Rational
halfPlusApproxPi = 0.5 + 22%7

where 0.5 "looks like" a floating-point number, but means effectively:

halfPlusApproxPi = fromRational (1%2) + 22%7

where the decimal number 0.5 has been converted to ${\tfrac {1}{2}}$ and wrapped with fromRational. We can see the effect of fromRational here:

> :t fromRational
fromRational :: Fractional a => Rational -> a
> :t fromRational 0.5
fromRational 0.5 :: Fractional a => a
> :t 0.5
0.5 :: Fractional p => p
> 0.5 :: Rational
1 % 2
> 0.5 :: Float
0.5
> 0.5 :: Complex Float
0.5 :+ 0.0

Note that to be a fractional literal, digits are needed both before and after the decimal point. (i.e. 0.5 not .5).

Literals in exponent form are compiled using fromRational, even if they don't contain a decimal point, and even if they are integer values:

> :t 1.22583e3
1.22583e3 :: Fractional p => p
> :t 1e3
1e3 :: Fractional p => p
> 1e3 :: Float
1000.0
> 1e3 :: Int
error: No instance for (Fractional Int) arising from ...

GHC has a language extension NumDecimals that allows can allows 1e3 :: Int.

Negative Literals

A "negative literal" compiles to an application of the prefix - operator. Hence -7 is equivalent to negate (fromInteger 7), and -0.5 is equivalent to negate (fromRational (1%2)).

In some cases, brackets may be needed due to operator precedence. For example 4 + -3 doesn't compile, but 4 == -3 does. 4 + (-3) and -3 + 4 also compile correctly.

GHC has a language extension NegativeLiterals that changes the interpretation, so that -7 is equivalent to fromInteger (-7).

Pattern Matching

Pattern matching on literals (numeric, character or string) compiles into a use of (==), so also depends on the numeric type being an instance of Eq. E.g:

isZero :: Integer -> Bool
isZero 0 = True
isZero _ = False

compiles to:

isZero :: Integer -> Bool
isZero x | x == fromInteger 0 = True
         | otherwise          = False

Note that the following compiles without warning, but will never return 2:

f :: Float -> Int
f (-0) = 1
f   0  = 2
f   _  = 3

Exercises
Why doesn't f work as expected? Write a version that does.

Non-Decimal literals

It is also possible to type integer literals in octal or hexadecimal:

> 0o77
63
> 0xFF
255
> 0xff
255

which are also all compiled using fromInteger.

Fractional literals must be in decimal, but GHC has a language extension HexFloatLiterals that also allows them in hexadecimal. 0x0.1 is then the same as 1/16.

Defaults

Type Ambiguity

In some cases there is ambiguity in the type of an expression. In many cases, ambiguous expressions will not compile, for example:

e0 = toEnum 0

without the type signature is an error. You could want a Bool, an Ordering, an Integer, but how does the compiler know?

To fix this, you can specify the type (ideally give e0 a type signature), or add an expression that uses e0 and requires it to be a specify type, e.g:

e1 = e0 == True

This expression would fix e0 to have type Bool. (Alternatively I could write e.g. e2 = e0 == GT, which would require e0 to have type Ordering. But I can't have both expressions, since e0 can only have one type.)

In some cases, it's not possible to fix ambiguity using a top-level type signature. For example:

e3 :: Bool
e3 = toEnum 4 > toEnum 3

Here I've given e3 a type signature, but it's still ambiguous what types toEnum should create. Here's one way to fix it:

e3 :: Bool
e3 = (toEnum 4 :: Word8) > toEnum 3

These examples above are fairly contrived to make a point. But the problem does often arise, especially with numeric types. For example:

evenish :: Float -> Bool
evenish = even . round

which takes a Float, and returns True if it's closer to an even number than an odd number.

Note the types:

round :: (RealFrac a, Integral b) => a -> b
even :: Integral a => a -> Bool

Hence round can produce any Integral type and even can consume any Integral type. How is the compiler meant to know which of the many Integral types to use? And why don't we get a type ambiguity error? The answer is defaults.

default

Each module (file) can have a default code declaration, and if it's omitted it's assumed to be:

default (Integer, Double)

The details of exactly how it works are specified in the Haskell Report, but essentially means that instead of giving an error for some ambiguous types, it will use one of the defaults if possible. It will use Integer for ambiguous Integral types and Double for ambiguous Fractional types. Hence evenish will compile so that round will produce, and even will consume, a value of type Integer.

If you turn on e.g. {-# OPTIONS -Wall #-}, which I often do, you will get a warning when type defaulting occurs.

You can change the defaulting rules by adding your own default statement to the .hs file. You can even disable it by stating default (), in which case evenish would give an error.

Exercises

Disable defaults, and change evenish so that it compiles. Generalise evenish as much as possible. Write a function getPythag :: Integer -> Integer -> Maybe Integer. getPythag x y should returns the integer z, if one exists, so that $x^{2}+y^{2}=z^{2}$ (i.e. they are a Pythagorean triple. (Hint: use ${\sqrt {x^{2}+y^{2}}}$ to get a potential z). Does your code depend on defaulting? Change getPythag so that it doesn't depend on defaults. Your solution to getPythag may work not work for all Pythagorean triples. For example, getPythag 246913577 30483157253467464 should return Just 30483157253467465, but does it? Why not? How could you fix it?

Note that fromInteger (hence also fromIntegral) and fromRational (hence also realToFrac) are often subject to defaulting, since (by design) they can return a value of any one of a number of types. As a result, numeric literals (which compile using fromInteger or fromRational) are also often subject to defaulting.

default in GHCi

It is a little curious that, when you enter e.g. 125 + 10 into GHCi, it replies with 135. Observe:

> 125 + 10
135
> it :: Int8
-121
> :t it
it :: Num a => a

We can see that GHCi is being as helpful as possible. It does the sum initially using the default type (Integer) because we didn't tell it otherwise (and displaying 135 is probably more helpful than displaying a type ambiguity error). If, however, we specify a type, it will do the calculation using the requested type, which in this case results in a different value.

Also, when we ask it to tell us the type of an expression, it will do so without regard to any defaulting that might occur upon evaluation.

We can turn off defaulting in GHCi as in .hs files:

> default ()
> 125
error: Ambiguous type variable...

In standard Haskell 2010, defaulting (and the default statement) only applies to numeric types. GHC (since 6.8.1) supports a language extension ExtendedDefaultRules that allows defaulting of additional types. You can enable this in .hs files, but it is initially enabled when you start GHCi:

> toEnum 0
()

where the type has defaulted to (the type) ().

You can modify this behaviour by turning off ExtendedDefaultRules:

> :unset -XExtendedDefaultRules
> toEnum 0
Error: Ambiguous type variable...

Mathematical Operations

Most mathematical operations in Haskell attempt to mirror "true" mathematical operations. However, none of the operations match perfectly due to overflow, rounding, etc, with different behaviours for different types. In addition, the standard types Double and Float represent real numerical values (within some range and only to certain precision), but also include representations of positive and negative infinities and negative zero.

This section compares Haskell mathematical operators and "true" maths.

TODO: Add something on benefit of Infinities, e.g. in f x = 3 - 2 / (4 + 3 / (x - 3))

Arithmetic Operations

Addition, Subtraction and Multiplication

(+), (binary) (-) and (*) follow the mathematical operations of addition, multiplication and subtraction, subject to overflow and rounding. These operations are defined as methods of the Num class, and are available for all numeric types. However, they are not closed for all types, for example (-) is not closed for the Natural type.

negate determines the additive inverse, where there is one.

Negative zeros and infinities behave "reasonably", for example:

> negate 0.0
-0.0
> 0.0 == -0.0
True
> 5.0 + (-0.0)
5.0
> let inf = fromRational infinity
> inf + inf
Infinity
> inf - inf
NaN

From a Haskell syntax perspective, (-) can be used as a prefix operator to represent negate (and so can't be used as a section with the operator on the left). There is a function subtract, where subtract 2 5 means "subtract 2 from 5", which can be used instead.

Division

Mathematically, integers are not not closed under division, but other numbers (rational, real, complex) are. Accordingly, Haskell splits division between two classes:

• Integral, which defines methods div and mod (and the combined divMod) for performing division with remainder (i.e. given integers $a$ and $b$, find integers $q$ and $r$ such that $a=bq+r$ and $0\leq r<|b|$).
• Fractional, which defines method (/) for performing division without remainder (i.e. given $a$ and $b$, find $q$ such that $a=bq$). It also provides recip for finding the multiplicative inverse.

Integral provides two sets of "division with remainder" functions, illustrated here when dividing -11 by 4:

round	$q$ function	$r$ function	combined function	example $q$	example $r$
towards negative infinity	div	mod	divMod	-3	1
towards zero	quot	rem	quotRem	-2	-3

In mathematics there is no ability to divide by zero. In Haskell, division by zero is treated differently for different types:

> 5 `div` 0
*** Exception: divide by zero
> 5 / 0
Infinity

However, note that these behaviours are not stated requirements of the (/) or div class methods. It would be possible for some Integral types (hand-written, or from other libraries) to return values, or for some Fractional types to raise exceptions.

Exponentiation

Interestingly, Haskell has four different functions corresponding to exponentiation ("raising to a power"):

(^) :: (Integral b, Num a) => a -> b -> a
(^^) :: (Fractional a, Integral b) => a -> b -> a
(**) :: Floating a => a -> a -> a
exp :: Floating a => a -> a

Exercises
Try to determine the behaviour of these three functions from their type signatures. Are all four really needed? Two of these are class methods (defined in a class declaration). Which ones and why? If the others aren't class methods, what are they?

scaleFloat can also be used for floating-point types. scaleFloat n x gives $x.r^{n}$ where r is the floatRadix (often 2) of x.

odd, even, gcd and lcm

These are all functions that operate on Integral types, and call methods defined on the Integral class.

Each integer is either even or odd. even returns a Bool indicating whether the argument is even, and odd returns a Bool indicating whether the argument is odd.

gcd calculates the greatest common divisor of two integers, using the Euclidean algorithm. For example, gcd 12 8 = 4.

lcm uses gcd to calculate the lowest common multiple. For example, lcm 12 8 = 24.

abs and signum

the abs and signum of a complex number

abs x determines the absolute value of x, often written $\vert x\vert$. signum x determines the sign of x.

Both operations are are methods of the Num class and are available for all numeric types. The two functions adhere to the law that, for any number x, abs x * signum x$\equiv x$. For all standard numeric types, signum returns a value of "magnitude" 0 or 1, but this is not a general requirement.

For any real number x: abs x$\equiv x$ if $x\geq 0$ and abs x$\equiv -x$ if $x<0$; and signum x is 1, 0 or -1. For types that support negative zero, signum (-0.0) gives -0.0.

For a (non-zero) complex number x: signum x is a complex number with magnitude 1 and the same phase as x; and abs x is a the magnitude of x (as a complex number with imaginary part of 0). Hence if $x=re^{i\theta }$, then signum x$\equiv e^{i\theta }$ and abs x$\equiv r+0i$

Exercises
You are coding a type representing Gaussian integers. Implement suitable abs and signum methods for it.

Irrational and Transcendental Functions

These functions all operate on instances of the Floating type, on either real or (with the exception of atan2) complex numbers. There are a number of subtleties around their use:

• precision: these functions produce only approximations to the mathematical results. For example, mathematically $\sin(-\pi )=0$, but GHC calculates sin (-pi) to be 8.742278e-8.
• principle values: mathematically, some "functions", especially "inverse" functions, are multivalued. For example, $x\to x^{2}$ maps both $2$ and $-2$ to $4$. The inverse function $x\to \pm {\sqrt {x}}$ maps $4$ to both $2$ and $-2$. Similarly $x\to \cos x$, which is periodic, maps $0$, $2\pi$ and $4\pi$ (and infinitely many other values) to $1$. The inverse function maps $1$ back to those infinitely many values. Sometimes only a single result is desired and, by convention, the notation ${\sqrt {x}}$ usually means only the positive value. Depending on context, $\arccos x$ may also refer to only a single principle value. The Haskell functions sqrt and acos only return a principle value for any given input: sqrt 4 gives 2.0 and acos 1 gives 0.0. These principle values are somewhat (but no universally) standardised. In some cases, for example $x\to \log _{e}x$ (the inverse of $x\to e^{x}$), there is only a single result within the real numbers but multiple results (and hence defined principle values) within the complex numbers.
• limited domains: mathematically, some functions are undefined for some values, for example $\log _{e}0$ is undefined. Float or Double results are set to the IEEE values of NaN, Infinity or -Infinity in these cases. For example, log 0 gives -Infinity. In some cases a function may be undefined for some value when the results are restricted to real numbers, but defined when complex numbers are allowed. For example, there is no ${\sqrt {-1}}$ within the real numbers, but there is within the complex numbers. sqrt (-1) gives NaN, but sqrt ((-1) :+ 0) gives 0.0 :+ 1.0. In some cases there is a valid real result but none is returned. For example, $(-2)^{3}=-8$, but (-8) ** (1/3) gives NaN.
• discontinuities and branch cuts: some functions are discontinuous at some points. A small change in the input can result is an extreme change in the output. For example $x\to \tan x$ is discontinuous (and undefined) at $\pi /2$. tan (pi/2-0.00001) gives 100302.22 but tan (pi/2+0.00001) gives -99430.34. When complex numbers are considered, the discontinuities run along lines (often the axes), and are called branch cuts. The locations of these branch cuts depend on the principle values chosen for the functions, as explained below.
• negative zeros: Float and Double also support negative zeros. Most arithmetic functions don't distinguish between 0.0 and -0.0, but some of the irrational and transcendental functions do. For example atan2 0 (-1) gives 3.1415927 but atan2 (-0) (-1) gives -3.1415927. For complex numbers, branch cuts often lie "between" 0.0 and -0.0. For example, log ((-1) :+ 0) gives 0.0 :+ 3.1415927 and log ((-1) :+ (-0)) gives 0.0 :+ (-3.1415927)

In many cases these subtleties are not problematic, but at times can conspire to create erroneous calculations. In particular, direct implementation of formulae that are mathematically equivalent may not yield computations that give the same results.

Exercises
You know that $\sin(-\pi )=0$, and $\sin(\pi /6)=0.5$. Is it possible to write sinPi :: Rational -> Rational, whose parameter expresses a multiple of $\pi$, that doesn't suffer from the rounding errors? Write sqrts :: RealFloat a => a -> [a] and acoss :: RealFloat a => a -> [a] that return all the results for each input. (Feel free to try the Floating versions instead if you'd prefer!)

Principle Values and Branch Cuts

Complex exp and log, principle values and branch cuts

The locations of branch cuts depend on the defined principle values.

For example, consider $z\to e^{z}$, as illustrated on the diagram on the right. The red line highlights points $z$ on a line on the imaginary axis, extending to infinity in both directions. Per Euler's formula, the mapping of points on the red line by $z\to e^{z}$ all lie on the unit circle, illustrated in blue. The point 0 on the red line maps to 1. As we move up the red line from 0, points map to points anti-clockwise around the circle. $(\pi /2)i$ maps to $i$ and $\pi i$ to $-1$. The point $3i$ maps to a point just before $-1$ and $4i$ to a point a little after it. As we move down the red line from 0, points map to points further clockwise from 1. $-(\pi /2)i$ maps to $-i$ and $-\pi i$ maps to $-1$. We can see that both $\pi i$ and $-\pi i$ map to $-1$. Similarly $4i$ and a point at about $-2.28i$ also map to the same place as each other. In fact, the mapping of the red line wraps around the blue circle infinitely many times, so every point on the blue circle has infinitely many points that map to it.

$x\to e^{x}$ maps other vertical lines to other circles centred on the origin. Vertical lines to the left of the red line map to smaller circles, and lines to the right map to larger circles. Points on any one vertical line with imaginary parts at $\pi$ and $-\pi$ map to the same point as each other, on the negative real axis.

Riemann surface log

The inverse mathematical function $z\to \log _{e}z$ is the complex logarithm. Sometimes it is useful to consider it multi-valued, as illustrated on the left. Each point $z$ (except the origin) will map to points vertically aligned in different layers in the diagram. $-1$ maps to $\pi i$ and to $-\pi i$ (and to infinitely many other points). As $z$ travels around a circle, its mappings move around the surface following a helix, and moving up a whole level for each full circuit of the circle. There are no branch cuts.

Sometimes it's more convenient for its range to be restricted so that it has single, principle value. Typically (but not universally), this range is defined as those numbers with imaginary part in the range $(-\pi ,\pi ]$. Then $-1$ maps to only the principle value $\pi i$. The range of $z\to \log _{e}z$ for all the points on the blue circle is illustrated by the green line (excluding the point $-\pi i$), which represents a subset of the points on the original red line. There is a branch cut along the negative real axis: points on it (or just above it) map to points with an imaginary part of (or just less than) $\pi$. Points just below it map to points with an imaginary part just greater than $-\pi$.

The Haskell function exp mirrors the behaviour of $z\to e^{z}$, except for rounding errors. log (for Float and Double) behaves the same as the restricted, single-valued, function $z\to log_{e}z$, but with a slightly different range due to the presence of negative zeros. It maps points with imaginary part 0.0 to points with imaginary part $\pi$ and points with imaginary part -0.0 to points with imaginary part $-\pi$. The branch cut is "between" 0.0 and -0.0 on the imaginary axis:

> log $ (-1) :+ 0
0.0 :+ 3.1415927
> log $ (-1) :+ (-0)
0.0 :+ (-3.1415927)

The range of log is those numbers with imaginary part in the range $[-\pi ,\pi ]$. It is represented by the green line, including the point $-\pi i$.

Both $-1$ (under $z\to log_{e}z$) and (-1) :+ 0 (under log) map to $\pi i$, indicated by the filled-in arrow on the diagram. Only (-1) :+ (-0) maps (under log) to $-\pi i$, indicated by the unfilled arrow.

One consequence of the branch cut is that log is only the inverse of exp for values within the range of log:

> log $ exp $ 0 :+ 3
0.0 :+ 3.0
> log $ exp $ 0 :+ 4
0.0 :+ (-2.2831855)

There is not a single agreed definition for either the principle values or branch cuts, and they may be different for different types, in other languages, in other systems and in different mathematical usage. It would, for example, be possible for a different (e.g. user-defined) type to define the range of log to be those numbers with imaginary part in the range $[-\pi /2,3\pi /2]$, with a branch cut on the negative imaginary axis.

Rounding and Branch Cuts

Sometimes, rounding errors result in values being the "wrong side" of branch cuts. For example:

> log $ exp $ 0 :+ pi :: Complex Float
0.0 :+ (-3.1415927)

0 :+ pi is within the range of log, so we would expect the result to be 0 :+ 3.1415927. The problem is clear if we look at the intermediate result:

> exp $ 0 :+ pi :: Complex Float
(-1.0) :+ (-8.742278e-8)

We can see the value has "overshot" $-1$ by a little bit, taking it to the wrong side of the branch cut. (Mathematically, $e^{\pi i}=-1$. Ideally, exp $ 0 :+ pi would give (-1.0) :+ 0.0, and exp $ 0 :+ (-pi) would give (-1.0) :+ (-0.0)).

In this case, when we use Double, which operates to greater precision, it behaves as expected:

> log $ exp $ 0 :+ pi :: Complex Double
0.0 :+ 3.141592653589793

Unfortunately this problem is sometimes hard to detect and code around. It is also not limited to problems with the inaccuracy of the algorithms for the core functions such as exp. For example, consider f x = 1 - (x+1)/x. Mathematically, this should be negative when x > 0, and tend to zero as x increases. To start with, the function behaves as expected:

> f 10000
-1.00016594e-4
> f 100000
-1.001358e-5

However, there comes a point when the precision of Float means it can't distinguish x+1 and x. At this point, the function stops returning a negative value:

> f 16777214
-1.1920929e-7
> f 16777215
-1.1920929e-7
> f 16777216
0.0

This by itself may not be a big problem. But now consider g x = signum (f x). When x > 0, g x should return -1.0. However, as soon as x reaches the "failure point", it suddenly jumps to 0.0, giving an unexpected discontinuity and an inaccurate result:

> g 16777214
-1.0
> g 16777215
-1.0
> g 16777216
0.0

A similar problem can occur with branch cuts, e.g. with h x = atan2 (f x) (-1):

> h 16777214
-3.1415925
> h 16777215
-3.1415925
> h 16777216
3.1415927

Or with some build-in functions:

> imagPart $ atanh $ (-16777217) :+ (-3)
-1.5707964
> imagPart $ atanh $ (-16777218) :+ (-3)
-1.5707964
> imagPart $ atanh $ (-16777219) :+ (-3)
1.5707964

Exception Handling

Note

Throughout this page I have tried to use the words "exception" and "error" as described here.

Some numeric operations raise exceptions in some situations, such as division by zero. It would generally be an error to allow these to occur without handling the exceptions. The following sections are some of the ways to deal with this.

An Aside on Avoiding Errors using Types

It is often best to design data types so that it is impossible to write erroneous programs. As a contrived example, compare the following:

data Suit = Hearts | Diamonds | Clubs | Spades deriving Show

data SuitColour = Red | Black deriving Show

suitColour :: Suit -> SuitColour
suitColour Hearts   = Red
suitColour Diamonds = Red
suitColour Clubs    = Black
suitColour Spades   = Black

with:

--Note:
--0 = Hearts, 1 = Diamonds, 2 = Clubs, 3 = Spades
--0 = Black, 1 = Red

suitColour :: Int -> Int
suitColour 0 = 0
suitColour 1 = 0
suitColour 2 = 1
suitColour 3 = 1

The second version would allow suitColour 152 to compile, which would give an error at run-time. The first version ensures we can't write such erroneous code (as well as being a lot easier to read!).

Suppose we tried to adopt this approach to avoid division by zero errors. We could define a NonZeroInteger type and redefine div with the type signature div :: Integer -> NonZeroInteger -> Integer. Now we have to fix errors like x `div` 0 at compile time and would never get a division by zero run-time exception.

But at some point we might want to code e.g. x `div` (y - z). And now we have a problem:

• we may want to allow either y or z to individually be zero (hence they would not be of type NonZeroInteger, so we'd need to convert them to NonZeroInteger in order to pass the result to div); and
• y and z might be the same, so (x - y) would be zero and the conversion would fail with a run-time exception that zero is out-of-bounds for NonZeroInteger.

This attempt to use types to catch division by zero at compile time has failed: we've just swapped one possible run-time exception for another. (And added complexity to the types).

Program logic

One way to avoid run-time exceptions is to include logic in your program, especially at places where you get data from the outside world (e.g. a user).

Here's an example program:

doDiv :: IO ()
doDiv = do
  putStr "Enter an integer: "
  x <- readLn
  let (d,r) = 100 `divMod` x
  putStrLn $ "100 divided by " ++ show x ++ " is " ++ show d ++ " remainder " ++ show r

It has a couple of problems, including that the user could type non-integer values (which we'll ignore for now), and that they or they could type in "0".

Exercises
Modify doDiv so it detects the zero and gives a different message.

"Safe" functions

One approach often advocated for pure functions (i.e. where the result depends only on the arguments passed to it) is have the function return Nothing for those values where it "fails". For example, the function:

stripPrefix :: Eq a => [a] -> [a] -> Maybe [a]

drops the given prefix from a list, but returns Nothing if the list did not start with it. There are also a number of safe functions in other modules (such as the cunningly named Safe, that provides safe version of list functions such as head).

Similarly, we could write "safe" versions of div etc:

safeDiv :: Integral a => a -> a -> Maybe a
_ `safeDiv` 0 = Nothing
x `safeDiv` y = Just $ x `div` y

Although a reasonable approach, it might be quite a challenge to build "safe" versions for all of the functions you use, especially since you would have to check the error conditions for each of them.

Exercises
Create a safeDivMod and modify doDiv to use it.

Note that you could use Either instead of Maybe to similar effect, and this would allow the response to indicate the type of error that occurred (not just that there was one).

Catching Exceptions

Another way to handle exceptions is with catch. This is defined as:

catch :: Exception e => IO a -> (e -> IO a) -> IO a

Both the result of catch and its first argument are IO monads. The second argument is an "exception handler". When executed, catch executes its first argument and, if an exception is raised, the "handler" is executed with the value of the exception passed as an argument. Otherwise, the result is returned as normal.

This works well with many IO actions, such as opening a file:

catch (readFile f)
      (\e -> do let err = show (e :: IOException)
                hPutStr stderr ("Warning: Couldn't open " ++ f ++ ": " ++ err)
                return "")

Here's a first attempt at using it in doDiv:

doDiv = do
  putStr "Enter an integer: "
  x <- readLn :: IO Integer
  catch (do let (d,r) = 100 `divMod` x
            putStrLn $ "100 divided by " ++ show x ++ " is " ++ show d ++ " remainder " ++ show r)
        (\e -> putStrLn $ const "Sorry, I can't divide by zero." (e :: ArithException))

Which gives the following:

> doDiv
Enter an integer: 0
100 divided by 0 is Sorry, I can't divide by zero.

which isn't quite what we want. The problem is that, as a result of lazy evaluation, putStrLn is happy to start displaying the result of "100 divided by ... before attempting to evaluate the div. The div is only evaluated when putStrLn needs the (++) to evaluate show d, and this is when the exception is triggered. The behaviour would be the same if the let (d,r) is outside of the catch.

However, we can "force" the evaluation of the div earlier, using evaluate:

evaluate :: a -> IO a

evaluate $ 100 `divMod` x will create an IO action which, when executed, will force evaluation of the div, and throw the exception if appropriate.

Exercises
Modify doDiv to use evaluate. Write validFloat that takes a floating-point value and returns it if it's valid, or throws an exception if it's Infinity or NaN. Write a function w8AddT. It should be like w8AddErr but, on overflow, should throw an exception instead of giving an error.

Note that evaluate doesn't "fully evaluate" expressions. For example, it would not cause an exception in head <$> evaluate [3, 4 `div` 0].

Catching Exceptions can be Painful

It might be nice if we could display tables showing how numeric operators worked, like this:

> putOpTable (-) [0, 1, 2 :: Int]
         0    1    2
    0    0   -1   -2
    1    1    0   -1
    2    2    1    0

But we need to be careful with operations that throw exceptions, so that we get this:

> putOpTable div [0, 1, 2 :: Int]
         0    1    2
    0    -    0    0
    1    -    1    0
    2    -    2    1

Our first attempt at putOpTable might start like this:

putOpTable :: Show a => (a -> a -> a) -> [a] -> IO ()
putOpTable op xs = do
  putStrLn titleLine
  mapM_ (putStrLn . opLine) xs

Exercises

Complete putOpTable, providing the implementation for the (pure) functions titleLine and opLine. Initially ignore any error handling. It should work for the (-) example above. Now create putOpTableCatch based on putOpTable but converted to add exception handling using catch and evaluate. It should work for both the (-) and the div examples above. As an alternative, write a version putOpTableSafe to use "safe" operators (putOpTableSafe safeDiv should work). What are the pros and cons of this vs the catch version?

You probably found the conversion to putOpTableCatch quite painful. We can no longer construct a string for each line using a pure function, since we want to catch exceptions in the middle of the string. Instead we have to execute putStr for each cell in the table, handing exceptions as we go, and much more of the code is written in the IO monad.

Catching Exceptions in Pure Code

Wouldn't it be nice if we could catch exceptions in pure code? Then we could keep the pure function opLine in putOpTable above, replacing any exceptions with the "-" character we want.

There is a way to do this, using this function with a slightly scary name from the module System.IO.Unsafe:

unsafePerformIO :: IO a -> a

which allows an IO computation to be performed at any time. It comes with a warning: For this to be safe, the IO computation should be free of side effects and independent of its environment. However, we only want to evaluate (pure) expressions and handle the exceptions they throw, so I think we're OK.

We can define:

checkArith :: a -> Maybe a
checkArith x = unsafePerformIO $
  catch (Just <$> evaluate x)
        (\e -> return $ const Nothing $ (e :: ArithException))

Now:

> checkArith $ 100 `div` 3
Just 33
> checkArith $ 100 `div` 0
Nothing
> putOpTableSafe (\x y -> checkArith $ x `div` y) [0, 1, 2]
         0    1    2
    0    -    0    0
    1    -    1    0
    2    -    2    1

Exercises
Modify putOpTable to use checkArith. Check e.g. putOpTable (-) [0, 1, 2 :: Natural] works.

Example Num Instances

Mod3

Let's create a new numeric type that does arithmetic modulo 3, so that addition works like this:

+	0	1	2
0	0	1	2
1	1	2	0
2	2	0	1

Here's a start:

data Mod3 = Zero | One | Two
  deriving (Eq, Ord, Enum, Bounded, Show, Read)

Note that we can automatically derive instances of many standard classes for this type. Also, this shows that being a "numeric" doesn't necessarily mean we have to use numeric digits (0, 1, 2) to represent the values.

Let's make this an instance of the appropriate numeric classes.

Num Instance

In order to do addition using (+), we need to make this an instance of Num:

instance Num Mod3 where
  Zero + Zero = Zero
  Zero + One  = One
  ...

OK - I got bored, so your turn:

Exercises

Use some maths (e.g. $x+0=x$), and the succ function (that we got for free by deriving Enum) to write a more interesting version of (+). Use putOpTable (+) [Zero, One, Two] to display an operation table, and check it against the table above. Add an implementation for (*). Again, use some maths! Check it using putOpTable. Add an implementation for negate. Use $-x+x=0$. (-) will now also work. (How?). Check (-) using putOpTable. Add implementations for abs and signum. Add an implementation for fromInteger. Follow the pattern for other bounded integers, where e.g. fromInteger 257 :: Word8 gives 1. (You can use toEnum to make this function less boring!). Once this is working, you should be able to type 2 :: Mod3 into GHCi and get Two (as described later).

Real and Integral Instances

Exercises

Write the Real instance. It only needs to support the toRational method. (What do you expect toRational Two to give?) You can leverage fromEnum. Start the Integral instance and implement the toInteger method. Again, you can leverage fromEnum. Write the code for _ `quotRem` Zero. This should use throw from Control.Exception. Check it by doing One `quotRem` Zero in GHCi. Write the remaining code for quotRem, using maths. (e.g., in x `quotRem` y, if x is less than y the answer is (Zero, y)). div, mod, etc, should now all work. (How?) Test the div function using putOpTable, and check that the exception handling works for division by zero.

Show and Read Instances

Exercises
Write custom Show and Read instances, so that the Mod3 numbers look like "0", "1" and "2". (Hint:: leverage Show and Read implementations for another type.)

Word8T

The standard Word8 type performs arithmetic modulo 256. Sometimes it would be useful to have a type that throws exceptions on overflow instead, so let's create type Word8T that does that.

Exercises

Create a newtype declaration for Word8T, so that it's based on Word8. Note that, if you enable the GHC extension GeneralizedNewtypeDeriving you can derive instances of Enum, etc, that simply inherit the implementations from the inner type. The numeric functions where overflow may occur are all in the Num class, so implement that. Leverage w8AddT and similar from earlier exercises, and implementations in the inner type where appropriate. We want Word8T to be an instance of other numeric types. Add these to the deriving clause. (This is possible, even though some of the methods use the custom Num implementation.)