I am just getting started with Lisp. I'm a grad student studying math,
and work with Mathematica and Python, so Lisp seemed like an obvious
language to pick up.
My first function is below. It (should) generate compositions of an
integer. A composition is an ordered list of nonnegative integers that
add up to the given number. "0 3 2", "1 1 3", and "2 0 3" are three
different compositions of 5.
Comments and improvements are welcome. One problem right now is that it
returns nested lists, and I want just a single list, containing lists
of integers.
The code:
(defun compositions (n k)
"Return a list of (weak) compositions of n into k parts."
(cond
;; if either is zero, there are no compositions - return the empty
;; list
((or (< n 0) (< k 0))
nil)
;; by convention, the empty list is a composition of zero into zero
;; parts, so return that if n == k == 0.
((= k 0)
(if (= n 0) (list ()) nil))
;; obviously one composition of something into one part: return a
;; list containing that one composition
((= k 1)
(list (list n)))
;; otherwise, recurse based on first element of the composition
(t
(mapcar (lambda (i)
(mapcar (lambda (comp)
(cons i comp)) (compositions (- n i) (- k
1))))
(cons 0 (range n))))))
It uses this function:
;;; from http://www.cs.berkeley.edu/~fateman/mma1.6/comb.lisp
(defun range (n &aux ans)
"Return a list of elements from 1 to n"
(declare (fixnum n))
(do ((i n (1- i)))
((= i 0) ans)
(declare (fixnum i))
(setq ans (cons i ans))))
Example run: (print (compositions 3 3)) produces
(((0 (0 3)) (0 (1 2)) (0 (2 1)) (0 (3 0))) ((1 (0 2)) (1 (1 1)) (1 (2
0)))
((2 (0 1)) (2 (1 0))) ((3 (0 0))))
Thanks!
Yes, "compositions" is a mathematical term.
"Ordered" means "order matters". That's why 0 3 2 and 2 0 3 are
different compositions of 5 -- the 0, 2, and 3 are in a different order.
··········@gmail.com writes:
> I am just getting started with Lisp. I'm a grad student studying math,
> and work with Mathematica and Python, so Lisp seemed like an obvious
> language to pick up.
>
> My first function is below. It (should) generate compositions of an
> integer. A composition is an ordered list of nonnegative integers that
> add up to the given number. "0 3 2", "1 1 3", and "2 0 3" are three
> different compositions of 5.
>
> Comments and improvements are welcome. One problem right now is that it
> returns nested lists, and I want just a single list, containing lists
> of integers.
> The code:
>
> (defun compositions (n k)
> "Return a list of (weak) compositions of n into k parts."
> (cond
> ;; if either is zero, there are no compositions - return the empty
> ;; list
> ((or (< n 0) (< k 0))
> nil)
> ;; by convention, the empty list is a composition of zero into zero
> ;; parts, so return that if n == k == 0.
> ((= k 0)
> (if (= n 0) (list ()) nil))
> ;; obviously one composition of something into one part: return a
> ;; list containing that one composition
> ((= k 1)
> (list (list n)))
> ;; otherwise, recurse based on first element of the composition
> (t
> (mapcar (lambda (i)
> (mapcar (lambda (comp)
> (cons i comp)) (compositions (- n i) (- k
> 1))))
> (cons 0 (range n))))))
Consider mapcan instead of mapcar.
(defun compositions (n k)
"Return a list of (weak) compositions of n into k parts."
(cond
;; if either is zero, there are no compositions - return the empty
;; list
((or (< n 0) (< k 0))
nil)
;; by convention, the empty list is a composition of zero into zero
;; parts, so return that if n == k == 0.
((= k 0)
(if (= n 0) (list ()) nil))
;; obviously one composition of something into one part: return a
;; list containing that one composition
((= k 1)
(list (list n)))
;; otherwise, recurse based on first element of the composition
(t
(mapcan (lambda (i) (mapcar (lambda (comp) (cons i comp))
(compositions (- n i) (- k 1))))
(cons 0 (range n))))))
[78]> (compositions 4 4)
((0 0 0 4) (0 0 1 3) (0 0 2 2) (0 0 3 1) (0 0 4 0) (0 1 0 3) (0 1 1 2) (0 1 2 1)
(0 1 3 0) (0 2 0 2) (0 2 1 1) (0 2 2 0) (0 3 0 1) (0 3 1 0) (0 4 0 0) (1 0 0 3)
(1 0 1 2) (1 0 2 1) (1 0 3 0) (1 1 0 2) (1 1 1 1) (1 1 2 0) (1 2 0 1) (1 2 1 0)
(1 3 0 0) (2 0 0 2) (2 0 1 1) (2 0 2 0) (2 1 0 1) (2 1 1 0) (2 2 0 0) (3 0 0 1)
(3 0 1 0) (3 1 0 0) (4 0 0 0))
[79]>
--
__Pascal Bourguignon__ http://www.informatimago.com/
I need a new toy.
Tail of black dog keeps good time.
Pounce! Good dog! Good dog!
Pascal Bourguignon wrote:
[Ben Caxton:]
>> My first function is below. It (should) generate compositions of an
>> integer. A composition is an ordered list of nonnegative integers that
>> add up to the given number. "0 3 2", "1 1 3", and "2 0 3" are three
>> different compositions of 5.
...
[Pascal:]
> Consider mapcan instead of mapcar.
[etc]
I think your solution has more special cases than it needs.
(defun compositions (n k)
"Return a list containing all K-element lists of non-negative
integers with sum N. Caller guarantees that N,K are non-negative
integers."
(if (zerop k)
(if (zerop n) (list nil) nil)
(loop for first-item upfrom 0 to n nconc
(mapcar (lambda (tail) (cons first-item tail))
(compositions (- n first-item) (1- k))))))
(I find LOOP ... NCONC ... clearer than MAPCAN.)
--
Gareth McCaughan
.sig under construc
From: Kent M Pitman
Subject: Re: my first Lisp code...comments welcome
Date:
Message-ID: <uk6lj1f5x.fsf@nhplace.com>
··········@gmail.com writes:
> ((= k 0)
> (if (= n 0) (list ()) nil))
Don't use the notation () as an unadorned expression in code.
It can be used in text, to denote an empty list that is part of a form.
For example:
(defun foo () 'foo)
In that case, () is not itself a form but is a sub-expression of a
DEFUN form, so it's ok.
If you mean an empty list, use a quote mark in front of it. e.g.,
(defun the-empty-list () '())
If you mean false, use nil (as if it were a variable holding false,
ignoring that nil is also the false value itself).
If you mean nil in the role of a symbol, use 'nil to highlight that
you are not thinking of its value (even though its value is also nil).
It's sometimes hard for newbies to understand when to use '() and when
to use nil. e.g., which does MEMBER return on a failing search. The
answer in that case is that on a succeeding search, MEMBER returns the
list tail whose car is the sought item. Since that's not true in the failing
case, what is returned is not a list tail and is instead just false. So
in that case, return NIL.
In your case here, if I read your code right, you're returning something
that on a recursion will be always appended, you want to say
(if (= n 0) (list '()) '())
This will help readers of your code know the intended view of your
nils here are both as empty lists, not as falses nor as symbols. It will
also keep you from confusing program text with program data.
> ;; obviously one composition of something into one part: return a
> ;; list containing that one composition
> ((= k 1)
> (list (list n)))
> ;; otherwise, recurse based on first element of the composition
> (t
> (mapcar (lambda (i)
> (mapcar (lambda (comp)
> (cons i comp)) (compositions (- n i) (- k
> 1))))
> (cons 0 (range n))))))
Except in very rare special cases, and function calls are not one of them,
don't ever start subform n of an expression on the same line as subform n-1
if you have already introduced a newline between subforms for previous
subforms of the expression. Never
(f
a b)
always either
(f a b)
or
(f a
b)
or
(f
a
b)
An example of an exception might be setq, where there is a certain structure
to the apparent linear nature of the args, so
(setq a b
c d)
is ok as a kind of special case. But you want
(mapcar (lambda (i)
(mapcar (lambda (comp) (cons i comp))
(compositions (- n i) (- k 1))))
(cons 0 (range n)))
above. This helps you more easily tell how many subforms something has
just by its indentation.
And don't indent by 4, indent by 2.
> It uses this function:
>
> ;;; from http://www.cs.berkeley.edu/~fateman/mma1.6/comb.lisp
> (defun range (n &aux ans)
> "Return a list of elements from 1 to n"
> (declare (fixnum n))
> (do ((i n (1- i)))
> ((= i 0) ans)
> (declare (fixnum i))
> (setq ans (cons i ans))))
In macros with a body, let the header forms be indented as you've done
but move the body back to an indentation level of 2 so you can see
where the header is done
(do ((i n (1- i)))
((= i 0) ans)
(declare (fixnum i))
(setq ans (cons i ans)))
Use PUSH instead of cons in the last part.
(push i ans) instead of (setq ans (cons i ans))
It makes it easier to see the idiom you're using.
Don't use &aux except in rare cases, usually internal to macros.
It's stylistically pretty yucky even though it can get you out of certain
odd and extremely obscure problems in macros. e.g.,
(defun range (n)
"Return a list of elements from 1 to n"
(declare (fixnum n))
(do ((ans '() (cons i ans))
(i n (1- i)))
((= i 0) ans)
(declare (fixnum i))))
Learn about DOTIMES, which is often easier to read than DO.
(defun range (n)
(let ((result '()))
(dotimes (i n) (push (1+ i) n))
(nreverse result)))
This is controversial with some, but over my career I've come to believe
it more and more: Learn about LOOP, which embraces a lot of idioms in
very much more readable ways than DO and, when used right, is still
easier to read than either DO or DOTIMES.
(defun range (n)
(loop for i from 1 to n
collect i))
Spell out variables. "answer" or "result", not "ans".
"ans" makes me wonder if it's a plural of an "an, whatever an "an" is.
Are you sure really need to make RANGE return only fixnums? The function
would be more general returning also bignums. You shouldn't have to write
a separate BIGNUM-RANGE if you end up needing one. Think reusable.
When you get to the point of delivering a commercial product and it runs
too slowly, clean it up by adding declarations. But don't prematurely
optimize your code now thinking you are making it better. I think you're
just slowing your coding, making it take more time and risking early success,
making it more fragile to needed evolution in the early stages. But that's
just me.
Hope that helps.
--Kent
From: David Trudgett
Subject: Re: my first Lisp code...comments welcome
Date:
Message-ID: <m3vf52sxll.fsf@rr.trudgett>
Kent M Pitman <······@nhplace.com> writes:
> ··········@gmail.com writes:
>
>> ((= k 0)
>> (if (= n 0) (list ()) nil))
>
> Don't use the notation () as an unadorned expression in code.
> It can be used in text, to denote an empty list that is part of a form.
<snip>
There's some good advice in there for us newbies, Kent! Very readable,
too.
Sometimes, I've been using (list) instead of '(), especially
where I want to initialise an empty list. For example:
(defmethod net-get-common-head-event ((net net) activity-names-list)
(let ((activity-list (loop
for name in activity-names-list
collect (gethash name (net-activities net))))
(head-events (list)))
(dolist (activity activity-list)
(pushnew (activity-head-event activity) head-events))
(return-from net-get-common-head-event
(if (= 1 (length head-events))
(first head-events)
nil))))
Is that reasonable, do you think? I was prompted to do this by the
thought that '() instead of (list) might create a sort of constant,
which might cause problems when we get to PUSHNEW, for instance.
David
--
David Trudgett
http://www.zeta.org.au/~wpower/
"On two occasions I have been asked [by members of Parliament!],
'Pray, Mr. Babbage, if you put into the machine wrong figures, will
the right answers come out?' I am not able rightly to apprehend the
kind of confusion of ideas that could provoke such a question."
-- Charles Babbage
From: Kent M Pitman
Subject: Re: my first Lisp code...comments welcome
Date:
Message-ID: <uk6liam5o.fsf@nhplace.com>
David Trudgett <······@zeta.org.au.nospamplease> writes:
> Sometimes, I've been using (list) instead of '(), especially
> where I want to initialise an empty list. For example:
>
> (defmethod net-get-common-head-event ((net net) activity-names-list)
> (let ((activity-list (loop
> for name in activity-names-list
> collect (gethash name (net-activities net))))
> (head-events (list)))
> (dolist (activity activity-list)
> (pushnew (activity-head-event activity) head-events))
> (return-from net-get-common-head-event
> (if (= 1 (length head-events))
> (first head-events)
> nil))))
>
> Is that reasonable, do you think? I was prompted to do this by the
> thought that '() instead of (list) might create a sort of constant,
> which might cause problems when we get to PUSHNEW, for instance.
NIL or () _is_ a constant. So are all numbers. Conveniently, though,
there are no operations defined to side-effect these objects so the
fact of their constantness really has no relevance.
(list) just yields '() so there's no difference.
Moral: Don't be superstitious. Learn the truth where the truth is knowable.
Protect yourself against things that can vary where the language tells
you they can vary, not where you might imagine people designing another
language might have varied things.
This is not like other languages where an empty list can be side-effected
to create a non-empty list. You need to understand this fact not paper
over the need to know.
From: David Trudgett
Subject: Re: my first Lisp code...comments welcome
Date:
Message-ID: <m3u0kllpj7.fsf@rr.trudgett>
Kent M Pitman <······@nhplace.com> writes:
> David Trudgett <······@zeta.org.au.nospamplease> writes:
>
>> Sometimes, I've been using (list) instead of '(), especially
>> where I want to initialise an empty list. For example:
>>
>> (defmethod net-get-common-head-event ((net net) activity-names-list)
>> (let ((activity-list (loop
>> for name in activity-names-list
>> collect (gethash name (net-activities net))))
>> (head-events (list)))
>> (dolist (activity activity-list)
>> (pushnew (activity-head-event activity) head-events))
>> (return-from net-get-common-head-event
>> (if (= 1 (length head-events))
>> (first head-events)
>> nil))))
>>
>> Is that reasonable, do you think? I was prompted to do this by the
>> thought that '() instead of (list) might create a sort of constant,
>> which might cause problems when we get to PUSHNEW, for instance.
>
> NIL or () _is_ a constant. So are all numbers. Conveniently, though,
> there are no operations defined to side-effect these objects so the
> fact of their constantness really has no relevance.
>
> (list) just yields '() so there's no difference.
That's good to hear, since it's what I believed before going all
superstitious and all. One could suggest, of course, that (list) is
slightly more explicit for the human reader than '(), but it's really
six of one and half a dozen of the other.
>
> Moral: Don't be superstitious.
:-) I take full responsibility for my heinous disregard for rationality
and my ignominious fall into superstition; may the Lisp debugger have
mercy on my soul. ;-)
> Learn the truth where the truth is knowable.
Yes indeed! :-) I like the Star Wars overtones, there, too! You forgot
the "padewan" at the end, though! ;-) What did you think of the latest
Star Wars movies, by the way? (Hey, maybe they used Lisp for special
effects, who knows!) George L. seems to have gone over to the dark
side for episodes 1 to 3, what do you reckon? Or maybe he just lost
the old magic touch.
David
--
David Trudgett
http://www.zeta.org.au/~wpower/
The recognition or non-recognition of a certain truth depends not on
external causes, but on certain other causes within the man himself.
So that at times under external conditions apparently very favorable
for the recognition of truth, one man will not recognize it, and
another, on the contrary, under the most unfavorable conditions will,
without apparent cause, recognize it. As it is said in the Gospel, "No
man can come unto me, except the Father which hath sent me draw him."
That is to say, the recognition of truth, which is the cause of all
the manifestations of human life, does not depend on external
phenomena, but on certain inner spiritual characteristics of the man
which escape our observation.
-- Leo Tolstoy, "The Kingdom of God is Within You"
In article <··············@rr.trudgett>,
David Trudgett <······@zeta.org.au.nospamplease> wrote:
> Is that reasonable, do you think? I was prompted to do this by the
> thought that '() instead of (list) might create a sort of constant,
> which might cause problems when we get to PUSHNEW, for instance.
I don't know if it's reasonable (it seems kind of gratutious to me to
call a function to return NIL, even if any compiler worth its salt will
optimize it out), but you won't have any problems with '().
NIL, (), '(), and (LIST) are all strictly equivalent when evaluated and
result in the symbol NIL. Keep in mind that PUSHNEW never modifies
existing list structure; if the element to be added isn't present in the
list, it will be pushed onto the front of the list by setting the
variable in question to a new cons cell with the added element.
-bcd, guilty of usually writing NIL for a empty list.
--
*** Brian Downing <bdowning at lavos dot net>
David Trudgett <······@zeta.org.au.nospamplease> writes:
> Sometimes, I've been using (list) instead of '(), especially
> where I want to initialise an empty list. For example:
> [...]
> Is that reasonable, do you think? I was prompted to do this by the
> thought that '() instead of (list) might create a sort of constant,
> which might cause problems when we get to PUSHNEW, for instance.
(every (lambda (item) (eq item '())) (list (list) '() () 'nil nil)) --> T
You don't earn anything with (lisp), you just luse one function call.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Small brave carnivores
Kill pine cones and mosquitoes
Fear vacuum cleaner
From: Edi Weitz
Subject: Re: my first Lisp code...comments welcome
Date:
Message-ID: <usm06cq05.fsf@agharta.de>
On Sun, 29 May 2005 02:53:32 +0200, Pascal Bourguignon <···@informatimago.com> wrote:
> You don't earn anything with (lisp)
Really? I sometimes earn money with it. And so do others AFAIK.
Edi.
--
Lisp is not dead, it just smells funny.
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
On Sun, 29 May 2005 11:58:50 +0200, Edi Weitz wrote:
> On Sun, 29 May 2005 02:53:32 +0200, Pascal Bourguignon <···@informatimago.com> wrote:
>
>> You don't earn anything with (lisp)
>
> Really? I sometimes earn money with it. And so do others AFAIK.
Maybe Pascal wanted to imply that evaluating lisp would yield the
same result as (list) ?
(eq (lisp) (list))
Cheers RalfD
Mene mene tekel u-parsin
From: David Trudgett
Subject: Re: my first Lisp code...comments welcome
Date:
Message-ID: <m3ll5xloqj.fsf@rr.trudgett>
"R. Mattes" <··@mh-freiburg.de> writes:
> Maybe Pascal wanted to imply that evaluating lisp would yield the
> same result as (list) ?
>
> (eq (lisp) (list))
; Warning: This function is undefined:
; LISP
;-)
--
David Trudgett
http://www.zeta.org.au/~wpower/
Ren jia qi wo wo bu qi. (2143324)
Wo ruo sheng qi zhong ta ji. (3414114)
Qi chu bing lai mei ren ti. (4142224)
Xiang xiang hai shi bie sheng qi. (3324214)
-- Chinese poem
A translation:
Should someone provoke me, I will not become angry.
To become angry would be to fall into his trap.
With anger comes loss of good health, which is irreplaceable.
Thinking about it, it is better not to become angry.
From: Joe Marshall
Subject: Re: my first Lisp code...comments welcome
Date:
Message-ID: <ll4xki1h.fsf@comcast.net>
Edi Weitz <········@agharta.de> writes:
> On Sun, 29 May 2005 02:53:32 +0200, Pascal Bourguignon <···@informatimago.com> wrote:
>
>> You don't earn anything with (lisp)
>
> Really? I sometimes earn money with it. And so do others AFAIK.
>
Do you think it is fair to mislead the newbies like this?
--
~jrm
From: Edi Weitz
Subject: Re: my first Lisp code...comments welcome
Date:
Message-ID: <u3br5s7da.fsf@agharta.de>
On Sat, 25 Jun 2005 21:45:14 -0400, Joe Marshall <·············@comcast.net> wrote:
> Do you think it is fair to mislead the newbies like this?
I thought the purpose of this newsgroup is to confuse newbies. Am I
wrong?
Cheers,
Edi.
PS: Nice to have you back here, BTW.
--
Lisp is not dead, it just smells funny.
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
From: Joe Marshall
Subject: Re: my first Lisp code...comments welcome
Date:
Message-ID: <oe9thxve.fsf@comcast.net>
Edi Weitz <········@agharta.de> writes:
> On Sat, 25 Jun 2005 21:45:14 -0400, Joe Marshall <·············@comcast.net> wrote:
>
>> Do you think it is fair to mislead the newbies like this?
>
> I thought the purpose of this newsgroup is to confuse newbies. Am I
> wrong?
Sorry, it's been a while.
Yes. Lisp will make you wealthy beyond your wildest dreams.
--
~jrm
From: David Trudgett
Subject: Re: my first Lisp code...comments welcome
Date:
Message-ID: <m3psv9lp2a.fsf@rr.trudgett>
Pascal Bourguignon <···@informatimago.com> writes:
> (every (lambda (item) (eq item '())) (list (list) '() () 'nil nil)) --> T
You're right about that!
>
> You don't earn anything with (lisp), you just luse one function call.
True, as it turns out, but I was assuming two things: (1) any
implemenation (as someone pointed out) worth its salt would optimise
out the actual function call and insert instead the constant value in
the case of my being wrong; and (2) a single function call in a
non-critical block will not have any measurable effect on performance.
Funny thing is that I got all superstitious after reading something
someone on this list wrote a while ago, but I can't remember what it
was. Obviously, whoever it was must have been talking about something
different.
Thanks for reminding me about EVERY, too, as I've yet to use the
critter! I'm sure it will come in handy at some stage.
David
--
David Trudgett
http://www.zeta.org.au/~wpower/
We must learn to live together as brothers or perish together as
fools.
-- Martin Luther King, Jr.
David Trudgett wrote:
> Sometimes, I've been using (list) instead of '(), especially
> where I want to initialise an empty list. For example:
>
> (defmethod net-get-common-head-event ((net net) activity-names-list)
> (let ((activity-list (loop
> for name in activity-names-list
> collect (gethash name (net-activities net))))
> (head-events (list)))
> (dolist (activity activity-list)
> (pushnew (activity-head-event activity) head-events))
> (return-from net-get-common-head-event
> (if (= 1 (length head-events))
> (first head-events)
> nil))))
>
> Is that reasonable, do you think? I was prompted to do this by the
> thought that '() instead of (list) might create a sort of constant,
> which might cause problems when we get to PUSHNEW, for instance.
That sounds like a good strategy when dealing with multiple languages,
with their own crazy eccentricities, when you feel like being
conservative. I often write a quick comment when I'm doing something
like that, when I think I'm being anti-idiomatic yet correct, but am
not interested in breaking my flow by looking something up in some
manual.
Stephen King had similar advice for writers. But as he says, you later
on want to go back and clean it up. So it won't be jarring and
confusing to readers.
Tayssir
From: David Trudgett
Subject: Re: my first Lisp code...comments welcome
Date:
Message-ID: <m3hdgllodh.fsf@rr.trudgett>
"Tayssir John Gabbour" <···········@yahoo.com> writes:
> That sounds like a good strategy when dealing with multiple languages,
> with their own crazy eccentricities, when you feel like being
> conservative.
Thank you! ;-)
> I often write a quick comment when I'm doing something
> like that, when I think I'm being anti-idiomatic yet correct, but am
> not interested in breaking my flow by looking something up in some
> manual.
Yeah, that's the thing. As a newbie, I already break my flow far too
often to look up docs! Oh well...
>
> Stephen King had similar advice for writers. But as he says, you later
> on want to go back and clean it up. So it won't be jarring and
> confusing to readers.
Luckily, it should be easy to find and replace all occurrences of
(list).
David
--
David Trudgett
http://www.zeta.org.au/~wpower/
Viking, n.:
1. Daring Scandinavian seafarers, explorers, adventurers,
entrepreneurs world-famous for their aggressive, nautical
import business, highly leveraged takeovers and blue eyes.
2. Bloodthirsty sea pirates who ravaged northern Europe
beginning in the 9th century.
Hagar's note: The first definition is much preferred; the
second is used only by malcontents, the envious, and disgruntled
owners of waterfront property.