Dirt <p...@inam3.com> writes: > I am trying to do this recursively but I am guessing I am way off > because I get a stack overflow. What I am trying to say in my code > below is:
> If the expression is a list, call the function again with the > cdr of the list, otherwise it is an atom so cons it to a list.
Now try to imagine what your function does with an ordinary list, and where it gets stuck. Understanding this will not give you a solution to your original problem, but you will understand why you get a stack overflow.
[ please look at how other Common Lisp programmers indent and present their code. parentheses are _not_ visually significant, although they are very syntactically significant, in Lisp source code. don't make them stand out -- please -- you're code is so ugly it's hard to help you with it. ]
* Dirt <p...@inam3.com> | I am trying to "unravel" a list, but with little luck. I wish to take a | list such as: | | (a (b c (d e)) f) | | and create a new list that looks like one top level list: | | (a b c d e f)
this is normally called "flattening" a list.
| I am trying to do this recursively but I am guessing I am way off because | I get a stack overflow. What I am trying to say in my code below is: | | If the expression is a list, call the function again with the cdr of the | list, otherwise it is an atom so cons it to a list.
what you wish to do is to move each element of each list you encounter onto a new list. I'll try to show you with slightly more modern Common Lisp that you're using:
(defun flatten (list) (loop for element in list if (listp element) nconc (flatten element) else collect element))
if you actually _need_ recursion, which will only waste space and time, you should be able to unravel this iterative solution easily. in my not so humble opinion, being able to think recursively is very valuable, the second most valuable ability you can have, beaten only by knowing _when_ to use recursion.
incidentally, this function considers an empty list a list of no elements while you might want NIL to be a separate element in the resulting list.
Erik Naggum <e...@naggum.no> writes: > (defun flatten (list) > (loop for element in list > if (listp element) nconc (flatten element) > else collect element))
> if you actually _need_ recursion, which will only waste space and time, > you should be able to unravel this iterative solution easily. in my not > so humble opinion, being able to think recursively is very valuable, the > second most valuable ability you can have, beaten only by knowing _when_ > to use recursion.
Learning Lisp in an academic environment (as I did) tends to breed distrust of looping constructs. (Especially considering that Common Lisp is not the Lisp dialect of choice for teaching purposes.) I agree that your solution above is simple and efficient, but I think the original poster's wish was to have a solution that utilizes as few ``advanced'' features of CL as possible. (I seriously doubt that his class covered loop at this point :) That said, here is a purely recursive Scheme-like solution:
Erik Naggum <e...@naggum.no> writes: > what you wish to do is to move each element of each list you encounter > onto a new list. I'll try to show you with slightly more modern Common > Lisp that you're using:
> (defun flatten (list) > (loop for element in list > if (listp element) nconc (flatten element) > else collect element))
> if you actually _need_ recursion, which will only waste space and time, > you should be able to unravel this iterative solution easily. in my not > so humble opinion, being able to think recursively is very valuable, the > second most valuable ability you can have, beaten only by knowing _when_ > to use recursion.
> incidentally, this function considers an empty list a list of no elements > while you might want NIL to be a separate element in the resulting list.
> #:Erik
Actually your solution is recursive. Look that in your loop construct you call (recursively) FLATTEN depending on the type of ELEMENT. This is clearly a case of recursion.
The use of a loop construct if not sufficient to say that the algorithm is iterative. I guess I should clearly define the concept of iteration/recursion. Seeing a function calling itself in its body is sometime a good hint for recognizing recursion.
Flattening a list cannot be done without some kind of recursion, be it explicit (a function calling itself) or implicit (building some intermediate stack to simulate recursion).
Has someone a truly iterative solution for this ? I know you could CPS the program and end up with a tail recursive solution. But this does not count as you are implicitly building a call stack.
* Pierre De Pascale <d...@siemens.ch> | Actually your solution is recursive. Look that in your loop construct you | call (recursively) FLATTEN depending on the type of ELEMENT. This is | clearly a case of recursion.
you're right, of course. the recursion that I find silly, and therefore reacted to, is using recursion to traverse lists, or recursing on the CDR. for the sake of argument, I ignored the recursion on the CAR. I think you made a good point for why that shouldn't be done.
Erik Naggum <e...@naggum.no> writes: > (defun flatten (list) > (loop for element in list > if (listp element) nconc (flatten element) > else collect element))
> if you actually _need_ recursion, which will only waste space and time, > you should be able to unravel this iterative solution easily.
Hmm, isn't your code above already recursive? Actually, it is both recursive and iterative: it iterates over the elements of a list and recurses when it encounters a nested list.
Constantine Vetoshev wrote: > I think the > original poster's wish was to have a solution that utilizes as few > ``advanced'' features of CL as possible. (I seriously doubt that his > class covered loop at this point :) That said, here is a purely > recursive Scheme-like solution:
Maybe Erik's intention was to make Dirt think about a solution rather than to help him cheat.
In article <wn901fv0mb....@siemens.ch>, Pierre De Pascale <d...@siemens.ch> wrote:
>Flattening a list cannot be done without some kind of recursion, be it >explicit (a function calling itself) or implicit (building some >intermediate stack to simulate recursion).
>Has someone a truly iterative solution for this ? I know you could CPS >the program and end up with a tail recursive solution. But this does >not count as you are implicitly building a call stack.
Well, the following is pretty close to iterative, if you allow for destroying the input-tree in-place:
(defun nflatten (list) "Flattens LIST and all its sublists. Destructive!" (loop with point = list for item = (first point) while point do (if (consp item) ;;; lift car, splice in cdr (setf (car point) (car item) (cdr point) (nconc (cdr item) (cdr point))) ;;; else move on (setf point (rest point)))) list) -- -------------------------------------------------------------------------- Bernhard Pfahringer, OeFAI http://www.ai.univie.ac.at/~bernhard/ -------------------------------------------------------------------------- iSteve: i is iCeo in iApple. You'll be iified. iResistance is inVain.
>Maybe Erik's intention was to make Dirt think about a solution rather >than to help him cheat.
How is asking for help cheating? I attempted to construct a solution, then posted that, asking for guidance. I did not once ask for anyone here to do my work.
I find it quite discouraging to see comments such as yours. Is this not a learning enviroment? Don't ask!! Don't learn!! Your Bad!!!
There are two separate issues with your code. The first one explains why you get a stack overflow. Stack overflows usually result when your code goes into an infinite recursion.
(listp NIL) => T (cdr NIL) => NIL
NIL is the empty list and the first clause of your cond will recursively call itself on successive CDRs of the input list until it reaches the end of the list (NIL), and then it will repeatedly call itself on NIL until you run out of stack space.
The second problem is that there is no assembly of the parts of the solution from the recursive call to the function. I should also point out that there is also no processing of the CAR of the input argument when it is a list.
One way to understand what is happening with your code is to step through a simple example of the input by hand (or using a combination of doing it by hand and typing things in) and seeing what happens.
For example, start with '((a) b) as input. (listp '((a) b)) => T (cdr '((a) b)) => (B) ;; recurse now (listp '(b)) => T (cdr '(b)) => NIL ;; recurse now (listp NIL) => NIL (cdr NIL) => NIL ;; recurse now
etc.
This will both help you understand what is happening as well as give you some clues as to how to change your function to get the results that you want.
-- Thomas A. Russ, USC/Information Sciences Institute t...@isi.edu
Dirt wrote: > How is asking for help cheating? I attempted to construct a solution, > then posted that, asking for guidance. I did not once ask for anyone > here to do my work.
> I find it quite discouraging to see comments such as yours. Is this > not a learning enviroment? Don't ask!! Don't learn!! Your Bad!!!
> Your comments are unwarranted and unappreciated.
* Dirt <p...@inam3.com> -> Robert Monfera | I find it quite discouraging to see comments such as yours. Is this | not a learning enviroment? Don't ask!! Don't learn!! Your Bad!!!
attempting to use USENET for homework has long traditions and only marginally shorter traditions of rebuke, hostile reactions, and general ill feelings in return. when you ask for help in solving really simple problems that any good textbook alredy explains well, you're putting yourself in the homework category, whether you are doing homework on the Net or not. defensive reactions _reinforce_ that impression strongly.
if you want to learn something from the net, be prepared to listen to _all_ the answers you get. criticism is always well intended at first, but the stupid, destructive people who insist on defending themselves whenever something they do is criticized and on attacking people "back" who never actually attacked them, make this a very strenous medium for such people. you see, people who are attacked this way are _not_ going to give you any benefit of the doubt: you are clearly guilty of hostile activities towards others, and if you respond strongly to such attacks, so will everybody else. if you feel unfairly attacked, consider the fact that you attack others unfairly on purpose when you attack them for having behaved badly towards you. in short, stupid people escalate a normal process of mild correction and attitude readjustment into flames and out-and-out hostilities. the solution is obvioulsy to get rid of the stupid people, but until we can do that, all we can do is ask people to stop behaving stupidly.
instead of getting worked up over criticism you don't understand, strive to understand what made it arise in the first place. most of the time, it has simple, straightforward reasons that you can easily change, and which it would be incredibly stupid of you not to change, because that means you don't listen and really _are_ stupid, like one particular dude here who never listens to anything he doesn't already agree to, and who accuses those who try to readjust his attitude of being psychopaths and maniacs, which only proves that he's just as retarded as they think he is.
incidentally, this is not really a learning environment. it's really an environment for sharing ideas and experiences with others. the helping and _learning_ part is the result of motivating those who have something that you need to share it. you don't do that by looking like you're doing homework on the Net. you can't change that by accusing people of holding stupid attitudes like "Don't ask!! Don't learn!! Your Bad!!".
so wise up, and behave like you're asking and learning and taking part in this environment, not just exploiting it and wasting people's time by not doing your homework _between_ articles you post to this forum. note the "behave like" -- nobody cares what you actually _do_ or _think_, as they can't see that in your articles and can't react to it unless they make the grave error of pretending to see people's thoughts across the net. (do notice how you make this mistake.)
Erik Naggum <e...@naggum.no> writes: > attempting to use USENET for homework has long traditions and only > marginally shorter traditions of rebuke, hostile reactions, and general > ill feelings in return. when you ask for help in solving really simple > problems that any good textbook alredy explains well, you're putting > yourself in the homework category, whether you are doing homework on the > Net or not. defensive reactions _reinforce_ that impression strongly.
etc.
This would have been an appropriate response if Dirt had asked a typical
"How do I <insert easily recognizable textbook problem> ?"
But that's not what he did.
He proposed a solution, asked for comments, got some, and responded intelligently to those. He never tried to hide the fact that he was doing homework, in fact it was obvious that he was working very hard at it.
* Jon K Hellan <hel...@acm.org> | This would have been an appropriate response if Dirt had asked a | typical
sigh.
Dirt's reaction would have been appropriate if anyone had actually accused him of any wrong-doing. I'm trying to tell him (and now you), that you have to _listen_ to what people are saying, not just react to what _you_ feel. please heed my advice, or heed my secondary advice: shut up if you have nothing to contribute.
| I think Dirt should be welcome on the net.
your implication that somebody thinks he is not is insulting. quit it.
I would have agreed with Erik a few years ago. I still think a good amout of learning results from frustration and [re-]reading not-so-well presented material in solitude, but "Dirt" did use the resources available to him appropriately. Whether he would have learned more had he let himself be frustrated and figure it out by himself seems to be a moot point in this day and age. He had the right approach to get people's time and attention, which in itself might be an equally valuable skill as extracting crucial insights from lectures and books. As a bonus he also got filled in on eq vs. = issues for number comparison which apparently his teacher failed to clarify.
The interaction was not inaproppriate, it was just good fruitful use of modern resources. His next step is learning to complement his skill in tapping into this knowledge with the acquisition of thicker skin for on-line disapproval. I think this newsgroup is up to helping him with that also!
> Well, the following is pretty close to iterative, if you allow > for destroying the input-tree in-place:
> (defun nflatten (list) > "Flattens LIST and all its sublists. Destructive!" > (loop with point = list > for item = (first point) > while point > do > (if (consp item) > ;;; lift car, splice in cdr > (setf (car point) (car item) > (cdr point) (nconc (cdr item) (cdr point))) > ;;; else move on > (setf point (rest point)))) > list)
OUCH! This is one of those places where the cure is worse than the disease! This IS code that illustrates that you can do anything iteratively that you can do recursively, as long as you are willing to ignore style, clarity, and cleanliness. Very interesting, but it makes my brain hurt just looking at it. I guess Lisp is better for allowing you to do these things, but sheesh... If I saw this code in a student's assignment, I'd probably (a) barf and (b) wonder if I'd been teaching them anything.
It's not eq to the 'How do I?' question, but it is much closer to this than to an almost-finished, hard-fought solution on which substantial _thinking_ time was spent and which needs a small 'gotcha' type of correction.
> He never tried to hide the fact that he was doing homework [...]
More accurately, he didn't say it was not homework.
Erik had a valid point about Dirt utilizing other people's time instead of opening a textbook or just doing a simple search on what's available on the web. It does not matter what we think about it though, because there will always be people doing it, and it's everyone's own business to help them. Also, there is a blurred line between helping and solving homework (strictly speaking, the very point of homework is to make people think hard, sweat and struggle solitarily in an effort to pump the way of thinking into students' brains).
In response to postings from people offering subtle help, someone posted the final, recursive solution off the bat. There is no way of _making_ someone adept at attacking problems with recursive code or divide et impera methods just by solving their homework. Dirt may or may not have skipped the solution, but it definitely let him shortcut the gist of the homework assignment (for which there is a word invented).
>>>>> "RM" == Robert Monfera <monf...@fisec.com> writes:
[...] RM> Right, depending on the meaning of fruitful. In an RM> educational setting the distinguished meaning may be different RM> from what you have in mind.
Hmm. I kind of follow this, but not completely. I was using 'fruitful' in the sense that he _did_ learn something and possibly more than he would have had he not posted.
RM> Studying and 'easy' are RM> oxymorons. If they weren't, someone would be able to redefine RM> the meaning of studying simply by adding hard work to the RM> recipe.
In my personal experience with my brief and not-so-successful attepts at both academic teaching and 'training' I have concluded that unless one has a semi-gifted teacher, learning of novel concepts happen _by accident_. Happily I was better at learning, but I could certainly sense when I was being succesfully taught, and when I was stumbling upon enlightenment. As far as I can see this happy accident of 'getting it' usually happens after long hours of dead-ends and frustration. I tend to infer a vague causal connection between the two and thus do value the hard work part of learning. Accepting and understanding the hard part of learning as a necessary evil is valuable in itself and ought to be learned. Having said that, I also think one should not discount the value of a nudge here, a hint there also as practical means of getting people to the light. Maybe the ng did go a bit further than I first thought in that last regard though.
RM> 'Assisted homework solving' wasn't made possible by the advent RM> of Internet; in the past, students mainly interested in the RM> deliverable could easily ask around and/or copy it among their RM> classmates (practicing their interpersonal skills :-),[...]
Of course, but presumably getting help from a set of skilled people spread all over the world is in an altogether different league than simple collective homework attempts among peers. People could always ask others in physical proximity, but it is only recently that they could ask questions to a concentrated collection of experts in the field of their problem without leaving their desks. _That_ is what is new and I think being able to tap into that is a very worthwhile skill.
RM> ... Learning and other RM> cognitive processes of the brain remained the same, never mind RM> the new channels. Even Gutenberg did not manage to do away RM> with the sweat on students' forehead!
I think we are in agreement in general but disagreeing on our perception of how much of the learning process he went though before posting. I am willing to concede that maybe I was quick to assume enough energy was expended before posting. I do not agree with the (possibly tongue-in-cheek) Gutenberg analogy, unless Gutenberg also managed to press the authors and their peers into the books.
RM> ... If someone thinks he can just RM> turn to the web for a quick solution during school and work, RM> then what's the point of attending the course in the first RM> place?
Actually this question is not rhetorical! What indeed? Unless, of course, one has a good teacher which I am not convinced can be replaced.
RM> By approving his way of problem solving, you may give RM> Dirt a false sense of security about its essence.
I intended no such thing! I hope Dirt understands that. What should be understood is that Usenet, without the wherewithall to filter it, is useless and might be harmful. You may break your car by reading rec.auto newsgroups, you may damage your file system if you believe the linux newsgroups, and we just may make sure you end up igorant and out of your tuition money at c.l.l.!
[...] RM> This skin thickening thing may work even if he just thinks he RM> was nailed down! (Dirt with thick skin?!?!)
> The interaction was not inaproppriate, it was just good fruitful use of > modern resources.
Right, depending on the meaning of fruitful. In an educational setting the distinguished meaning may be different from what you have in mind. Studying and 'easy' are oxymorons. If they weren't, someone would be able to redefine the meaning of studying simply by adding hard work to the recipe.
'Assisted homework solving' wasn't made possible by the advent of Internet; in the past, students mainly interested in the deliverable could easily ask around and/or copy it among their classmates (practicing their interpersonal skills :-), while keeping the risk of getting caught lower. Learning and other cognitive processes of the brain remained the same, never mind the new channels. Even Gutenberg did not manage to do away with the sweat on students' forehead!
The importance of learning has always been a distinguished part of our value system (except dark ages), and it is especially true in the information society, which has a lower need for dock workers etc.. If someone thinks he can just turn to the web for a quick solution during school and work, then what's the point of attending the course in the first place? By approving his way of problem solving, you may give Dirt a false sense of security about its essence.
> His next step is learning to complement his skill > in tapping into this knowledge with the acquisition of thicker skin for > on-line disapproval. I think this newsgroup is up to helping him with > that also!
This skin thickening thing may work even if he just thinks he was nailed down! (Dirt with thick skin?!?!)
I appreciate your thoughts and just like to hang around for a little more.
Bulent Murtezaoglu wrote: > In my personal experience with my brief and not-so-successful attepts > at both academic teaching and 'training' I have concluded that unless > one has a semi-gifted teacher, learning of novel concepts happen _by > accident_.
I was often thinking of learning as a way to _force_ the brain to compress facts and information on a subject. The better the compression, the higher the chance that the essence of the subject is captured. What is difficult for me to see is how this compression can happen without pressure. This pressure may come from various sources. Going to school or doing certain types of jobs is an acceptance of subjecting oneself to pressure. Another source is internal motivation. Accidents only happen if there is velocity, weight and drag. If a piece of molten plastic drops into a mint form, it may accidentally fill all the fine details of the mint, but it is standard practice to make it happen with pressure. Also, accidental great discoveries were usually preceded by years or tens of years of hard and possibly fruitless work.
> Happily I was better at learning, but I could certainly > sense when I was being succesfully taught, and when I was stumbling > upon enlightenment. As far as I can see this happy accident of > 'getting it' usually happens after long hours of dead-ends and > frustration. I tend to infer a vague causal connection between the > two and thus do value the hard work part of learning.
We say the same here, except maybe the strength of correlation.
> [...] getting help from a set of skilled people > spread all over the world is in an altogether different league than > simple collective homework attempts among peers. [...] > _That_ is what > is new and I think being able to tap into that is a very worthwhile > skill.
Yes, it is definitely more efficient, not only because of the global pool of possible responders but also their often deep knowledge. c.l.l. is not a moderated learning channel though, and the solution is usually given away quickly before seeing working code from the OP. As for the skills required to post a question to a newsgroup, and its relative weight compared to the skill of systematic thinking or brainstorming in a team, our opinion seemingly differs :-)
> I do not agree with the > (possibly tongue-in-cheek) Gutenberg analogy, unless Gutenberg also > managed to press the authors and their peers into the books.
In fact some thinkers of the time were worried that people will lose their memory, because the mass availability of books eliminates the need to remember. It was partially justified, as these days parents have the option to tell tales from books rather than from memory, amongst more beneficial examples. Even though printing books was a revolution quite comparable with the current Internet revolution, the need to use our brains has only increased since then as well as the time spent in the classroom.
And _your_ suspicion is not rhetorical either; in a sense (or 'in essence'?) Gutenberg did press the authors into the book, while peers could share thoughts via side notes!
Erik Naggum wrote: > incidentally, this is not really a learning environment. it's really an > environment for sharing ideas and experiences with others. the helping > and _learning_ part is the result of motivating those who have something > that you need to share it.
Actually, I quite agree with Erik. But it is always interesting to examine the diversity of programming styles of those who provide solutions even to simple "homework-like" problems, because they raise style issues.
If I have not missed anything, no one suggested (yet) the textbook-based "flatten" function using an accumulator:
Incidentally, I found no detectable improvement in performance (on a real-world program) when using it instead of the "standard" tree-recursive version (this was some time ago, but I justed checked again with Allegro 5.0).
Marc Cavazza <M.Cava...@bradford.ac.uk> writes: > If I have not missed anything, no one suggested (yet) the textbook-based > "flatten" function using an accumulator:
A couple of possible reasons why no-one has proposed this:
- Exposing your internal accumulator via the external interface of your function is not only very ugly, it's also error prone and invites mis-use, which will later make it nearly impossible to change the implementation of flatten!
A better implementation would IMHO use an internal helper function:
This has the additional benefit that many compilers can make more agressive optimizations on flatten-internal (no optional args, and especially, not globally visible, i.e. you don't have to go through the value cell of the symbol, and it can't be redefined):
On CMUCL with (optimize (speed 3)) the two versions differ markedly:
10000 times flatten-bad of '((a b (c d) e) f (g (h (i)))) Evaluation took: 1.27 seconds of real time 0.93 seconds of user run time 0.08 seconds of system run time [Run times include 0.3 seconds GC run time] 0 page faults and 9975800 bytes consed.
vs.
10000 times flatten of '((a b (c d) e) f (g (h (i)))) Evaluation took: 0.09 seconds of real time 0.05 seconds of user run time 0.03 seconds of system run time 0 page faults and 1043568 bytes consed.
> Incidentally, I found no detectable improvement in performance > (on a real-world program) when using it instead of the "standard" > tree-recursive version (this was some time ago, but I justed > checked again with Allegro 5.0).
- Outside of textbooks, simple flattening is usually a very rare operation: Either you are traversing a tree or graph structure and collecting the results of applying some operation to certain nodes (in which case you'll try to combine the "flattening" operation with the calculation), and/or you care about the order of traversal, and/or you don't want to visit/process every node, and/or you are using a different internal representation instead of lists, etc.
So few people spend time on writing flatten, and the few that do (outside academic exercises) won't try to optimize their implementation, because it won't matter. If it does matter, then you should either think about using other representations, caching, or any other more advanced technique to speed up your program. Optimizing flatten (even algorithmically) is IMHO a case of premature and wrong optimization...
Regs, Pierre.
-- Pierre Mai <p...@acm.org> PGP and GPG keys at your nearest Keyserver "One smaller motivation which, in part, stems from altruism is Microsoft- bashing." [Microsoft memo, see http://www.opensource.org/halloween1.html]
> - Exposing your internal accumulator via the external interface of > your function is not only very ugly, it's also error prone and > invites mis-use, which will later make it nearly impossible to > change the implementation of flatten!
In general, I find such use of 'labels' ugly.
My personal taste of style tells me that in simple cases where the 'real' parameters are few and fixed, using optional parameters for accumulating values is a good solution.
'labels' clutters the code and I don't like to use it just to 'hide' functions, but would like to reserve it to functions which need the lexical environment of the enclosing function.
Often, using a globally defined auxiliary function (with a package- internal symbol as a name, of course) makes code easier to read than defining too voluminous functions with 'labels'-functions.
So my personal style guide is:
- Use labels and flet for local functions which need the lexical environment of the enclosing function.
- In some cases, you may use optional parameters for accumulating values (but only in really simple cases - I don't want to argue whether the case at hand is a good example)
- Otherwise, use auxiliary functions. In general, don't be afraid to have a lot of top-level functions. It makes your code better suited for small dynamic updates.
I'd like to hear other peoples opinion on this! -- (espen)
"Pierre R. Mai" wrote: > Marc Cavazza <M.Cava...@bradford.ac.uk> writes:
> > If I have not missed anything, no one suggested (yet) the textbook-based > > "flatten" function using an accumulator:
> A couple of possible reasons why no-one has proposed this:
> - Exposing your internal accumulator via the external interface of > your function is not only very ugly, it's also error prone and > invites mis-use, which will later make it nearly impossible to > change the implementation of flatten!
That's an interesting comment (BTW, I have diplomatically omitted the name of the - quite famous - Textbook :-) and the optimisations figures you sent are indeed convincing ...
> - Outside of textbooks, simple flattening is usually a very rare > operation
I agree with the general comments. However in some (non-textbook) AI code, my view is that you sometimes have to split up processing tasks when they start getting too complex.
> Optimizing flatten (even algorithmically) is IMHO a case of > premature and wrong optimization...
I think you're right. For different reasons, though. After profiling (on ACL) and successfully optimising, I was trying to scavenge whatever remaining functions could be optimised
