next up previous
Next: Trees Up: The Frightened Freshers Guide Previous: Recursion

More fun (sic!) with lists

So, you know how to define recursive datatypes and do a few interesting things with them. You have seen how to get the first element in a list, the last element and summing a list. You may or may not have noticed but operating on lists always take a similar general form.


\begin{lstlisting}
- With the datatype:
data ListInt = Nil \vert Cons Int ListI...
...on Nil = ...
someFunction (Cons x ys) = ... someFunction ys ...
\end{lstlisting}

All the sections with ... in are there to be filled in by you when defining this function. This general form works nicely, you can do anything with your recusively defined datatype and valid inputs from it. An example of something like this is checking if there is a specific element inside of a list.


\begin{lstlisting}
- Keeping the same ListInt definition as above
elemList :: I...
... False
elemList x (Cons y ys) = (x==y) \vert\vert elemList x ys
\end{lstlisting}

While at first this really does not look obvious, its not too bad. If the input list is empty then, of course, the function will return False. If not, then first of all the function will check if x is equal to y and return True if it is so and otherwise will call elemList once again with the same input (x) and the remains of the list (ys). The || operator is the logical OR operator, so if either the first or the second part of it is True then the whole thing will be True. The easiest way to understand this is by using once again step by step evaulation.


\begin{lstlisting}
- This example the input (6)
- is in the list (6, 42 and Ni...
...) \vert\vert (True)
 True
- So 6 is in the list 6, 42 and Nil!
\end{lstlisting}

It should be noted that once haskell has found a True in the or bit of code then it will evaluate the whole statement to True. This is another example of lazy evaluation in haskell and saves processing time (haskell does not need to compute the result of elemList 6 Nil in this case because no matter what the outcome, ((True) || (elemList 6 Nil)) will return True).


next up previous
Next: Trees Up: The Frightened Freshers Guide Previous: Recursion
Tom Carlson 2006-04-11