Anonymous user
Talk:Flatten a list: Difference between revisions
→Vandalization-like modification to C code
Line 57:
::I vote change it back, if it's incorrect. I think it's possible that the editor doesn't understand what a list is. (He may have been going for a "clever" solution; I doubt it was meant as vandalism, else he probably wouldn't have created a user account.) -- [[User:Eriksiers|Erik Siers]] 14:56, 1 October 2010 (UTC)
I have reverted the changes I made. Sorry for the inadvertent breach of protocol. I didn't realize it would cause so much consternation. I assumed most people here would immediately understand. If not, let me plead my case. First, I think you have to admit that my solution yields the correct answer for all well-formed lists so how wrong can it be?
Second, just because one may not be accustomed to seeing a list being represented as a string doesn't mean it is not valid. One can easily implement the entire list API in C using a string as the internal representation, and it will have roughly the same performance as a native lisp list. (If in doubt, see the Tcl code below.)
Third, that "imagined silly conversation" where the professor extols Scheme, ridicules C, and finally says "just strip away all the extra parentheses" is not imagined at all. It is roughly what a professor at a prestigious university once said when flattening a list in Scheme, and it breaks my heart to see so many people so uninformed about C. If you just want to strip out the parentheses why not just do it directly? And, what is more expressive than a language that lets you easily do so?
Granted, to the uninitiated, my solution may seem sophomoric at first, but consider this: Most of the languages with built-in list processing are based on the lambda calculus, but for some reason, it gets lost that regular expressions have just as deep mathematical roots. It seems pretty clear to me that the Unix/C people explicitly chose regular expressions over lambda calculus. For example, they could have passed S-expressions through their pipes, but instead of lists, they chose to pass strings and then use regular expressions to slice and dice. So it stands to reason, that there is probably a very deep equivalence between lists and strings for which most Unix/C people have an intuitive feel. For example, is there any real difference between Lisp's (car lst) and (cadr lst) and Awk's $1 and $2? I think another clear example of this is Lisp's (eval) vs. C's lex/yacc, but I'll leave it to the reader fill in those details.
Lastly, in the real world, there is probably no better example of the equivalence between lists and strings than Tcl which is implemented in C and which maintains an equivalence between all lists and strings. For example, the following Tcl code flattens a list simply by treating it as a string. (The Tcl code below works provided the list does not hold strings with embedded braces, but this problem can be fixed with a better regexp.) Note that at all times, the Tcl list is available as a '''real''' and "general" list held in memory as demonstrated by the use of the "llength" function before and after flattening the list, but that doesn't prevent the list from being by treating directly as a string. Also, regarding the point that one needs a tree traversal routine written in C that traverses lists implemented as strings before my solution is correct, one can just link with libtcl to get exactly that.
<lang tcl>
proc flatten lst {
string map {"{" "" "}" ""} $lst
}
set lst {{1 2 3} {4 5 6}}
puts [llength $lst]
puts [llength [flatten $lst]]
</lang>
It should also be pointed out that one of the hallmarks of C is its ability to reinterpret data. The high-performance Fortran and C programmers have long used arrays to model sequences or lists. The trick is to decouple the contents of the list from the structure of the list. This allows you to reinterpret the list by simply replacing the part that describes the structure of the list. Using this approach, the problem of flattening a list can be solved on the order of O(1). Essentially, this is what my original solution did (although on order of O(n)). It extracted the contents of the list, and because a flattened list has almost no structure, there really wasn't anything left to do except print the results. So please consider that the solution I originally posted is far from being vandalism and should be reinterpreted in the spirit of C.
| |||