I was browsing around lazily when I came across the List comprehensions
article in Wikipedia:
http://en.wikipedia.org/wiki/List_comprehensions
I looked at the first few lines and I sighed "oh how close-to-natural
in terms of mathematical notation! But it looks like Haskell, how would
it be in Common Lisp?"
After showing this to one of my fellow Turkish Lispers, HB, he told me that
he had just found a paper by Guy Lapalme [1], written in 1991 with a title
of "Implementation of a Lisp comprehension macro":
http://rali.iro.umontreal.ca/Publications/urls/LapalmeLispComp.pdf
We both rushed to our Emacsen + SLIMEs, typed the code:
http://paste.lisp.org/display/21380
and then saw that we were able to write similar list comprehension
code like that:
CL-USER> [x (x <- '(1 2 3)) (oddp x)]
(1 3)
CL-USER> [(list x y) (x <- '(a b c)) (y <- '(1 2 3))]
((A 1) (A 2) (A 3) (B 1) (B 2) (B 3) (C 1) (C 2) (C 3))
(The paper also included the classical QuickSort implementation
that used this list comprehension notation).
Once again I understood why Lisp is called a "programmable
programming language."
In the conclusion, author mentions advantages and drawbacks of
the implementation of this notation, he also compares it to
the Series.
Since the article was written about 15 years ago, I just wondered
if this macro became a part of a frequently used package.
Maybe Lispers who know much more will tell us more about
this subject?
1- http://www.iro.umontreal.ca/~lapalme/
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http://emba.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
>
> CL-USER> [x (x <- '(1 2 3)) (oddp x)]
> (1 3)
>
CL-USER> (loop for x in (list 1 2 3) when (oddp x) collect x)
(1 3)
LOOP does some kind of list comprehension aswell, without an additional
software.
Jonathan Heusser schrieb:
> >
> > CL-USER> [x (x <- '(1 2 3)) (oddp x)]
> > (1 3)
> >
> CL-USER> (loop for x in (list 1 2 3) when (oddp x) collect x)
> (1 3)
>
> LOOP does some kind of list comprehension aswell, without an additional
> software.
For combinations of this kind of stuff I really prefer the functional
approach:
CL-USER 5 > (remove-if-not 'oddp '(1 2 3))
(1 3)
······@corporate-world.lisp.de wrote:
> For combinations of this kind of stuff I really prefer the functional
> approach:
> CL-USER 5 > (remove-if-not 'oddp '(1 2 3))
> (1 3)
I know it is possible, but I'm not sure aboout how to write the following
with a functional approach:
> (loop for i from 1 to 10 collect (loop for j from 1 to i collect j))
((1) (1 2) (1 2 3) (1 2 3 4) (1 2 3 4 5) (1 2 3 4 5 6) (1 2 3 4 5 6 7) (1 2
3 4 5 6 7 8) (1 2 3 4 5 6 7 8 9) (1 2 3 4 5 6 7 8 9 10))
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss <··@frank-buss.de> writes:
> I know it is possible, but I'm not sure aboout how to write the following
> with a functional approach:
>
>> (loop for i from 1 to 10 collect (loop for j from 1 to i collect j))
> ((1) (1 2) (1 2 3) (1 2 3 4) (1 2 3 4 5) (1 2 3 4 5 6) (1 2 3 4 5 6 7) (1 2
> 3 4 5 6 7 8) (1 2 3 4 5 6 7 8 9) (1 2 3 4 5 6 7 8 9 10))
It's a matter of appropriate building blocks. For example:
- an arithmetic sequence (range)
- map
- conversion of a sequence to a list
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Frank Buss wrote:
> ······@corporate-world.lisp.de wrote:
>
> > For combinations of this kind of stuff I really prefer the functional
> > approach:
> > CL-USER 5 > (remove-if-not 'oddp '(1 2 3))
> > (1 3)
>
> I know it is possible, but I'm not sure aboout how to write the following
> with a functional approach:
>
> > (loop for i from 1 to 10 collect (loop for j from 1 to i collect j))
> ((1) (1 2) (1 2 3) (1 2 3 4) (1 2 3 4 5) (1 2 3 4 5 6) (1 2 3 4 5 6 7) (1 2
> 3 4 5 6 7 8) (1 2 3 4 5 6 7 8 9) (1 2 3 4 5 6 7 8 9 10))
This looks like a simple recursive problem. A typical task for
Functional
Programming.
Did you ever read SICP? After reading that book, writing that code in
a functional style would be easy...
In a simple style I would
a) generate a list of 1 to 10
b) map over that list and generate sublists that go from 1 to n
Often the function to generate integers from 0..n is called IOTA:
here is the definition from AIMA:
(defun iota (n &optional (start-at 0))
"Return a list of n consecutive integers, by default starting at 0."
(if (<= n 0) nil (cons start-at (iota (- n 1) (+ start-at 1)))))
CL-USER 3 > (iota 10 1)
(1 2 3 4 5 6 7 8 9 10)
Mapping over a list and returning a list of results is done with
MAPCAR:
CL-USER 4 > (mapcar (lambda (n) (iota n 1)) (iota 10 1))
((1) (1 2) (1 2 3) (1 2 3 4) (1 2 3 4 5) (1 2 3 4 5 6) (1 2 3 4 5 6 7)
(1 2 3 4 5 6 7 8) (1 2 3 4 5 6 7 8 9) (1 2 3 4 5 6 7 8 9 10))
>
> --
> Frank Buss, ··@frank-buss.de
> http://www.frank-buss.de, http://www.it4-systems.de
······@corporate-world.lisp.de wrote:
> In a simple style I would
>
> a) generate a list of 1 to 10
> b) map over that list and generate sublists that go from 1 to n
>
> Often the function to generate integers from 0..n is called IOTA:
>
> here is the definition from AIMA:
>
> (defun iota (n &optional (start-at 0))
> "Return a list of n consecutive integers, by default starting at 0."
> (if (<= n 0) nil (cons start-at (iota (- n 1) (+ start-at 1)))))
This should be written in Common Lisp like this:
(defun iota (n &optional (start-at 0))
"Return a list of n consecutive integers, by default starting at 0."
(when (> n 0) (cons start-at (iota (1- n) (1+ start-at)))))
> Mapping over a list and returning a list of results is done with
> MAPCAR:
>
> CL-USER 4 > (mapcar (lambda (n) (iota n 1)) (iota 10 1))
> ((1) (1 2) (1 2 3) (1 2 3 4) (1 2 3 4 5) (1 2 3 4 5 6) (1 2 3 4 5 6 7)
> (1 2 3 4 5 6 7 8) (1 2 3 4 5 6 7 8 9) (1 2 3 4 5 6 7 8 9 10))
Nice. Another solution with more higher order functions:
(defun iota ()
(lambda (n &optional (start-at 0))
(let ((end (+ n start-at)))
(labels ((next (n)
(when (< n end) (cons n (next (1+ n))))))
(next start-at)))))
; alternative:
(defun non-recursive-iota ()
(lambda (n &optional (start-at 0))
(loop for i from start-at below (+ start-at n) collect i)))
(defun iota-from-1 ()
(lambda (n)
(funcall (iota) n 1)))
(defun test ()
(mapcar (iota-from-1) (funcall (iota-from-1) 10)))
(no currying in Common Lisp without libraries like ARNESI, so there is no
way to write the first argument to mapcar much easier than with a lambda)
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Am 26.06.2006 22:28 Uhr schrieb "Frank Buss" unter <··@frank-buss.de> in
······························@40tude.net:
> ······@corporate-world.lisp.de wrote:
>
>> In a simple style I would
>>
>> a) generate a list of 1 to 10
>> b) map over that list and generate sublists that go from 1 to n
>>
>> Often the function to generate integers from 0..n is called IOTA:
>>
>> here is the definition from AIMA:
>>
>> (defun iota (n &optional (start-at 0))
>> "Return a list of n consecutive integers, by default starting at 0."
>> (if (<= n 0) nil (cons start-at (iota (- n 1) (+ start-at 1)))))
>
> This should be written in Common Lisp like this:
>
> (defun iota (n &optional (start-at 0))
> "Return a list of n consecutive integers, by default starting at 0."
> (when (> n 0) (cons start-at (iota (1- n) (1+ start-at)))))
Not really. It is no improvement to use WHEN over IF ... NIL.
It is also no improvement to use -1 of (- ... 1). These are
basically useless improvements. The IF version makes clear that
the NIL result is really a wanted result. Additionally
in most self-respecting Lisps 1+ will not make any difference
to (+ 1 ...) .
>
>> Mapping over a list and returning a list of results is done with
>> MAPCAR:
>>
>> CL-USER 4 > (mapcar (lambda (n) (iota n 1)) (iota 10 1))
>> ((1) (1 2) (1 2 3) (1 2 3 4) (1 2 3 4 5) (1 2 3 4 5 6) (1 2 3 4 5 6 7)
>> (1 2 3 4 5 6 7 8) (1 2 3 4 5 6 7 8 9) (1 2 3 4 5 6 7 8 9 10))
>
> Nice. Another solution with more higher order functions:
>
> (defun iota ()
> (lambda (n &optional (start-at 0))
> (let ((end (+ n start-at)))
> (labels ((next (n)
> (when (< n end) (cons n (next (1+ n))))))
> (next start-at)))))
Well, IOTA is usually defined as a function that returns a vector (or LIST
in case of Lisp). And not as a function that returns a function. The
introduction of yet another LAMBDA is also useless. See below.
(defun iota (n &optional (start-at 0))
(let ((end (+ n start-at)))
(labels ((next (n)
(when (< n end) (cons n (next (1+ n))))))
(next start-at))))
> ; alternative:
> (defun non-recursive-iota ()
> (lambda (n &optional (start-at 0))
> (loop for i from start-at below (+ start-at n) collect i)))
>
> (defun iota-from-1 ()
> (lambda (n)
> (funcall (iota) n 1)))
(defun iota-from-1 (n)
(iota n 1))
>
> (defun test ()
> (mapcar (iota-from-1) (funcall (iota-from-1) 10)))
This version here is simpler. The function is directly used.
(defun test ()
(mapcar #'iota-from-1 (iota-from-1 10)))
If you wanted you can use arbitrary deep functions. Unless there is a reason
for it, and I don't see it here, I would stay away from that. Higher
Order does not mean cooler. ;-) In this case it is easy to detect.
Your toplevel function just returns another function without closing over
a variable. That's useless mostly. You could have used the toplevel function
directly.
What you may have wanted is a IOTA function generator:
(defun make-iota-function (&optional (start-at 0))
(lambda (n)
(let ((end (+ n start-at)))
(labels ((next (n)
(when (< n end) (cons n (next (1+ n))))))
(next start-at)))))
(setf (symbol-function 'iota-from-1)
(make-iota-function 1))
(defun test ()
(mapcar #'iota-from-1 (iota-from-1 10)))
Or
(defun test ()
(let ((iota-from-1-function (make-iota-function 1)))
(mapcar iota-from-1-function
(funcall iota-from-1-function 10))))
> (no currying in Common Lisp without libraries like ARNESI, so there is no
> way to write the first argument to mapcar much easier than with a lambda)
?
Frank Buss <··@frank-buss.de> wrote:
+---------------
| ······@corporate-world.lisp.de wrote:
| > Often the function to generate integers from 0..n is called IOTA:
| > here is the definition from AIMA:
| > (defun iota (n &optional (start-at 0))
| > "Return a list of n consecutive integers, by default starting at 0."
| > (if (<= n 0) nil (cons start-at (iota (- n 1) (+ start-at 1)))))
|
| This should be written in Common Lisp like this:
| (defun iota (n &optional (start-at 0))
| "Return a list of n consecutive integers, by default starting at 0."
| (when (> n 0) (cons start-at (iota (1- n) (1+ start-at)))))
+---------------
Personally, I prefer this version:
(defun iota (count &optional (start 0) (step 1))
(loop repeat count for i upfrom start by step collect i))
Besides the obvious uses:
> (iota 5)
(0 1 2 3 4)
> (iota 5 3)
(3 4 5 6 7)
> (iota 5 3 3)
(3 6 9 12 15)
>
it can be used for other things as well:
> (iota 5 3 0)
(3 3 3 3 3)
> (iota 5 5 -1)
(5 4 3 2 1)
>
Though note that these latter cases technically violate the CLHS
requirement that LOOP's BY prepositions's value be positive:
6.1.2.1.1 The for-as-arithmetic subclause
...
BY The loop keyword BY marks the increment or decrement
supplied by FORM3. The value of FORM3 can be any
positive number. The default value is 1.
Both cases work in CMUCL & CLISP. Is there a CL implementation
that does *not* accept zero and/or negative BY values?
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
····@rpw3.org (Rob Warnock) writes:
> Personally, I prefer this version:
>
> (defun iota (count &optional (start 0) (step 1))
> (loop repeat count for i upfrom start by step collect i))
> [...]
> Though note that these latter cases technically violate the CLHS
> requirement that LOOP's BY prepositions's value be positive:
>
> 6.1.2.1.1 The for-as-arithmetic subclause
> ...
> BY The loop keyword BY marks the increment or decrement
> supplied by FORM3. The value of FORM3 can be any
> positive number. The default value is 1.
>
> Both cases work in CMUCL & CLISP. Is there a CL implementation
> that does *not* accept zero and/or negative BY values?
You can easily make it conformant:
(defun iota (count &optional (start 0) (step 1))
(cond
((minusp step)
(loop :repeat count :for i :downfrom start :by (- step) :collect i))
((plusp step)
(loop :repeat count :for i :upfrom start :by step :collect i))
(t
(loop :repeat count :collect start))))
(mapcar (lambda (step) (iota 5 10 step)) '(-1 0 1))
--> ((10 9 8 7 6) (10 10 10 10 10) (10 11 12 13 14))
--
__Pascal Bourguignon__ http://www.informatimago.com/
Pour moi, la grande question n'a jamais �t�: �Qui suis-je? O� vais-je?�
comme l'a formul� si adroitement notre ami Pascal, mais plut�t:
�Comment vais-je m'en tirer?� -- Jean Yanne
Jonathan Heusser <·····@drugphish.ch> writes:
>>
>> CL-USER> [x (x <- '(1 2 3)) (oddp x)]
>> (1 3)
>>
> CL-USER> (loop for x in (list 1 2 3) when (oddp x) collect x)
> (1 3)
>
> LOOP does some kind of list comprehension aswell, without an additional
> software.
Certainly it does. However I'd still be happy to have alternatives
and "more natural" (whatever that means, at least it rings some
bells for me ;-)) syntax as well as a more compact and concise one.
LOOP construct of CL has a very nice English-like syntax
but the one presented in the paper I mentioned in my original post
also provides a good syntax for the mathematically inclined.
Happy hacking,
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http://emba.www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
"Emre Sevinc" <·····@bilgi.edu.tr> wrote
>> LOOP does some kind of list comprehension aswell, without an additional
>> software.
>
> Certainly it does. However I'd still be happy to have alternatives
> and "more natural" (whatever that means, at least it rings some
> bells for me ;-)) syntax as well as a more compact and concise one.
>
> LOOP construct of CL has a very nice English-like syntax
> but the one presented in the paper I mentioned in my original post
> also provides a good syntax for the mathematically inclined.
Here are other list comprehension librairies:
http://www.cl-user.net/asp/search?search=comprehension
Marc
Marc Battyani wrote:
> "Emre Sevinc" <·····@bilgi.edu.tr> wrote
>>> LOOP does some kind of list comprehension aswell, without an additional
>>> software.
>> Certainly it does. However I'd still be happy to have alternatives
>> and "more natural" (whatever that means, at least it rings some
>> bells for me ;-)) syntax as well as a more compact and concise one.
>>
>> LOOP construct of CL has a very nice English-like syntax
>> but the one presented in the paper I mentioned in my original post
>> also provides a good syntax for the mathematically inclined.
>
> Here are other list comprehension librairies:
> http://www.cl-user.net/asp/search?search=comprehension
See also http://p-cos.net/lisp-ecoop/submissions/Nystrom.pdf
Pascal
--
3rd European Lisp Workshop
July 3 - Nantes, France - co-located with ECOOP 2006
http://lisp-ecoop06.bknr.net/
Emre Sevinc wrote:
> Jonathan Heusser <·····@drugphish.ch> writes:
>
>>> CL-USER> [x (x <- '(1 2 3)) (oddp x)]
>>> (1 3)
>>>
>> CL-USER> (loop for x in (list 1 2 3) when (oddp x) collect x)
>> (1 3)
>
> Certainly it does. However I'd still be happy to have alternatives
> and "more natural" (whatever that means, at least it rings some
> bells for me ;-)) syntax as well as a more compact and concise one.
>
all a matter of taste which version is more natural/readable, right ;)