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