Hoy to copy a struct that represents a tree.
in [Lisp]
|
Prev: Reader ?
Next: translating cmucl command line to sbcl
From: Vassil Nikolov on 24 Oct 2009 12:29 On Sat, 24 Oct 2009 07:20:29 +0200, pjb(a)informatimago.com (Pascal J. Bourguignon) said: > Vassil Nikolov <vnikolov(a)pobox.com> writes: >> On Fri, 23 Oct 2009 06:28:41 +0200, pjb(a)informatimago.com (Pascal J. Bourguignon) said: >> >>> Vassil Nikolov <vnikolov(a)pobox.com> writes: >>>> On Fri, 23 Oct 2009 03:22:21 +0200, pjb(a)informatimago.com (Pascal J. Bourguignon) said: >>>>> ... >>>>> (defun collect-nodes (tree) >>>>> (if (null tree) >>>>> '() >>>>> (cons tree (append (collect-nodes (my-tree-l tree)) >>>>> (collect-nodes (my-tree-c tree)) >>>>> (collect-nodes (my-tree-r tree)))))) >>>> >>>> APPEND?! >> >>> Do you have a use case where more performance is needed? >> >> Large trees. > If you implement a unit test for real-copy-my-tree which works on > trees of depth 3, do you really need to further test it on trees of > depth 100? If I take my unit tests seriously, yes, I do [*]. Besides, COLLECT-NODES and similar functions may be useful in general, not just for unit tests, and it's best to avoid suboptimal definitions when it takes little to provide better ones. (When it is equally easy and uncomplicated to use either of several algorithms, it is only natural to prefer the one of lesser complexity.) _________ [*] There are a number of (not just theoretical) reasons why a nominally correct implementation may work satisfactorily on toy examples, but not be up to scratch on large ones, and such cases are best caught early, of course. >> [s/append/nconc/] > It's harder to prove the correctness of collect-nodes with mutation. > (Perhaps it's only one inference, but it's one inference I did not > need to think about to write the unit test). We want the functions > used in unit tests to be proved very easily to be quite sure the tests > are good. Which is why I also provided another definition, which does not do mutation, and is faster besides. ---Vassil. -- "Even when the muse is posting on Usenet, Alexander Sergeevich?"
From: Vassil Nikolov on 24 Oct 2009 12:49 On Sat, 24 Oct 2009 15:38:58 +0000 (UTC), Kaz Kylheku <kkylheku(a)gmail.com> said: > On 2009-10-24, Vassil Nikolov <vnikolov(a)pobox.com> wrote: >> >> On Fri, 23 Oct 2009 05:29:05 -0700 (PDT), Andy Chambers <achambers.home(a)googlemail.com> said: >>> ... >>> what it is about structs/classes that makes >>> them more suitable for real apps? >> >> Perhaps the most important thing is proper support for data abstraction. > But a TREE struct with slots C, L and R is not a superior data abstraction > to a CONS with slots CAR and CDR. What does that mean? If the above said, "a TREE structure with clots [E,] C, L, and R is not a superior _general-purpose_ data _structure_ to a CONS with slots CAR and CDR", then it would be clearly (or at least arguably) true, but on a different topic. As to data _abstractions_, CONS with CAR and CDR---if it qualifies to be called a "data abstraction" at all---is one at a much lower level; and whether or not a TREE with MAKE-TREE, TREE-E, TREE-C, TREE-L, and TREE-R is superior or inferior to another data abstraction at the same level, or if indeed it is any good at all, depends on what we are modelling, which isn't specified here at all. Part of the value of DEFSTRUCT, and perhaps the most important part, is that it allows, in great many cases, the automatic generation of constructors, selectors, and recognizers, as well as the automatic maintenance of the underlying physical representation, and thus it greatly facilitates the proper use of data _abstractions_. ---Vassil. -- "Even when the muse is posting on Usenet, Alexander Sergeevich?"
From: Vassil Nikolov on 24 Oct 2009 13:05 On Fri, 23 Oct 2009 05:29:05 -0700 (PDT), Andy Chambers <achambers.home(a)googlemail.com> said: > ... > Please could you expand on what it is about structs/classes that makes > them more suitable for real apps? By the way, perhaps not so much about greater suitability, but about usefulness of features, one less obvious valuable property of structures is the support for user-defined literals (of a certain form). Among the _standardized_ character macros of Common Lisp, only `#S' (sharp-S) is user-extensible in the sense that only it supports the introduction of new literals by the user _while_ using just the _standard_ read table. (While `#.' (sharp-dot) allows (nearly) arbitrary literals, it can only be counted as providing the above feature with a grain of salt, because it is unsafe and therefore may tend to be turned off.) ---Vassil. -- "Even when the muse is posting on Usenet, Alexander Sergeevich?"
From: Wade on 24 Oct 2009 15:14 On Oct 24, 11:05 am, Vassil Nikolov <vniko...(a)pobox.com> wrote: > On Fri, 23 Oct 2009 05:29:05 -0700 (PDT), Andy Chambers <achambers.h...(a)googlemail.com> said: > > > ... > > Please could you expand on what it is about structs/classes that makes > > them more suitable for real apps? > > By the way, perhaps not so much about greater suitability, but about > usefulness of features, one less obvious valuable property of > structures is the support for user-defined literals (of a certain > form). Among the _standardized_ character macros of Common Lisp, > only `#S' (sharp-S) is user-extensible in the sense that only it > supports the introduction of new literals by the user _while_ using > just the _standard_ read table. > > (While `#.' (sharp-dot) allows (nearly) arbitrary literals, it can > only be counted as providing the above feature with a grain of salt, > because it is unsafe and therefore may tend to be turned off.) > > ---Vassil. > > -- > "Even when the muse is posting on Usenet, Alexander Sergeevich?" Besides the read macro, structures also are slot comparable by the standard EQUALP. Wade
From: russell_mcmanus on 25 Oct 2009 11:03
Vassil Nikolov <vnikolov(a)pobox.com> writes: > [*] There are a number of (not just theoretical) reasons why a > nominally correct implementation may work satisfactorily on toy > examples, but not be up to scratch on large ones, and such cases > are best caught early, of course. This article comes to mind: http://portal.acm.org/citation.cfm?id=1516632&dl=GUIDE&coll=GUIDE&CFID=58206374&CFTOKEN=27403333 -russ |