15.8 Haskell 711
wanted to know if a particular number was a perfect square, we could check the
squares list with a membership function. Suppose we had a predicate function
named member that determined whether a given atom is contained a given list.
Then we could use it as in
member 16 squares
which would return True. The squares definition would be evaluated until
the 16 was found. The member function would need to be carefully written.
Specifically, suppose it were defined as follows:
member b [] = False
member b (a:x)= (a == b) || member b x
The second line of this definition breaks the first parameter into its head and
tail. Its return value is true if either the head matches the element for which
it is searching (b) or if the recursive call with the tail of the list returns True.
This definition of member would work correctly with squares only if the
given number were a perfect square. If not, squares would keep generating
squares forever, or until some memory limitation was reached, looking for the
given number in the list. The following function performs the membership test
of an ordered list, abandoning the search and returning False if a number
greater than the searched-for number is found.^14
member2 n (m:x)
| m < n = member2 n x
| m == n = True
| otherwise = False
Lazy evaluation sometimes provides a modularization tool. Suppose that
in a program there is a call to function f and the parameter to f is the return
value of a function g.^15 So, we have f(g(x)). Further suppose that g produces
a large amount of data, a little at a time, and that f must then process this data,
a little at a time. In a conventional imperative language, g would run on the
whole input producing a file of its output. Then f would run using the file as
its input. This approach requires the time to both write and read the file, as
well as the storage for the file. With lazy evaluation, the executions of f and g
implicitly would be tightly synchronized. Function g will execute only long
enough to produce enough data for f to begin its processing. When f is ready
for more data, g will be restarted to produce more, while f waits. If f termi-
nates without getting all of gās output, g is aborted, thereby avoiding useless
computation. Also, g need not be a terminating function, perhaps because it
produces an infinite amount of output. g will be forced to terminate when f
- This assumes that the list is in ascending order.
- This example appears in Hughes (1989).
