good lisp style ?
Eli Bendersky
I've written the following function to find out all pairs in a
list:
(defun find-all-pairs (lst)
"Finds all pairs - unique subsets of size 2 in the given list"
(cond
((null lst) '())
(t (append (mapcar #'(lambda (x) (list (car lst) x)) (cdr lst))
(find-all-pairs (cdr lst))))))
Although it is functional and short, I'm concerned about the usage
of mapcar in the recursion with append. Is this good style ? I'm
not talking about efficiency, because turning a clear function into
something ugly, but one that is a tail-recursion is only good for
some applications, not all.
So, what do you think ?
--
Eli Bendersky - http://www.geocities.com/spur4444/
Nils Goesche
> I've written the following function to find out all pairs in a
> list:
>
> (defun find-all-pairs (lst)
> "Finds all pairs - unique subsets of size 2 in the given list"
> (cond
> ((null lst) '())
> (t (append (mapcar #'(lambda (x) (list (car lst) x)) (cdr lst))
> (find-all-pairs (cdr lst))))))
>
> Although it is functional and short, I'm concerned about the usage
> of mapcar in the recursion with append.
You can safely use NCONC instead of APPEND. You can also easily avoid
recursion as in
(defun find-all-pairs (list)
(mapcon (lambda (tail)
(mapcar (lambda (x)
(list (car tail) x))
(cdr tail)))
list))
or do something equivalent with LOOP.
Regards,
--
Nils Goesche
"Don't ask for whom the <CTRL-G> tolls."
PGP key ID 0x0655CFA0
Frode Vatvedt Fjeld
> (defun find-all-pairs (lst)
> "Finds all pairs - unique subsets of size 2 in the given list"
> (cond
> ((null lst) '())
> (t (append (mapcar #'(lambda (x) (list (car lst) x)) (cdr lst))
> (find-all-pairs (cdr lst))))))
>
> [..] So, what do you think ?
I think it's ok. Only two minor things: Naming variables "lst" rather
than a proper word such as "list" isn't the CL way. And since you
explicitly create a fresh list for each element of the result, you may
use nconc rather than append.
BTW I don't see how "unique" applies to the subsets generated by this
function. From that description I'd expect no two similar two-tuples
to be returned (under eq or eql).
--
Frode Vatvedt Fjeld
Eli Bendersky
Frode Vatvedt Fjeld wrote:
> Eli Bendersky <just....@in.the.newsgroup> writes:
>
> > (defun find-all-pairs (lst)
> > "Finds all pairs - unique subsets of size 2 in the given list"
> > (cond
> > ((null lst) '())
> > (t (append (mapcar #'(lambda (x) (list (car lst) x)) (cdr lst))
> > (find-all-pairs (cdr lst))))))
> >
> > [..] So, what do you think ?
>
> I think it's ok. Only two minor things: Naming variables "lst" rather
> than a proper word such as "list" isn't the CL way. And since you
> explicitly create a fresh list for each element of the result, you may
> use nconc rather than append.
I hear about the usage of nconc a lot. How is it beneficial in
this case ?
> BTW I don't see how "unique" applies to the subsets generated by this
> function. From that description I'd expect no two similar two-tuples
> to be returned (under eq or eql).
What do you mean ? Unless there is a bug in it, the function
should not generate identical tuples. As I strive for subsets,
(1 2) and (2 1) are the same, and I want to have only one of
them. Unless the input is not a set (eg. has duplicates), it
should work fine.
Frode Vatvedt Fjeld
> I hear about the usage of nconc a lot. How is it beneficial in this
> case ?
append will not destructively modify any of its arguments, so it must
copy any list whose tail it needs to modify. Which in this case means
it will generate quite a bit of garbage needlessly. nconc doesn't mind
modifying its arguments, so it just splices the pieces together. For
your function this is OK, because you know that every piece is freshly
generated by mapcar.
Come to think of it, is mapcar really guaranteed to return a fresh
list?
>> BTW I don't see how "unique" applies to the subsets generated by
>> this function. From that description I'd expect no two similar
>> two-tuples to be returned (under eq or eql).
>
> What do you mean ? Unless there is a bug in it, the function should
> not generate identical tuples. As I strive for subsets, (1 2) and (2
> 1) are the same, and I want to have only one of them. Unless the
> input is not a set (eg. has duplicates), it should work fine.
I think, stylistically, such requirements on the input should be
documented. If there are no duplicates in the input, it would be a
strange algorithm that produced duplicate pairs.
--
Frode Vatvedt Fjeld
Nils Goesche
> Frode Vatvedt Fjeld wrote:
>
> > Eli Bendersky <just....@in.the.newsgroup> writes:
> >
> > > (defun find-all-pairs (lst)
> > > "Finds all pairs - unique subsets of size 2 in the given list"
> > > (cond
> > > ((null lst) '())
> > > (t (append (mapcar #'(lambda (x) (list (car lst) x)) (cdr lst))
> > > (find-all-pairs (cdr lst))))))
> > >
> > > [..] So, what do you think ?
> >
> > I think it's ok. Only two minor things: Naming variables "lst" rather
> > than a proper word such as "list" isn't the CL way. And since you
> > explicitly create a fresh list for each element of the result, you may
> > use nconc rather than append.
>
> I hear about the usage of nconc a lot. How is it beneficial in
> this case ?
NCONC modifies its arguments (except the last one), APPEND doesn't:
CL-USER 66 > (let ((one (copy-list '(foo bar baz)))
(two (copy-list '(1 2 3))))
(pprint (append one two))
(pprint one))
(FOO BAR BAZ 1 2 3)
(FOO BAR BAZ)
CL-USER 67 > (let ((one (copy-list '(foo bar baz)))
(two (copy-list '(1 2 3))))
(pprint (nconc one two))
(pprint one))
(FOO BAR BAZ 1 2 3)
(FOO BAR BAZ 1 2 3)
So, in the first case, APPEND makes a fresh copy of the list contained
in ONE. Pro: Old references to the same list won't see any change.
Con: You need more cons cells. Especially if there can't possibly
be around any references to the all-but-last arguments of APPEND, as
in your example, it is nothing but wasteful if you use APPEND instead
of NCONC. When in doubt, however, use APPEND.
Nils Goesche
> Come to think of it, is mapcar really guaranteed to return a fresh
> list?
Heh, well, all I can find in the standard is
# mapcan and mapcon are like mapcar and maplist respectively, except
# that the results of applying function are combined into a list by
# the use of nconc rather than list.
This seems to imply that MAPCAR and MAPLIST accumulate by using LIST.
Erik Naggum
This is very rude. People should be able to contact you directly.
| I've written the following function to find out all pairs in a list:
It looks like a nice Scheme function, which is usually the same as an ugly
Common Lisp function.
| Although it is functional and short, I'm concerned about the usage of mapcar
| in the recursion with append. Is this good style? I'm not talking about
| efficiency, because turning a clear function into something ugly, but one
| that is a tail-recursion is only good for some applications, not all.
There is no tail-recursion here. Just because some recursive call occurs
textually at the end does not mean tail-recursion applies. Tail-recursion
applies when the caller simply returns the value of the recursive call. In
this case, you use the returned value from the recursive call to return a
different value. To do this for something as simple as list traversal is
really bad style.
And what /is/ the point with this useless micro-level "functional style"?
What is /important/ in functional style is that you do not destructively
modify variable bindings or mutable objects that you have not created
yourself. I completely fail to understand this obsession with a limited
language just because you have some theory that dictates something. If goto
is considered harmful, it leads to convoluted code in many cases. In this
case, your code is very complex and hard to read and is only a good example
of how functional style should not be taught.
| So, what do you think?
(defun list-pairs (list)
(loop for (head . tail) on list
nconc (loop for element in tail
collect (list head element))))
"Find" is used in Common Lisp to return an existing object from some sort of
database, like `find´, `find-class´, `find-method´, `find-package´,
`find-symbol´, etc.
--
Erik Naggum, Oslo, Norway
Act from reason, and failure makes you rethink and study harder.
Act from faith, and failure makes you blame someone and push harder.
Erik Naggum
| Come to think of it, is mapcar really guaranteed to return a fresh
| list?
Yes. For two reasons: (1) The values is collects into a list are all fresh
as far as mapcar is concerned. (2) Where would it find the old cons cells
to use?
It would be really stupid to use `mapcan´ or `mapcon´ with a function that
returned old cons cells, however.
Stephen J. Bevan
> * Eli Bendersky <just....@in.the.newsgroup>
>
> This is very rude. People should be able to contact you directly.
>
> | I've written the following function to find out all pairs in a list:
>
> It looks like a nice Scheme function, which is usually the same as an ugly
> Common Lisp function.
I'm no arbiter of Scheme style but it doesn't look like a very nice
Scheme function to me. I've have written it in Scheme as :-
(define (list-pairs l)
(list:catl '() l
(lambda (acc head tail)
(list:catl acc tail
(lambda (acc ih ignore)
(cons (list head ih) acc))))))
where list:catl stands for "list catamorphism left" which encodes a
recursion pattern which seems pretty common when dealing with lists
and is defined as :-
(define (list:catl z l f)
(if (null? l)
z
(list:catl (f z (car l) (cdr l)) (cdr l) f)))
In CL there is no need for this function since, as you showed, "loop"
subsumes this recursion pattern.