There was an error submitting the form

Copied to clipboard

"Obverse, or reverse, I can make nothing out of it." - Mohi

Published: Feb. 19, 2015

Last updated: Feb. 9, 2022

Still other examples will show not only the harmony between obverse and reverse, but how coins were dedicated to more than one divinity.

—Isaac Bassett Choate (Myth in American Coinage)

In section 7.5 of Thinking Functionally with Haskell, Richard Bird
uses the `reverse`

function as an example of improving the running
time of a function by adding an accumulating parameter to it. He
begins with a simple and inefficient definition of `reverse`

, which
we'll call `obverse`

:

```
obverse :: [a] -> [a]
obverse [] = []
obverse (x:xs) = obverse xs ++ [x]
```

In order to get a better idea of the inefficiency of this function, let's clock it:

```
> clockSomething (obverse [1..1000000] :: [Integer])
1.20 s
> clockSomething (obverse [1..10000000] :: [Integer])
11.66 s
```

In search of a more efficient definition of `obverse`

, Bird defines an
auxiliary function, `reverse'`

, as follows:

```
reverse' :: [a] -> [a] -> [a]
reverse' xs ys = obverse xs ++ ys
```

Clearly,

```
obverse xs == reverse' xs []
```

An efficient definition of `reverse'`

can be calculated by induction.
In the case of an empty list,

`reverse' [] ys`

`==`

(by definition of `reverse'`

)

`obverse [] ++ ys`

`==`

(by definition of `obverse`

)

`[] ++ ys`

`==`

(by left identity)

`ys`

Otherwise,

`reverse' (x:xs) ys`

`==`

(by definition of `reverse'`

)

`obverse (x:xs) ++ ys`

`==`

(by definition of `obverse`

)

`(obverse xs ++ [x]) ++ ys`

`==`

(by associativity)

`obverse xs ++ [x] ++ ys`

`==`

(by definition of `(++)`

and left identity)

`obverse xs ++ (x:ys)`

`==`

(by definition of `reverse'`

)

`reverse' xs (x:ys)`

The efficient definition of `reverse'`

can be used to define an
efficient `reverse`

function, as follows:

```
reverse :: [a] -> [a]
reverse xs = reverse' xs []
where
reverse' [] ys = ys
reverse' (x:xs') ys = reverse' xs' (x:ys)
```

In order to compare the efficiency of the `obverse`

and `reverse`

functions, let's clock the latter too:

```
> clockSomething (reverse [1..1000000] :: [Integer])
493.63 ms
> clockSomething (reverse [1..10000000] :: [Integer])
5.08 s
```

This is not just an example of how to improve a program's performance, but an example of how to use mathematics to find a better algorithm, which is "the best way to improve a program's performance." We're merely using definitions and the fact that lists, the empty list, and the append function form a monoid, but we could do so much more. In short, it's just an example of how to use mathematics as one way to better understand and improve our programs.

(For more information and the definition of `clockSomething`

, see
https://github.com/stackbuilders/reverse.)