On Mar 16, 2:00 pm, ·······@googlemail.com wrote:
[...]
> In scheme I would use letrec to avoid needing to pass the elt
> parameter to each loop iteration. Is there something similar in
> lisp or an alternative idiomatic way to write this loop?
LABELS[1] is Common Lisp answer to Scheme's letrec, in that it lets
you set up local, recursive function bindings. Personally, I'd use
that to do what you do in your Scheme version. An alternative would be
to use the complicated-but-powerful LOOP macro to do it---some CLers
would say that's *more* idiomatic.
Cheers,
Pillsy
[1] http://www.lisp.org/HyperSpec/Body/speope_fletcm_scm_macrolet.html
On Mar 16, 3:43 pm, "Pillsy" <·········@gmail.com> wrote:
> On Mar 16, 2:00 pm, ·······@googlemail.com wrote:
> > In scheme I would use letrec to avoid needing to pass the elt
> > parameter to each loop iteration. Is there something similar in
> > lisp or an alternative idiomatic way to write this loop?
> LABELS[1] is Common Lisp answer to Scheme's letrec, in that it lets
> you set up local, recursive function bindings. Personally, I'd use
> that to do what you do in your Scheme version. An alternative would be
> to use the complicated-but-powerful LOOP macro to do it---some CLers
> would say that's *more* idiomatic.
Sorry about replying to myself, but I just remembered one caveat: your
CL implementation may not eliminate tail calls, so the recursive
version could conceivably blow the stack on a very long list. Most of
the implementations out there actually do TCE, but the spec doesn't
require them to, and they may let you turn it off and on using
declarations.
Cheers,
Pillsy
Pillsy wrote:
> On Mar 16, 2:00 pm, ·······@googlemail.com wrote:
> [...]
> > In scheme I would use letrec to avoid needing to pass the elt
> > parameter to each loop iteration. Is there something similar in
> > lisp or an alternative idiomatic way to write this loop?
>
> LABELS[1] is Common Lisp answer to Scheme's letrec, in that it lets
> you set up local, recursive function bindings. Personally, I'd use
> that to do what you do in your Scheme version. An alternative would be
> to use the complicated-but-powerful LOOP macro to do it---some CLers
> would say that's *more* idiomatic.
>
> Cheers,
> Pillsy
>
> [1] http://www.lisp.org/HyperSpec/Body/speope_fletcm_scm_macrolet.html
Excellent, thanks. I'll give it a go with labels. The lists won't
ever get
particularly long so lack of TCO will not be a problem.
Ian
·······@googlemail.com writes:
> I'm trying to write a loop that inserts a dotted key/value pair in
> order into a list of ordered
> key/value pairs.
>
> So far I've got a recursive solution:
>
> (defun kv-insert (list elt)
> (if (null list) '()
> (let* ((h (car list))
> (k1 (car elt))
> (k2 (car h)))
> (cond ((string< k1 k2) (cons elt list))
> ((string= k1 k2) (cons elt (cdr list)))
> (t (cons h (kv-insert (cdr list) elt)))))))
I find this pretty comprehensible. Is it by design that if an element
has a key that's string> that the key of the last element of the list,
it's discarded?
> (KV-INSERT '((a . 1) (b . 2)) '(c . 3))
((a . 1) (b . 2))
Rob St. Amant wrote:
> ·······@googlemail.com writes:
>
> > I'm trying to write a loop that inserts a dotted key/value pair in
> > order into a list of ordered
> > key/value pairs.
> >
> > So far I've got a recursive solution:
> >
> > (defun kv-insert (list elt)
> > (if (null list) '()
> > (let* ((h (car list))
> > (k1 (car elt))
> > (k2 (car h)))
> > (cond ((string< k1 k2) (cons elt list))
> > ((string= k1 k2) (cons elt (cdr list)))
> > (t (cons h (kv-insert (cdr list) elt)))))))
>
> I find this pretty comprehensible. Is it by design that if an element
> has a key that's string> that the key of the last element of the list,
> it's discarded?
>
> > (KV-INSERT '((a . 1) (b . 2)) '(c . 3))
> ((a . 1) (b . 2))
Good point. The (if (null ...) guard was supposed to be (if (null
list) (list elt) ...
Thanks,
Ian
On 2007-03-16 14:00:40 -0400, ·······@googlemail.com said:
> I'm trying to write a loop that inserts a dotted key/value pair in
> order into a list of ordered
> key/value pairs.
If this is what you're really tying to do:
* (defun kv-insert (list elt) (stable-sort (push elt list) #'string<
:key #'car))
KV-INSERT
* (kv-insert (list (cons "alpha" "zeta") (cons "beta" "delta") (cons
"zeta" "eta")) (cons "sigma" "gamma"))
(("alpha" . "zeta") ("beta" . "delta") ("sigma" . "gamma") ("zeta" . "eta"))
*
On Fri, 16 Mar 2007 16:03:46 -0400, Raffael Cavallaro <················@pas-d'espam-s'il-vous-plait-mac.com> said:
| ...
| * (defun kv-insert (list elt) (stable-sort (push elt list) #'string< :key #'car))
^^^^
Apart from any efficiency considerations (this is O(n log n), while
it can be just O(n)), this either needs a (COPY-LIST LIST) or a
comment explaining why the value is expendable. Also, the PUSH is
gratuitous; this is a job for CONS.
---Vassil.
--
Definitely worth seeing: "Das Leben der Anderen" ("The Lives of Others").
On 2007-03-16 23:29:30 -0400, Vassil Nikolov <···············@pobox.com> said:
> Apart from any efficiency considerations (this is O(n log n), while
> it can be just O(n)),
sigh...
I knew someone would bring this up. Is this *really* likely to be an
execution hot spot of the program? The OP asked for *idiomatic* common
lisp. After all, we're talking about using dotted pairs as a data
structure! Is a program that needs real speed on large data sets really
using dotted pairs in a list as the data structure?
If what he really wanted was a tutorial on how to write clever
schemisms in common lisp, then, hey, go to town with labels and the
rest. Notice that all of his various examples are ~10-20 lines long,
while the idiomatic Common Lisp version I posted is one line. Common
Lisp is a language for getting things done, not for theoretical purity.
There is really no point in programming in Common Lisp if you are not
going to avail yourself of its huge library. It provides a means of
adding an element to an existing list (push) and a means to stably sort
an existing list destructively, which takes not one, but two functional
arguments for customization. Stable sort is tailor made for this
problem, and if it's done in any reasonable fashion by one's
implementation using it is unlikely to be an efficiency issue.
> this either needs a (COPY-LIST LIST) or a
> comment explaining why the value is expendable.
It needs neither, since the OP's request was for a function:
"that inserts a dotted key/value pair in
order into a list of ordered
key/value pairs."
iow, he didn't ask for a function that returns a *copy* of the original
list with an added item, he asked for a new item to be inserted in an
existing sorted list - he asked for a destructive modification to an
existing data structure.
> Also, the PUSH is
> gratuitous; this is a job for CONS.
Again, only if you assume that what is desired is a functional
approach. The OP didn't ask for it. Lisp provides a very direct way to
do it destructively, and since we're trashing the original list with
sort, might as well use push too ;^)
On Sat, 17 Mar 2007 00:07:57 -0400, Raffael Cavallaro <················@pas-d'espam-s'il-vous-plait-mac.com> said:
| On 2007-03-16 23:29:30 -0400, Vassil Nikolov <···············@pobox.com> said:
|| Apart from any efficiency considerations (this is O(n log n), while
|| it can be just O(n)),
| sigh...
| I knew someone would bring this up. Is this *really* likely to be an
| execution hot spot of the program? The OP asked for *idiomatic* common
| lisp. After all, we're talking about using dotted pairs as a data
| structure! Is a program that needs real speed on large data sets
| really using dotted pairs in a list as the data structure?
| If what he really wanted was a tutorial on how to write clever
| schemisms in common lisp, then, hey, go to town with labels and the
| rest. Notice that all of his various examples are ~10-20 lines long,
| while the idiomatic Common Lisp version I posted is one line. Common
| Lisp is a language for getting things done, not for theoretical purity.
Indeed it is, but in the appropriate way, not in the way of that
notorious adage, "Lisp programmers know the value of everything but
the cost of nothing." This is (an exercise in writing) a library
function, and library functions are best done without undue
overhead, which tends to bite sooner or later (of course, often
someone other than the author of the library is the one who gets
bitten...).
I believe one of the criteria for idiomatic Lisp is the
Norvig-Pitman test (I call it thus because I read about it in their
(excellent) tutorial (should be easily googlable)), which can
essentially be summarized in the following way. If p is a program
and d is a (corresponding) description of a program in natural
language, P is the transformation from d to p and D is the
transformation from p to d, then a program is good if D*P and P*D
are both identities. Now, if d says "insert" and p says "sort", I
don't think this test passes.
| There is really no point in programming in Common Lisp if you are not
| going to avail yourself of its huge library. It provides a means of
| adding an element to an existing list (push) and a means to stably
PUSH is not about adding an element to (the head of) an existing
list---it is about adding an element to a _place_, which is not
exactly the same thing. In this case, the place happens to be a
local variable that is not used anywhere else, so there is no
semantic difference, but there is a difference in style and
(communicated) intent.
| sort an existing list destructively, which takes not one, but two
| functional arguments for customization. Stable sort is tailor made for
| this problem, and if it's done in any reasonable fashion by one's
| implementation using it is unlikely to be an efficiency issue.
By the way, I should have mentioned earlier (and probably someone
already has, anyway) that using sort would leave duplicate keys,
which may or may not be what we want.
|| this either needs a (COPY-LIST LIST) or a
|| comment explaining why the value is expendable.
| It needs neither, since the OP's request was for a function:
| "that inserts a dotted key/value pair in
| order into a list of ordered
| key/value pairs."
| iow, he didn't ask for a function that returns a *copy* of the
| original list with an added item, he asked for a new item to be
| inserted in an existing sorted list - he asked for a destructive
| modification to an existing data structure.
The original post does not say "destructive", none of the solutions
given in it is destructive, and then in general a-lists are usually
used in a non-destructive fashion (as opposed to, say, p-lists). So
I don't see either a requirement or a permission to be destructive.
---Vassil.
--
The truly good code is the obviously correct code.
On 2007-03-20 00:56:06 -0400, Vassil Nikolov <···············@pobox.com> said:
> This is (an exercise in writing) a library
> function, and library functions are best done without undue
> overhead, which tends to bite sooner or later (of course, often
> someone other than the author of the library is the one who gets
> bitten...).
The real issue here is that the OP was rolling his own and asking for
the idiomatic[1] Common Lisp way of doing what he wanted to do. The
most important component of that issue is that the idiomatic Common
Lisp way is to use the abundant library utilities that are part of the
standard language - even if they are slightly inefficient - rather than
roll your own.
Why? because processor time ceased being the bottleneck in software
production well over a decade ago. The bottleneck now is programmer
time. So unless he knows this task to be a significant drain on CPU
resources, he should spend zero time optimizing it by hand writing a
loop. He should write it as quickly as possible and move on to another
task. Writing it as quickly as possible means using the abundant built
in functionality of the language.
His problem called for sorted output. Common Lisp has a sort (and
stable-sort and merge) library functions. They are destructive. He can
trivially make the version I originally presented functional by simply
copying the args, as any Common Lisp programmer would if using sort on
a sequence he didn't want modified. If kv-insert really is a library
function, it is actually more useful if it is destructive. With a
destructive library function we trivially get it's functional
counterpart by copying args before passing them to the function. The
reverse is not true - given only a functional library routine you
cannot easily get the destructive counterpart - you have to write it
from scratch. Note that assigning the return value of a functional
routine to an existing location does not count as "destructive" because
the whole point of destructive functions is to reduce or eliminate
memory allocation. Why does the Common Lisp standard have sort,
stable-sort, and merge (all destructive) but no functional versions of
these three? Possibly because functional counterparts are trivially had
by copying args.
Since he was actually interested in replacing existing ocurrances I
later posted another version which uses other Common Lisp library
functionality to do the job (i.e., it also uses remove). Since there
was a clamor to make it functional, this version is functional (it uses
copy-seq) but could easily be destructive. This side issue of
functional/destructive apart, it does what it does by using existing
Common Lisp library functions, not by reinventing the wheel yet again.
Sadly this wheel reinvention appears to be a favorite pastime of
programmers who mistakenly believe that the time every part of their
program takes to run is more valuable than the time it takes the
programmer to write it.
But you have taught me a valuable lesson Vassil, and that is to never
try to disabuse anyone posting here of the notion that all tasks are
best accomplished by rolling your own. Those who believe this should be
left to their wheel reinvention until they have one of two epiphanies:
a. "Gosh I'm wasting a lot of time writing utilities that someone else
has already written!" at which point they may start using Common Lisp
as it is more productively used.
b. "Gosh, If I'm going to reinvent *everything* I might as well be
using Scheme!" at which point they will decamp for c.l.s. where they
belong.
[1] It's in the *subject* of the thread.
On Mar 20, 7:43 pm, Raffael Cavallaro <················@pas-d'espam-
s'il-vous-plait-mac.com> wrote:
> The real issue here is that the OP was rolling his own and asking for
> the idiomatic[1] Common Lisp way of doing what he wanted to do. The
> most important component of that issue is that the idiomatic Common
> Lisp way is to use the abundant library utilities that are part of the
> standard language - even if they are slightly inefficient - rather than
> roll your own.
I do think it's hard to know whether there's a "question behind the
question," on a low-bandwidth medium like usenet.
If it's performance optimization, then we might want a more exotic
object to insert into than a simple sorted list.
If the fellow just wants to know how LOOP works, ok...
If it's readability or what people typically code, then I think a
quick first draft makes sense. Minimal code rather than a relatively
complex loop. Maybe more reliable, less mental burden, etc.
Why not take cues from writers? I think some of Stephen King's points
may be interesting.
http://mikeshea.net/Everything_You_Need_to_Kn.html
Your mileage may vary...
Tayssir
On Mar 17, 4:29 am, Vassil Nikolov <···············@pobox.com> wrote:
> On Fri, 16 Mar 2007 16:03:46 -0400, Raffael Cavallaro said:
> | * (defun kv-insert (list elt)
> | (stable-sort (push elt list) #'string< :key #'car))
> ^^^^
>
> Apart from any efficiency considerations (this is O(n log n), while
> it can be just O(n)), this either needs a (COPY-LIST LIST) or a
> comment explaining why the value is expendable. Also, the PUSH is
> gratuitous; this is a job for CONS.
You could have O(n) and non-destructiveness with:
(defun kv-insert (list elt)
(merge 'list (copy-seq list) (list elt) #'string< :key #'car))
But you tell me
Over and over and over again, my friend
Ah, you don't believe
We're on the eve
of destruction.
Tayssir
"Tayssir John Gabbour" <············@googlemail.com> writes:
> On Mar 17, 4:29 am, Vassil Nikolov <···············@pobox.com> wrote:
>> On Fri, 16 Mar 2007 16:03:46 -0400, Raffael Cavallaro said:
>> | * (defun kv-insert (list elt)
>> | (stable-sort (push elt list) #'string< :key #'car))
>> ^^^^
>>
>> Apart from any efficiency considerations (this is O(n log n), while
>> it can be just O(n)), this either needs a (COPY-LIST LIST) or a
>> comment explaining why the value is expendable. Also, the PUSH is
>> gratuitous; this is a job for CONS.
>
> You could have O(n) and non-destructiveness with:
>
> (defun kv-insert (list elt)
> (merge 'list (copy-seq list) (list elt) #'string< :key #'car))
This is the cleanest solution so far, I think. At least part of the
reason the original poster's code was longer, though, was that he
wanted to replace the value for a key if it was already in the list.
I don't know if this can be done without either an explicit iteration
or by making two passes, e.g.,
;; destructive
(defun kv-insert (list elt)
(let ((pair (assoc (car elt) list :test #'string=)))
(cond (pair
(setf (cdr pair) (cdr elt))
list)
(t (merge 'list list (list elt) #'string< :key #'car)))))
On 2007-03-17 08:15:11 -0400, ·······@ncsu.edu (Rob St. Amant) said:
> At least part of the
> reason the original poster's code was longer, though, was that he
> wanted to replace the value for a key if it was already in the list.
(defun kv-insert (list elt)
(merge 'list (remove elt (copy-seq list)
:test (lambda (a b) (string= (car a) (car b))))
(list elt) #'string< :key #'car))
CL-USER 4 > (kv-insert (list (cons "alpha" "zeta") (cons "beta"
"delta") (cons "sigma" "delta") (cons "zeta" "eta")) (cons "sigma"
"gamma"))
(("alpha" . "zeta") ("beta" . "delta") ("sigma" . "gamma") ("zeta" . "eta"))
On Sat, 17 Mar 2007 08:15:11 -0400, ·······@ncsu.edu (Rob St. Amant) said:
| "Tayssir John Gabbour" <············@googlemail.com> writes:
|| ...
|| (defun kv-insert (list elt)
|| (merge 'list (copy-seq list) (list elt) #'string< :key #'car))
| This is the cleanest solution so far, I think. At least part of the
| reason the original poster's code was longer, though, was that he
| wanted to replace the value for a key if it was already in the list.
| I don't know if this can be done without either an explicit iteration
| or by making two passes
It may be worth implementing (say) MERGE-DISCARDING-DUPLICATES, with
a signature just like MERGE, which would make a single pass (with
explicit iteration) and only take the element from (say) the first
sequence if the element from the second sequence matches (as if it
does
((lambda (k1 k2)
(not (or (funcall predicate k1 k2) (funcall predicate k2 k1))))
(funcall key e1)
(funcall key e2))
where E1 and E2 are the current incoming elements from the first and
the second sequence, respectively). It is of sufficiently general
purpose to deserve its own implementation. Of course, such a
function may well be already available somewhere.
(Note that this would not produce the same result as that of
applying REMOVE-DUPLICATES (or DELETE-DUPLICATES) to the value
returned by MERGE, since we want to keep duplicates occurring within
the same sequence and only discard ones arising from the merge
itself.)
Incidentally, this illustrates the benefit of <,=, etc. _not_ being
generic functions. In a(nother) function which actually makes such
two calls to the predicate together, an implementation might, on
finding that (MEMBER PREDICATE `(,#'CL:< ,#'CL:>)), make a single
call to CL:= (or CL:/=) in lieu of those two calls. Such an
optimization would not apply for a generic comparison function.
---Vassil.
--
The truly good code is the obviously correct code.