I'm back to LISP after having been away for a long, long time (it's
_hard_ to break the SETQ habit :). BTW, this is not homework of any
sort.
Anyway, I have a function in my current program which is a planner of
sorts. It takes a list of stuff as a parameter and builds lists of
candidates for action.
Pseudo-code:
(defun chain-stuff (stuff-list start end level)
(if (<= start end)
(dolist (stuff stuff-list)
(when (eligible-p stuff start)
(chain-stuff stuff-list (+ start 5) end
(append level stuff))
)
) level
)
)
What I'd like to return is a list of the accumulated lists (which
would be "level" at the if-else case), but can't think of a way to
do it other than appending to something outside the function's scope.
(Which I viscerally recognize as abhorrent...:)
Thanks in advance,
Jeffrey Katcher
Jeff Katcher wrote:
> I'm back to LISP after having been away for a long, long time (it's
> _hard_ to break the SETQ habit :). BTW, this is not homework of any
> sort.
Don't forget to fill in
http://alu.cliki.net/The%20Road%20to%20Lisp%20Survey .
> )
> ) level
> )
> )
Do not put close parentheses on a line by themselves. Contrary to the
holy wars concerning the placement of curly braces in other languages,
this is something Lispers are unanimous about.
> What I'd like to return is a list of the accumulated lists (which
> would be "level" at the if-else case), but can't think of a way to
> do it other than appending to something outside the function's scope.
> (Which I viscerally recognize as abhorrent...:)
I'm not sure what your code is supposed to do, but I suspect you want
(return-from chain-stuff level)
Be warned, however, that the append in your code does not modify level
in the way I think you want it to.
Sebastian Stern
"Freedom is the freedom to say (= (+ 2 2) 4). If that is granted, all
else follows."
Sebastian Stern wrote:
[Jeff Katcher:]
> > )
> > ) level
> > )
> > )
[Sebastian:]
> Do not put close parentheses on a line by themselves. Contrary to the
> holy wars concerning the placement of curly braces in other languages,
> this is something Lispers are unanimous about.
Well, at least the second of Jeff's lines quoted above
doesn't have a close-paren on its own line, so that must
be good, right? :-)
--
Gareth McCaughan
.sig under construc
·········@yahoo.com (Jeff Katcher) writes:
> I'm back to LISP after having been away for a long, long time (it's
> _hard_ to break the SETQ habit :).
Welcome back. And please, try at least as hard to lose the dangling
parens. Indentation is the visual code-block delimiter in Lisp, and
the parens merely tell your editor how to indent things. And a
paren-aware editor /is/ essential.
> Anyway, I have a function in my current program which is a planner
> of sorts. It takes a list of stuff as a parameter and builds lists
> of candidates for action.
I wasn't able to understand much from your pseudo-code, but from this
description it seems to me that what you'd want is something like
(remove-if (complement #'eligible-p) stuff-list :start start :end end)
Or, if you need more control:
(loop for stuff in stuff-list as position upfrom 0
when (and (eligible-p stuff)
(blabla stuff start))
collect (figure-out-action stuff position))
Perhaps if you explain why this doesn't work, we can help you more.
--
Frode Vatvedt Fjeld
Jeff Katcher wrote:
> I'm back to LISP after having been away for a long, long time (it's
> _hard_ to break the SETQ habit :). BTW, this is not homework of any
> sort.
>
> Anyway, I have a function in my current program which is a planner of
> sorts. It takes a list of stuff as a parameter and builds lists of
> candidates for action.
>
> Pseudo-code:
> (defun chain-stuff (stuff-list start end level)
> (if (<= start end)
> (dolist (stuff stuff-list)
> (when (eligible-p stuff start)
> (chain-stuff stuff-list (+ start 5) end
> (append level stuff))
> )
> ) level
> )
> )
Can you add a little more about what you want to achieve? I /think/ the
pseudocode is off enough to obscure that. Supplying a sample input and
desired output would help a lot.
Suppose eligible-p is '>, and we call chain-stuff thus:
(chain-stuff '(5 10 3 9 16 25 3) 5 10 nil)
Do you want back?:
'((10 9 16 25)
(23 16 25))
btw, the deepest level of call chain-stuff returns the accumulated list
passed to it as the level parameter, but higher levels discard the
return value of recursive calls.
also, you have (append level stuff). Unless stuff is a list you want
joined with the level list as if by concatenation, you want:
(append level (list stuff))
But it is probably better at this point to get straight what are you
attempting.
kt
--
http://tilton-technology.com
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Your Project Here! http://alu.cliki.net/Industry%20Application
Adding to my own thread...
I've fixed my code and have it working properly. The main issue was: in a
deeply recursive function, I was having trouble getting the accumulation of
return values right. Of course success lead to another issue...
Everything is fine for small and medium sized data sets, but there's a
combinatorial explosion (the only phrase that comes to mind) for large
ones that exceeds the limits of my LISP systems. It seems like the proper
Lisp esthetic is to pass the input to the function and get the accumulated
results in return. In C, for example, I could select the valuable alternatives
at the deepest recursion level and hand them to some external data structure.
This avoids the death by return accumulation that I'm seeing. Of course I could
implement the same sort of thing in Lisp but it would be ugly and un-Lisp-like.
How does one balance the native style with the need to solve the problem?
Jeff
P.S. Consider me properly chastened in regard to dangling parenthesis.
·········@yahoo.com (Jeff Katcher) writes:
> Adding to my own thread...
>
> I've fixed my code and have it working properly. The main issue was: in a
> deeply recursive function, I was having trouble getting the accumulation of
> return values right. Of course success lead to another issue...
>
> Everything is fine for small and medium sized data sets, but there's a
> combinatorial explosion (the only phrase that comes to mind) for large
> ones that exceeds the limits of my LISP systems. It seems like the proper
> Lisp esthetic is to pass the input to the function and get the accumulated
> results in return. In C, for example, I could select the valuable alternatives
> at the deepest recursion level and hand them to some external data structure.
> This avoids the death by return accumulation that I'm seeing. Of course I could
> implement the same sort of thing in Lisp but it would be ugly and un-Lisp-like.
> How does one balance the native style with the need to solve the problem?
As Kenny suggests, passing a function to your traversal function is a
standard way of dealing with this issue, if I understand it correctly.
You might find it interesting to see how existing Lisp-based planners
do things; for example, take a look at the function bestf-search in
UCPOP, which takes as input goal-p, among other arguments. Such
functions may be able handle bookkeeping without requiring that
enormously long lists of candidate solutions be consed up to be
immediately discarded (though depending on your search control, this
might be inevitable anyway.)
--
Rob St. Amant
http://www4.ncsu.edu/~stamant
·········@yahoo.com (Jeff Katcher) writes:
> Adding to my own thread...
>
> I've fixed my code and have it working properly. The main issue was: in a
> deeply recursive function, I was having trouble getting the accumulation of
> return values right. Of course success lead to another issue...
Is this still the `chain-stuff' problem?
(defun chain-stuff (stuff-list start end level)
(if (> start end)
level
(dolist (stuff stuff-list)
(when (eligible-p stuff start)
(chain-stuff stuff-list (+ start 5) end
(append level stuff))))))
This is baffling, but it sort of looks as if you want something like
this:
Given an unordered list of elements and a start and end, segregate
the elements and return a bunch of lists, one list for each
subrange.
So suppose that `eligible-p' were:
(defun eligible-p (item start)
(and (>= item start)
(< item (+ start 5))))
then (chain-stuff '(18 10 24 12 5 3 27 17 11 22 13 19 7 6 33) 5 25)
=> '((5 7 6)
(10 12 11 13)
(18 17 19)
(24 22)
(27))
Elements less than 5 and greater than 30 are ignored, and the others
are grouped by fives.
Is this sort of what you are looking for?
A simple solution is this:
(defun chain-stuff (stuff start end)
(if (> start end)
;; if nothing is in the range, return nothing.
'()
(do ((tail stuff (cdr tail))
;; extend goodies with the eligible stuff.
(goodies '() (if (eligible-p (car tail) start)
(cons (car tail) goodies)
goodies)))
((null tail)
(cons goodies
(chain-stuff stuff (+ start 5) end))))))
You go over the entire list once for each group. Not good if you have
a lot of groups and a big list.
One thing that will help is to remove elements from the list once
you decide where they go.
(defun split-list (items predicate)
(let ((winners '())
(losers '()))
(dolist (item items)
(if (funcall predicate item)
(push item winners)
(push item losers)))
(values (nreverse winners) (nreverse losers))))
(defun chain-stuff (stuff start end)
(if (> start end)
;; if nothing is in the range, return nothing.
'()
(multiple-value-bind (goodies remaining)
(split-list stuff (lambda (item)
(eligible-p item start)))
(cons goodies (chain-stuff remaining (+ start 5) end)))))
This is slightly better because you are reducing the size of the list
on each iteration, but it isn't much better because you still examine
the later elements many times.
If you can sort the list, you can do it in O(n + divisions + n log n) time.
If you know what the divisions are beforehand, you can do it in
O(n * log (divisions))
It's hard to say based on so little information, though.
> How does one balance the native style with the need to solve the problem?
Well, solving the problem is usually what you get paid for, but if you
find yourself fighting with the style, that often means that you're
trying to shoehorn the wrong solution into the language. Starting
from `what do I want to accomplish, and how would I prefer to interact
with the solution' is a good idea.
Jeff Katcher wrote:
> Adding to my own thread...
>
> I've fixed my code and have it working properly. The main issue was: in a
> deeply recursive function, I was having trouble getting the accumulation of
> return values right. Of course success lead to another issue...
>
> Everything is fine for small and medium sized data sets, but there's a
> combinatorial explosion (the only phrase that comes to mind) for large
> ones that exceeds the limits of my LISP systems. It seems like the proper
> Lisp esthetic is...
While I admire your appreciation of the need to do in rome as romans do,
I have this sense that you are putting the cart before the horse. from
what little I can understand of this combinatorial explosion, it sounds
as if you are simply missing a simple technique (see below), so there is
no need to worry about high-flying concerns such as Lisp aesthetics.
to pass the input to the function and get the accumulated
> results in return. In C, for example, I could select the valuable alternatives
> at the deepest recursion level ...
Good idea. So pass along a first-class function to your exploding
traversal function and let it pick out just the ones it likes:
(let (best-of)
(exploding-traverse
entire-universe
(lambda (node)
(when (hellasweet-p node)
(pushnew node best-of))))
(nreverse best-of))
kt
and hand them to some external data structure.
> This avoids the death by return accumulation that I'm seeing. Of course I could
> implement the same sort of thing in Lisp but it would be ugly and un-Lisp-like.
It might be easier on the learning curve if you do what you anticipate
will be judged ugly and see what happens. You can offer a disclaimer "I
know this is a C approach, but..."
> How does one balance the native style with the need to solve the problem?
Lisp is a multi-paradigm, highly practical language. Just solve the
problem and don't worry about native style--we'll nail you on that fast
enough if you post the code.
>
> Jeff
>
> P.S. Consider me properly chastened in regard to dangling parenthesis.
See?
:)
kt
--
http://tilton-technology.com
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Your Project Here! http://alu.cliki.net/Industry%20Application