SGR@SCRC-STONY-BROOK.ARPA (Stephen G. Rowley) (06/03/86)
Date: Mon, 2 Jun 86 09:27 N
From: DESMEDT%HNYKUN52.BITNET@WISCVM.WISC.EDU
In AIList Digest V4 #134, Mike Maxwell reluctantly prefers the efficiency
of a hand-coded "do" construction in Lisp, although mapping a function on
a list would be more elegant. Indeed, mapping sometimes causes many
unnecessary computations. Consider the following example:
(defun member (element list)
(apply 'or (mapcar #'(lambda (list-element)
(eql element list-element))
list)))
I can't help but point out that, if you're using Common Lisp, this
function is strange on several accounts:
[1] It shadows MEMBER, which can't be a good idea.
[2] It tries to return the first thing in the list eql to element,
whereas the real MEMBER returns a tail of the list or NIL.
[3] It attempts to apply OR, which is a special form and hence cannot be
applied. In this case, you'd use SOME instead.
Obviously, though, I'm just quibbling with your example. Let's move on:
Your statements about the general wastefulness of mapping functions are
true, if you restrict yourself to MAPCAR and friends. However, if you
write your own mapping functions, they can be quite elegant.
Here's an example. I was writing a discrimination net for a pattern
database. Given a pattern, it would search a database for things that
might unify with it, and do something to all of them. (See, for
example, Charniak, Riesbeck, & McDermott's "Artificial Intelligence
Programming", chapters 11 & 14.) For example, a program might want to
print everything that unified with the pattern (foo a ?x), where ?x is a
variable.
The first implementation cried out for lazy evaluation; I didn't want to
compute a list of all the patterns because of consing effects. The
top-level search function returned a stream object (simulation of
laziness) which could be prodded to produce the next answer:
(loop with stream = (search-for-pattern '(foo a ?x))
for next = (next-element stream)
while next
doing (print next))
The second implementation got smarter and made the callers of the search
function package up their intentions in a closure. The search function
would then apply that closure to patterns that it found. The result is
something very mapping-like:
(search-for-pattern '(foo a ?x) #'print)
The second implementation also turned out to be faster and consed less,
although it did use up some more stack space than the first.
Moral: Appropriate use of function closures can often (although not
always) satisfy your needs for lazy evaluation.