Greetings.
So I'm working on a little project and I've written a bunch of functions
to manipulate a data structure (I've called it 'cities') that looks
something like this:
(((CITY "BELLINGHAM") (LATITUDE (48 48 0)) (LONGITUDE (122 25 0))
(NEIGHBORS (("SEATTLE" 90))))
((CITY "EL PASO") (LATITUDE (31 47 0)) (LONGITUDE (106 29 0))
(NEIGHBORS (("LAS CRUCES" 37))))
((CITY "GREAT FALLS") (LATITUDE (47 29 33)) (LONGITUDE (112 18 23))
(NEIGHBORS (("HELENA" 87))))
((CITY "PORTLAND") (LATITUDE (45 31 6)) (LONGITUDE (122 40 35))
(NEIGHBORS (("HERMISTON" 181) ("EUGENE" 114) ("SEATTLE" 172))))
((CITY "SEATTLE") (LATITUDE (47 36 32)) (LONGITUDE (122 40 35))
(NEIGHBORS (("BELLINGHAM" 90) ("ELLENSBURG" 107) ("PORTLAND" 172)))))
Everything works ok, except that almost everything is recursive and
sometimes the recursion gets so large that the Lisp Interpreters die (at
least gcl and Allegro did... the snap of clisp I have installed has
other problems.)
For example, to find a city of a specified latitude and longitude, I
have the following functions:
(defun get-cityname-of-coordinates (cities latitude longitude)
(cond ((endp cities) nil)
((and (equal (get-latitude-of-first cities) latitude)
(equal (get-longitude-of-first cities) longitude))
(get-cityname-of-first cities))
(t (get-cityname-of-coordinates (rest cities) latitude
longitude))))
(defun get-latitude-of-first (cities)
(second (assoc 'latitude (first cities))))
(defun get-longitude-of-first (cities)
(second (assoc 'longitude (first cities))))
(defun get-cityname-of-first (cities)
(second (assoc 'city (first cities))))
I would call (get-cityname-of-coordinates cities '(10 10 10) '(10 10
10)) and it would call the other functions and itself until successful.
Does anyone know of an easy way to make get-cityname-of-coordinates into
an iterative function? I was playing around with find-if's but have not
yet gotten anywhere.
Thanks!
--
Jason Holmes
Maybe I'm wrong, but I think its usually a trivial matter to go from
recursive to iterative - you just simulate a stack with your own lists, and
use it in place of the internal stack used by the interpreter for your
recursive calls. That is, push your parameters/locals onto the stack when
you would normally make a recursive call, then re-initialize them and loop.
"Chase Saunders" <········@gwi.net> writes:
> Maybe I'm wrong, but I think its usually a trivial matter to go from
> recursive to iterative - you just simulate a stack with your own lists, and
> use it in place of the internal stack used by the interpreter for your
> recursive calls. That is, push your parameters/locals onto the stack when
> you would normally make a recursive call, then re-initialize them and loop.
There may be multiple conversations on this, and I might be responding
out of turn, but if you're responding to my remark...
What you say is quite true, but it's a solution I was specifically
trying to avoid in the remarks I made. I agree this works, but I was
making a distinction between things like that and things that allow
you to devise an elegant answer that gets around the recursive part.
Some "recursive problems", like fibonacci have tail-recursive
renditions that also do not accumulate data structures. I know how to
accumulate garbage as I compute fib, but I don't know how to make the
trick you have to do there general. (That doesn't mean there isn't a
way; just that I'm not seeing it.) If you broaden the the problem to
allow passing the stack as an argument, you're just begging the
question I was asking, which is: how do you not consume increased
storage over time and still use a recursive paradigm. Problems that
don't have a solution to that would seem to me to be the problems
rainer was saying are "recursive problems". Or maybe he meant
"problems most usefully viewed recursively".
In article <·················@psu.edu> , Jason Holmes <·······@psu.edu>
wrote:
> Greetings.
>
> So I'm working on a little project and I've written a bunch of functions
> to manipulate a data structure (I've called it 'cities') that looks
> something like this:
>
> (((CITY "BELLINGHAM") (LATITUDE (48 48 0)) (LONGITUDE (122 25 0))
> (NEIGHBORS (("SEATTLE" 90))))
> ((CITY "EL PASO") (LATITUDE (31 47 0)) (LONGITUDE (106 29 0))
> (NEIGHBORS (("LAS CRUCES" 37))))
> ((CITY "GREAT FALLS") (LATITUDE (47 29 33)) (LONGITUDE (112 18 23))
> (NEIGHBORS (("HELENA" 87))))
> ((CITY "PORTLAND") (LATITUDE (45 31 6)) (LONGITUDE (122 40 35))
> (NEIGHBORS (("HERMISTON" 181) ("EUGENE" 114) ("SEATTLE" 172))))
> ((CITY "SEATTLE") (LATITUDE (47 36 32)) (LONGITUDE (122 40 35))
> (NEIGHBORS (("BELLINGHAM" 90) ("ELLENSBURG" 107) ("PORTLAND" 172)))))
>
> Everything works ok, except that almost everything is recursive and
> sometimes the recursion gets so large that the Lisp Interpreters die (at
> least gcl and Allegro did... the snap of clisp I have installed has
> other problems.)
>
> For example, to find a city of a specified latitude and longitude, I
> have the following functions:
>
> (defun get-cityname-of-coordinates (cities latitude longitude)
> (cond ((endp cities) nil)
> ((and (equal (get-latitude-of-first cities) latitude)
> (equal (get-longitude-of-first cities) longitude))
> (get-cityname-of-first cities))
> (t (get-cityname-of-coordinates (rest cities) latitude
> longitude))))
>
> (defun get-latitude-of-first (cities)
> (second (assoc 'latitude (first cities))))
>
> (defun get-longitude-of-first (cities)
> (second (assoc 'longitude (first cities))))
>
> (defun get-cityname-of-first (cities)
> (second (assoc 'city (first cities))))
>
> I would call (get-cityname-of-coordinates cities '(10 10 10) '(10 10
> 10)) and it would call the other functions and itself until successful.
>
> Does anyone know of an easy way to make get-cityname-of-coordinates into
> an iterative function? I was playing around with find-if's but have not
> yet gotten anywhere.
You're on the right track with find-if. You need to specify a test function
that returns true if the latitude and longitude of a city in the list
matches the latitude and longitude for which you're searching.
(find-if #'(lambda (city)
;; return true if city latitude and longitude
;; match the search criteria
[body of function])
cities)
The body of the function can reference parameters of the enclosing function
to get the search latitude and longitude.
If this is part of a real program, and not a homework exercise, I'd suggest
that you consider other representations. A structure would give more
efficient access to city fields than the assoc you're now using. And you
can certainly do better than linear search.
--
David B. Lamkins <http://www.teleport.com/~dlamkins/>
((lambda (x) (list x (list 'quote x)))
'(lambda (x) (list x (list 'quote x))))
"David B. Lamkins" wrote:
*snip*
> You're on the right track with find-if. You need to specify a test function
> that returns true if the latitude and longitude of a city in the list
> matches the latitude and longitude for which you're searching.
>
> (find-if #'(lambda (city)
> ;; return true if city latitude and longitude
> ;; match the search criteria
> [body of function])
> cities)
>
> The body of the function can reference parameters of the enclosing function
> to get the search latitude and longitude.
>
> If this is part of a real program, and not a homework exercise, I'd suggest
> that you consider other representations. A structure would give more
> efficient access to city fields than the assoc you're now using. And you
> can certainly do better than linear search.
>
> --
> David B. Lamkins <http://www.teleport.com/~dlamkins/>
>
> ((lambda (x) (list x (list 'quote x)))
> '(lambda (x) (list x (list 'quote x))))
Ok, got it. Thanks much. And yeah, this is part of a homework
exercise. I figured it didn't hurt to ask since I had already figured
out a way to do what needed to be done and was just looking for a better
way (a shame, too... I was having fun recursing everything. :) I'll
have to check out structures here if I get time... my relationship with
Lisp consists of yesterday and today, so there is much yet that I am not
aware of.
Thanks again!
--
Jason Holmes
1. You should always state up front if the problem is for homework.
2. If a program "blows up" because of poor complexity behavior (big-O
stuff, etc., ask your teacher), don't just assume that you can fix the
problem by making a small adjustment to single key algorithm. That
MIGHT (and often does) do the trick, but you can often do MUCH better by
restructuring the problem entirely.
For example, if you are searching for a desired property from a huge set
of data, making minor changes to a british-library search isn't going to
be nearly as big a win as changing the organization of data so that you
can use a different kind of search entirely. For example, in this
problem, think about how you could organize your list of millions of
'cities' so as to have them "pre-searched" (i.e., partitioned) into more
manageable sections. (This is what David Lamkins was talking about at
the end of his message.)
3. Never take failure for granted. For the small data set you show, it
is not obvious to me why a quick-and-dirty brute-force hack should blow
up. Find out why. There might be something else going on. Use the
backtrace and/or the trace utility.
Jason Holmes wrote:
>
> Greetings.
>
> So I'm working on a little project and I've written a bunch of functions
> to manipulate a data structure (I've called it 'cities') that looks
> something like this:
>
> (((CITY "BELLINGHAM") (LATITUDE (48 48 0)) (LONGITUDE (122 25 0))
> (NEIGHBORS (("SEATTLE" 90))))
> ((CITY "EL PASO") (LATITUDE (31 47 0)) (LONGITUDE (106 29 0))
> (NEIGHBORS (("LAS CRUCES" 37))))
> ((CITY "GREAT FALLS") (LATITUDE (47 29 33)) (LONGITUDE (112 18 23))
> (NEIGHBORS (("HELENA" 87))))
> ((CITY "PORTLAND") (LATITUDE (45 31 6)) (LONGITUDE (122 40 35))
> (NEIGHBORS (("HERMISTON" 181) ("EUGENE" 114) ("SEATTLE" 172))))
> ((CITY "SEATTLE") (LATITUDE (47 36 32)) (LONGITUDE (122 40 35))
> (NEIGHBORS (("BELLINGHAM" 90) ("ELLENSBURG" 107) ("PORTLAND" 172)))))
>
> Everything works ok, except that almost everything is recursive and
> sometimes the recursion gets so large that the Lisp Interpreters die (at
> least gcl and Allegro did... the snap of clisp I have installed has
> other problems.)
>
> For example, to find a city of a specified latitude and longitude, I
> have the following functions:
>
> (defun get-cityname-of-coordinates (cities latitude longitude)
> (cond ((endp cities) nil)
> ((and (equal (get-latitude-of-first cities) latitude)
> (equal (get-longitude-of-first cities) longitude))
> (get-cityname-of-first cities))
> (t (get-cityname-of-coordinates (rest cities) latitude
> longitude))))
>
> (defun get-latitude-of-first (cities)
> (second (assoc 'latitude (first cities))))
>
> (defun get-longitude-of-first (cities)
> (second (assoc 'longitude (first cities))))
>
> (defun get-cityname-of-first (cities)
> (second (assoc 'city (first cities))))
>
> I would call (get-cityname-of-coordinates cities '(10 10 10) '(10 10
> 10)) and it would call the other functions and itself until successful.
>
> Does anyone know of an easy way to make get-cityname-of-coordinates into
> an iterative function? I was playing around with find-if's but have not
> yet gotten anywhere.
>
> Thanks!
>
> --
> Jason Holmes