Next: More fun (sic!) with Up: The Frightened Freshers Guide Previous: Enumerated Types

Recursion

Recursion is the practice of including a function in its own definition. First of all, we really need to know how to define a recursive datatype for use in such a recursive function. The example below is a list of integers.
$\begin{lstlisting} data ListInt = Nil \vert Cons Int ListInt deriving(Show,Eq,Ord) \end{lstlisting}$

Although this does seem very odd at first, it makes perfect sense in reality! The two options for things of type ListInt are either Nil (So the list will end here) or Int ListInt in which there will be a single Int and then another ListInt inside of the current ListInt. This can go on for as long as you like. Valid values for this datatype include:
$\begin{lstlisting} Nil Cons 42 Nil Cons 42 (Cons 6 Nil) \end{lstlisting}$

You can also do pattern matching on datatypes such as the ListInt datatype that was defined earlier. The functions below return the first element in a list and the rest of a list respecively.

$\begin{lstlisting} headList :: ListInt -> Int headList Nil = error ''Woops, noth... ...= error ''Argh, this list is empty!'' tailList (Cons x xs) = xs \end{lstlisting}$

In each of these definitions you can check how it works based on the recursive definition of ListInt. The first one, headList, will assign the variables x and xs to the first (an Int) and last (A ListInt) parts of the data fed to it and thus spit out the first Integer in the ListInt. The tailList has an almost identical structure to it and will instead return the ListInt minus the first Integer.

Another example given in lectures for the ListInt datatype is the ability to sum all of the items in a ListInt. Its function definition is as follows:

$\begin{lstlisting} sumList :: ListInt -> Int sumList Nil = 0 sumList (Cons x ys) = x + sumList ys \end{lstlisting}$

Once again, this is just a function that will keep on going around, and around, and around until it reaches a Nil. Evaluation for this function is fairly similar to the one for tailList and headList.

	sumList Cons 42 (Cons 6 Nil)
	42 + sumList (Cons 6 Nil)
	42 + 6 + sumList Nil
	48 + 0
	48

It is quite easy to see what is going on when everything is broken down, but if you try and do it all at once then I almost guarantee you will get confused. So break it down into its smallest components for the best results!

Next: More fun (sic!) with Up: The Frightened Freshers Guide Previous: Enumerated Types

Tom Carlson 2006-04-11