Prev: the Modernization of Emacs
Next: Clipboard Access on Windows
From: joswig on 20 Jun 2006 14:33

Frank Buss wrote:
> joswig(a)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, fb(a)frank-buss.de
> http://www.frank-buss.de, http://www.it4-systems.de

From: Frank Buss on 26 Jun 2006 16:28
joswig(a)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, fb(a)frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
From: Rainer Joswig on 26 Jun 2006 19:46
Am 26.06.2006 22:28 Uhr schrieb "Frank Buss" unter <fb(a)frank-buss.de> in
pvyi2g18y73m$.a94ixhwfcotg.dlg(a)40tude.net:

> joswig(a)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)

?

From: Rob Warnock on 27 Jun 2006 05:01
Frank Buss <fb(a)frank-buss.de> wrote:
+---------------
| joswig(a)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(a)rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607

From: Pascal Bourguignon on 27 Jun 2006 07:45
rpw3(a)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
First  |  Prev  | 
Pages: 1 2 3
Prev: the Modernization of Emacs
Next: Clipboard Access on Windows