Hi,
I'm taking a Programming Language Concepts class and we're looking at Lisp.
I'm having trouble 'thinking recursively' and would greatly appreciate any
help from someone who is familiar with Lisp programming.
Here is the problem:
A function takes a list of shape descriptions and returns a number
indicating their total area. 3 shapes ( square, circle, rectangle).
The numbers represent dimensions. For circle, the number = radius.
This is a typical call: (area '((square 5) (rect 2 6) (circle 3)) )
Here is what I've written so far:
( defun area ( lst )
;( list
( cond
(( null lst ) 'NO_DATA_PRESENT_!! )
(t
(cond
(( equal ( first( first lst )) 'square ) (* ( second( first
lst ))( second ( first lst ))) )
(( equal ( first( first lst )) 'circle ) (* 3.14159 (*
second( first lst )))( second ( first lst ))) )
(( equal ( first( first lst )) 'rect ) (* ( second( first
lst)) ( third( first lst ))) )
)
( area( rest lst ))
);END - t
);END - cond
);END - ( defun area ( lst )
IT 'AINT WORKIN' !!
Thank you very much in advance to anyone who can help this poor novice out
!!
John
"John Kontos" <········@bellsouth.net> writes:
>
> Hi,
>
> I'm taking a Programming Language Concepts class and we're looking at Lisp.
> I'm having trouble 'thinking recursively' and would greatly appreciate any
> help from someone who is familiar with Lisp programming.
>
> Here is the problem:
>
> A function takes a list of shape descriptions and returns a number
> indicating their total area. 3 shapes ( square, circle, rectangle).
> The numbers represent dimensions. For circle, the number = radius.
>
> This is a typical call: (area '((square 5) (rect 2 6) (circle 3)) )
>
> Here is what I've written so far:
>
[Reformatted to more usual Lisp conventions:]
> (defun area (lst)
> ;( list
> (cond
> ((null lst) 'NO_DATA_PRESENT_!! )
> (t
> (cond
> ((equal (first (first lst)) 'square )
> (* (second (first lst)) (second (first lst))) )
> ((equal (first (first lst)) 'circle )
> (* 3.14159 (* (second (first lst))) (second (first lst))) )
> ((equal (first (first lst)) 'rect)
> (* (second (first lst)) (third (first lst))) )
> )
> (area (rest lst))
> );END - t
> );END - cond
> );END - ( defun area ( lst )
>
> IT 'AINT WORKIN' !!
OK. Let's start with some basic principles involved in recursive
function design. Recursive functions work by breaking down a problem
into smaller pieces that can be more easily solved, and then assembling
the results of these additional function calls into the final answer.
Based on that, your function has a couple of problems. The first is
that there is no attempt to combine the results of recursively applying
the function to each of the subproblems. The second is that the end
case returns a value (namely 'NO_DATA_PRESENT) which you would not be
able to combine even if the first problem was solved.
Analysis of your problem:
The final result that you want is to compute the total area. That
should suggest a particular arithmetic operator as the natural one
for handling the combination aspects of the problem.
Once you have this operator, you can turn your attention to the
problem of handling the NULL case. You can do this in one of
several ways. One would be to ask youself what is the area of a
list of no objects. One not unreasonable answer would be zero.
This is convenient because the other method of handling the NULL
case involves examining your combination function and choosing a
value that is the arithmetic identity value. Assuming you decided
that + was the proper function, this would also lead you to zero.
[Aside: If you really want to have an empty list be an error
condition you can do that, but it will complicate the function for
no real gain.]
OK. Now that you have the basic structure, you will need to figure out
how to do the break-down and recombination.
A typical way of doing this in Lisp when processing lists is to handle
the CAR (FIRST) of the list and then the CDR (REST). Connecting these
two parts in your combination function.
My personal preference would be to recursively call the AREA function on
each element and distinguish between those lists which are headed by a
SYMBOL (indicating an object) and those lists headed by a CONS (or
LIST), which indicate a sequence of objects. You could, however, code
the object => Area computation in-line as you have sketched above.
Some syntactic notes:
In Your function above, the first COND clause's T branch ends with the
form (area (rest lst)). That is the value that is returned by that
branch of the cond clause. The computations in the COND form that
precede it are carried out, but the values are never returned, so they
are (in effect) skipped.
That is why your function as currently always returns NO-DATA-PRESENT.
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
"John Kontos" <········@bellsouth.net> writes:
< Hi,
<
< I'm taking a Programming Language Concepts class and we're looking at Lisp.
< I'm having trouble 'thinking recursively' and would greatly appreciate any
< help from someone who is familiar with Lisp programming.
<
< Here is the problem:
(defun area ( lst )
;;( list
(cond
((null lst) 'NO_DATA_PRESENT_!!)
(t (cond
((equal (first (first lst)) 'square)
(* (second (first lst))
(second (first lst))))
((equal (first (first lst)) 'circle)
(* 3.14159 (* second (first lst))) ; ***
(second (first lst)))
) ; ***
((equal (first (first lst)) 'rect)
(* (second (first lst))
(third (first lst)))))
) ; ***
(area (rest lst)))))
Maybe you're trying to do too much at one time. I tend to think that
lisp code likes to be written in many small pieces. Here is some help
that may make the code a bit easier to manage - but it will not do the
recursion because you didn't state whether or not it needed to be tail
recursive. Just kidding - recursion is really useful, not to mention
that it's really nifty stuff. You can't really lose much from
learning.
Also, most Lisps are good at function calling so don't worry about
calling too many functions. I think that sometimes using a function
solely for documentation can help the readability of my program - but
I guess this is really a personal preference.
The function compute-area uses a macro called `case'. It is like
`cond', except that it may be easier to read. The function
compute-area2 uses a `cond' so that you can compare.
Also you'll notice I've replaced `3.14159' with the special variable
named `pi'. Again this is not really important - just thought it may
be worth mentioning to you. (I wonder why it is pie and not *pie*?)
(defun compute-area (object)
(let ((shape (first object))
(params (rest object)))
(case shape ; the case macro
(circle (* (first params) pi))
(square (* (first params) (first params)))
(t
(format t "Unknown shape: ~A" shape)
nil))))
(defun compute-area2 (object)
(let ((shape (first object))
(params (cdr object)))
(cond ((equal shape 'circle) ; good 'ole cond
(* (first params) pi))
((equal shape 'square)
(* (first params) (first params)))
(t
(format t "Unknown shape: ~A" shape)
nil))))
(defun area (lst)
(if (endp lst) ; end of list LST
nil
(compute-area (first lst))))
Hope this helps some...
On Sun, 5 Jul 1998 21:33:25 -0700,
John Kontos <········@bellsouth.net> wrote:
(...)
>Here is the problem:
>
>A function takes a list of shape descriptions and returns a number
>indicating their total area. 3 shapes ( square, circle, rectangle).
>The numbers represent dimensions. For circle, the number = radius.
>
>This is a typical call: (area '((square 5) (rect 2 6) (circle 3)) )
You already have (at least) one solution; I hope I can
provide some additional help.
I hope you are not cheating with your homework
(if you are, your professor may be reading this group!).
>Here is what I've written so far:
>
>( defun area ( lst )
> ;( list
> ( cond
> (( null lst ) 'NO_DATA_PRESENT_!! )
^^^^^^^^^^^^^^^^^^^
This is wrong because (NULL LST) will become true when
you have reached the end of the list, so this is
a normal situation, and then a value of 0 should be
returned to be added to the accumulated area, like this:
((null lst) 0)
> (t
> (cond
These two lines are superfluous.
> (( equal ( first( first lst )) 'square ) (* ( second( first
>lst ))( second ( first lst ))) )
> (( equal ( first( first lst )) 'circle ) (* 3.14159 (*
> second( first lst )))( second ( first lst ))) )
> (( equal ( first( first lst )) 'rect ) (* ( second( first
>lst)) ( third( first lst ))) )
> )
> ( area( rest lst ))
^^^^^^^^^^^^^^
This is not what you need. You need to add the value just
computed to the sum of the values from the rest of the list.
See below.
> );END - t
> );END - cond
>);END - ( defun area ( lst )
One way to amend your solution would be to take the three
clauses starting with equality tests to a separate function
that computes the area of a single shape:
(defun area1 (shape)
(ecase (first shape)
(square (* (second shape) (second shape)))
(circle (* pi (second shape) (second shape)))
(rect (* (second shape) (third shape)))))
This is used e.g. as (AREA1 '(RECT 3 4)).
Note the use of ECASE which will signal an error
if the first element of the list is not a recognisable
shape id: ECASE is like CASE where the `otherwise'
clause is a call to ERROR, and CASE is like a COND
with all these tests for equality implicit. The
above ECASE construction could be written with
COND like this:
(cond ((eql 'square (first shape))
(* ...))
((eql 'circle (first shape))
(* pi ...))
...
(t (error "wrong shape")))
Now that we have AREA1, your function could be rewritten
like this:
(defun area (shapes)
(reduce #'+ (mapcar #'area1 shapes)))
which is the Lisp way of doing this:
(defun area (shapes)
(if (endp shapes) 0
(+ (area1 (first shapes)) (area (rest shapes)))))
Caveat: I believe the above code is correct, but I have
not tested it so take it for what it's worth...
I'd like to add that this particular problem is not
in my opinion the best way to exercise recursiveness.
This is more suitable for exercising generic functions,
and I would prefer writing AREA1 in this way:
(defgeneric area1-better (shape &rest dimensions))
(defmethod area1-better ((shape (eql square)) &rest dimensions)
(* (first dimensions) (first dimensions)))
etc., and of course in a more realistic setting
each kind of shape would be represented by its class
so we would actually have:
(defgeneric area1-even-better (shape))
(defmethod area1-even-better ((shape square))
(* (square-side shape) (square-side shape)))
etc.
Good luck,
Vassil.