7.3.1 Rational number arithmetic

For this example, let’s implement a group of Haskell functions to perform rational number arithmetic, assuming that the Haskell library does not contain such a data type. We focus first on the operations we want to perform on the data.

In mathematics we usually write rational numbers in the form $\frac{\texttt{x}}{\texttt{y}}$ where x and y are integers and y $\neq$ 0.

For now, let us assume we have a special type Rat to represent rational numbers and a constructor function

    makeRat :: Int -> Int -> Rat

to create a Haskell rational number instance from a numerator x and a denominator y. That is, makeRat x y constructs a Haskell rational number with mathematical value $\frac{\texttt{x}}{\texttt{y}}$, where $\texttt{y} \neq 0$.

Let us also assume we have selector functions numer and denom with the signatures:

    numer, denom :: Rat -> Int

Functions numer and denom take a valid Haskell rational number and return its numerator and denominator, respectively.

Requirement:

For any Int values x and y where $\texttt{y} \neq 0$, there exists a Haskell rational number r such that makeRat x y == r and rational number values $\frac{\texttt{numer r}}{\texttt{denom r}}$ $=$ $\frac{\texttt{x}}{\texttt{y}}$.

Note: In this example, we use fraction notation like $\frac{\texttt{x}}{\texttt{y}}$ to denote the mathematical value of the rational number. In constrast, r above denotes a Haskell value representing a rational number.

We consider how to implement rational numbers in Haskell later, but for now let’s look at rational arithmetic implemented using the constructor and selector functions specified above.

Given our knowledge of rational arithmetic from mathematics, we can define the operations for unary negation, addition, subtraction, multiplication, division, and equality as follows. We assume that the operands x and y are values created by the constructor makeRat.

    negRat :: Rat -> Rat 
    negRat x = makeRat (- numer x) (denom x)

    addRat, subRat, mulRat, divRat :: Rat -> Rat -> Rat  -- (1)
    addRat x y = makeRat (numer x * denom y + numer y * denom x)
                         (denom x * denom y) 
    subRat x y = makeRat (numer x * denom y - numer y * denom x)
                         (denom x * denom y) 
    mulRat x y = makeRat (numer x * numer y) (denom x * denom y) 
    divRat x y  -- (2) (3)
        | eqRat y zeroRat = error "Attempt to divide by 0"
        | otherwise       = makeRat (numer x * denom y)
                                    (denom x * numer y)

    eqRat :: Rat -> Rat -> Bool 
    eqRat x y = (numer x) * (denom y) == (numer y) * (denom x)

The above code:

1. combines the type signatures for all four arithmetic operations into a single declaration by listing the names separated by commas

2. introduces the parameterless function zeroRat to abstract the constant rational number value 0

   Note: We could represent zero as makeRat 0 1 but choose to introduce a separate abstraction.

3. calls the error function for an attempt to divide by zero

These arithmetic functions do not depend upon any specific representation for rational numbers. Instead, they use rational numbers as a data abstraction defined by the type Rat, constant zeroRat, constructor function makeRat, and selector functions numer and denom.

The goal of a data abstraction is to separate the logical properties of data from the details of how the data are represented.

7.3.2 Rational number data representation

Now, how can we represent rational numbers?

For this package, we define type synonym Rat to denote this type:

    type Rat = (Int, Int) 

For example, (1,7), (-1,-7), (3,21), and (168,1176) all represent the value $\frac{\texttt{1}}{\texttt{7}}$.

As with any value that can be expressed in many different ways, it is useful to define a single canonical (or normal) form for representing values in the rational number type Rat.

It is convenient for us to choose a Haskell rational number representation (x,y) that satisfies all parts of the following Rational Representation Property:

• (x,y) $\in$ (Int,Int)

• y > 0

• if x == 0, then y == 1

• x and y are relatively prime

• rational number value is $\frac{\texttt{x}}{\texttt{y}}$

By relatively prime, we mean that the two integers have no common divisors except 1.

This representation keeps the magnitudes of the numerator x and denominator y small, thus reducing problems with overflow arising during arithmetic operations.

This representation also gives a unique representation for zero. For convenience, we define the name zeroRat to represent this constant:

    zeroRat :: (Int,Int)
    zeroRat = (0,1)

We can now define constructor function makeRat x y that takes two Int values (for the numerator and the denominator) and returns the corresponding Haskell rational number in this canonical form.

    makeRat :: Int -> Int -> Rat
    makeRat x 0 = error ( "Cannot construct a rational number "
                          ++ show x ++ "/0" )         -- (1)
    makeRat 0 _ = zeroRat
    makeRat x y = (x' `div` d, y' `div` d)            -- (2)
        where x' = (signum' y) * x                    -- (3,4)
              y' = abs' y 
              d  = gcd' x' y'

In the definition of makeRat, we use features of Haskell we have not used in the previous examples. the above code:

1. uses the infix ++ (read “append”) operator to concatenate two strings

   We discuss ++ in the chapter on infix operations.

2. puts backticks (`) around an alphanumeric function name to use that function as an infix operator

   The function div denotes integer division. Above the div operator denotes the integer division function used in an infix manner.

3. uses a where clause to introduce x', y', and d as local definitions within the body of makeRat

   These local definition can be accessed from within makeRat but not from outside the function. In contrast, sqrtIter in the Square Root example is at the same level as sqrt', so it can be called by other functions (in the same Haskell module at least).

   The where feature allows us to introduce new definitions in a top-down manner—first using a symbol and then defining it.

4. uses type inference for local variables x', y', and d instead of giving explicit type definitions

   These parameterless functions could be declared

       x', y', d :: Int

   but it was not necessary because Haskell can infer the types from the types involved in their defining expressions.

   Type inference can be used more broadly in Haskell, but explicit type declarations should be used for any function called from outside.

We require that makeRat x y satisfy the precondition:

    y /= 0

The function generates an explicit error exception if it does not.

As a postcondition, we require makeRat x y to return a result (x',y') such that:

• (x',y') satisfies the Rational Representation Property

• rational number value is $\frac{\texttt{x}}{\texttt{y}}$

Note: Together the two postcondition requirements imply that $\frac{\texttt{x'}}{\texttt{y'}}$ $=$ $\frac{\texttt{x}}{\texttt{y}}$.

The function signum' (similar to the more general function signum in the Prelude) takes an integer and returns the integer -1, 0, or 1 when the number is negative, zero, or positive, respectively.

    signum' :: Int -> Int 
    signum' n | n == 0     =  0 
              | n > 0      =  1 
              | otherwise  = -1 

The function abs' (similar to the more general function abs in the Prelude) takes an integer and returns its absolute value.

    abs' :: Int -> Int
    abs' n | n >= 0    =  n
           | otherwise = -n

The function gcd' (similar to the more general function gcd in the Prelude) takes two integers and returns their greatest common divisor.

    gcd' :: Int -> Int -> Int 
    gcd' x y = gcd'' (abs' x) (abs' y) 
        where gcd'' x 0 = x 
              gcd'' x y = gcd'' y (x `rem` y) 

Prelude operation rem returns the remainder from dividing its first operand by its second.

Given a tuple (x,y) constructed by makeRat as defined above, we can define numer (x,y) and denom (x,y) as follows:

    numer, denom :: Rat -> Int
    numer (x,_) = x
    denom (_,y) = y

The preconditions of both numer (x,y) and denom (x,y) are that their arguments (x,y) satisfy the Rational Representation Property.

The postcondition of numer (x,y) = x is that the rational number values $\frac{\texttt{x}}{\texttt{numer (x,y)}}$ $=$ $\frac{\texttt{x}}{\texttt{y}}$.

Similarly, the postcondition of denom (x,y) = y is that the rational number values $\frac{\texttt{denom (x,y)}}{y}$ $=$ $\frac{\texttt{x}}{\texttt{y}}$.

Finally, to allow rational numbers to be displayed in the normal fractional representation, we include function showRat in the package. We use function show, found in the Prelude, here to convert an integer to the usual string format and use the list operator ++ to concatenate the two strings into one.

    showRat :: Rat -> String
    showRat x = show (numer x) ++ "/" ++ show (denom x)

Unlike Rat, zeroRat, makeRat, numer, and denom, function showRat (as implemented) does not use knowledge of the data representation. We could optimize it slightly by allowing it to access the structure of the tuple directly.

7.3.3 Rational number modularization

There are three groups of functions in this package:

1. the six public rational arithmetic functions negRat, addRat, subRat, mulRat, divRat, and eqRat

2. the public type Rat, constant zeroRat, public constructor function makeRat, public selector functions numer and denom, and string conversion function showRat

3. the private utility functions called only by the second group, but just reimplementations of Prelude functions anyway

    module RationalCore
        (Rat, makeRat, zeroRat, numer, denom, showRat)
    where
        -- Rat,makeRat,zeroRat,numer,denom,showRat definitions

    module Rational1
      ( Rat, zeroRat, makeRat, numer, denom, showRat,
        negRat, addRat, subRat, mulRat, divRat, eqRat )
    where
        import RationalCore
        -- negRat,addRat,subRat,mulRat,divRat,eqRat definitions 

7.3.4 Alternative data representation

In the rational number data representation above, constructor makeRat creates pairs in which the two integers are relatively prime and the sign is on the numerator. Selector functions numer and denom just return these stored values.

An alternative representation is to reverse this approach, as shown in the following module (in file RationalDeferGCD.hs.)

    module RationalDeferGCD
        (Rat, zeroRat, makeRat, numer, denom, showRat)
    where

    type Rat = (Int,Int)

    zeroRat :: (Int,Int)
    zeroRat = (0,1)

    makeRat :: Int -> Int -> Rat
    makeRat x 0 = error ( "Cannot construct a rational number "
                          ++ show x ++ "/0" )
    makeRat 0 y = zeroRat 
    makeRat x y = (x,y)

    numer :: Rat -> Int
    numer (x,y) = x' `div` d
        where x' = (signum' y) * x 
              y' = abs' y 
              d  = gcd' x' y'

    denom :: Rat -> Int
    denom (x,y) = y' `div` d
        where x' = (signum' y) * x 
              y' = abs' y 
              d  = gcd' x' y'

    showRat :: Rat -> String
    showRat x = show (numer x) ++ "/" ++ show (denom x)

This approach defers the calculation of the greatest common divisor until a selector is called.

In this alternative representation, a rational number (x,y) must satisfy all parts of the following Deferred Representation Property:

• (x,y) $\in$ (Int,Int)

• y /= 0

• if x == 0 , then y == 1

• rational number value is $\frac{\texttt{x}}{\texttt{y}}$

Furthermore, we require that makeRat x y satisfies the precondition:

    y /= 0

The function generates an explicit error condition if it does not.

As a postcondition, we require makeRat x y to return a result (x',y') such that:

• (x',y') satisfies the Deferred Representation Property

• rational number value is $\frac{\texttt{x}}{\texttt{y}}$

The preconditions of both numer (x,y) and denom (x,y) are that (x,y) satisfies the Deferred Representation Property.

The postcondition of numer (x,y) = x' is that the rational number values $\frac{\texttt{x'}}{\texttt{numer (x,y)}}$ $=$ $\frac{\texttt{x}}{\texttt{y}}$.

Similarly, the postcondition of denom (x,y) = y is that the rational number values $\frac{\texttt{denom (x,y)}}{y'}$ $=$ $\frac{\texttt{x}}{\texttt{y}}$.

Question:

What are the advantages and disadvantages of the two data representations?

Like module RationalCore, the design secret for this module, RationalDeferGCD, is the rational number data representation.

Regardless of which approach is used, the definitions of the arithmetic and comparison functions do not change. Thus the Rational module can import data representation module RationalCore or RationalDeferGCD.

Figure 7.1 shows the dependencies among the modules we have examined in the rational arithmetic example.

We can consider the RationalCore and RationalDeferGCD modules as two concrete instances (Haskell modules) of a more abstract module we call RationalRep in the diagram.

The module Rational relies on the abstract module RationalRep for an implementation of rational numbers. In the Haskell code above, there are really two versions of the Haskell module Rational that differ only in whether they import RationalCore or RationalDeferGCD.

Chapter 21 introduces user-defined (algebraic) data types. Instead of concrete data types (e.g., the Int pairs used by the type alias Rat), we can totally hide the details of the data representation using modules.

7.3.5 Haskell information-hiding modules

In the Rational Arithmetic example, we defined two information-hiding modules:

1. “RationalRep”, whose secret is how to represent the rational number data and whose interface consists of the data type Rat, constant zeroRat, operations (functions) makeRat, numer, denom, and showRat, and the constraints on these types and functions

2. “Rational”, whose secret is how to implement the rational number arithmetic and whose interface consists of operations (functions) negRat, addRat, subRat, mulRat, divRat, and eqRat, the other module’s interface, and the constraints on these types and functions

We developed two distinct Haskell modules, RationalCore and RationalDeferGCD, to implement the “RationalRep” information-hiding module.

We developed one distinct Haskell module, Rational, to implement the “Rational” information-hiding module. This module can be paired (i.e., by changing the import statement) with either of the other two variants of “RationalRep” module. (Source file Rational1.hs imports module RationalCore; source file Rational2.hs imports module RationalDeferGCD.)

Unfortunately, Haskell 2010 has a relatively weak module system that does not support multiple implementations as well as we might like. There is no way to declare that multiple Haskell modules have the same interface other than copying the common code into each module and documenting the interface carefully. We must also have multiple versions of Rational that differ only in which other module is imported.

Together the Glasgow Haskell Compiler (GHC) release 8.2 (July 2017) and the Cabal-Install package manager release 2.0 (August 2017) support a new extension, the Backpack mixin package system. This new system remedies the above shortcoming. In this new approach, we would define the abstract module “RationalRep” as a signature file and require that RationalCore and RationalDeferGCD conform to it.

Further discussion of this new module system is beyond the scope of this chapter.

7.3.6 Rational number testing

Chapter 12 discusses testing of the Rational modules designed in this chapter. The test scripts for the following modules are in the files shown:

• Module RationalRep

  • TestRatRepCore.hs for module instance RationalCore

  • TestRatRepDefer.hs for module instance RationalDeferGCD

• Module Rational

  • TestRational1.hs for Rational using RationalCore.

  • TestRational2.hs for Rational using RationalDeferGCD.

7.4.1 RationalRep modules

In the Rational Arithmetic example, the interface invariant for the “RationalRep” abstract module is the following.

RationalRep Interface Invariant:

For any valid Haskell rational number r, all the following hold:

• r $\in$ Rat

• denom r > 0

• if numer r == 0, then denom r == 1

• numer r and denom r are relatively prime

• the (mathematical) rational number value is $\frac{\texttt{numer r}}{\texttt{denom r}}$

We note that the precondition for makeRat x y is defined above without any dependence upon the concrete representation.

    y /= 0

We can restate the postcondition for makeRat x y = r generically to require both of the following to hold:

• r satisfies the RationaRep Interface Invariant

• rational number r ’s value is $\frac{\texttt{x}}{\texttt{y}}$

The preconditions of both numer r and denom r are that their argument r satisfies the RationalRep Interface Invariant.

The postcondition of numer r = x' is that the rational number value $\frac{\texttt{x'}}{\texttt{denom r}}$ is equal to the rational number value of r.

Similarly, the postcondition of denom r = y' is that the rational number value $\frac{\texttt{numer r}}{y'}$ is equal to the rational number value of r.{.haskell}

An implementation invariant guides the developers in the design and implementation of the internal details of a module. It relates the internal details to the interface invariant.

7.4.2 Rational modules

The Rational abstract module extends the RationalRep abstract module with new functionality.

• It imports the public interface of the RationalRep abstract module and exports those features in its own public interface. Thus it must maintain the interface invariant for the RationalRep module it uses.

• It does not add any new data types or constructor (or destructor) functions. So it does not need any new invariant components for new data abstractions.

• It adds one unary and four binary arithmetic functions that take rational numbers and return a rational number. It does so by using the data abstraction provided by the RationalRep module. These must preserve the RationalRep interface invariant.

• It adds an equality comparison function that takes two rational numbers and returns a Bool.