Hi, I'm working on this particular problem in my text:
Define a recursive function double that takes a list in which all
atoms are numbers. The function doubles all numbers at every level in
the list.
Tests of the function double:
(double NIL) ; NIL
(double 3) ; 6
(double '(1 2 3)) ; (2 4 6)
(double ' (1 (2 3) ((4) (5 6 (7))))) ; (2 (4 6) ((8) (10 12
(14))))
And here's what I worked out:
(defun double (lst)
(if (null lst)
Nil
(if (atom (first lst))
(cons (* 2 (first lst)) (double (cdr lst)))
(cons (double (first lst)) (double (cdr lst))))))
I tried out a few of the examples given above and seem to get correct
answers:
[42]> (double NIL)
NIL
[43]> (double '(1 2 3))
(2 4 6)
[44]> (double ' (1 (2 3) ((4) (5 6 (7)))))
(2 (4 6) ((8) (10 12 (14))))
What I would like to know is if I can write this program in a better
way ?
On Apr 14, 1:22 pm, pereges <·······@gmail.com> wrote:
> Hi, I'm working on this particular problem in my text:
>
> Define a recursive function double that takes a list in which all
> atoms are numbers. The function doubles all numbers at every level in
> the list.
G'day. Thought you might like a newLISP response.
(define (double (x))
(if (list? x) (map double x) (if (not (nil? x)) (* x 2))))
(double nil)
(double 3)
(double '(1 2 3))
(double ' (1 (2 3) ((4) (5 6 (7)))))
outputs:
nil
6
(2 4 6)
(2 (4 6) ((8) (10 12 (14))))
Kind regards,
Bruce.
From: Pascal J. Bourguignon
Subject: Re: doubling list elements at every level using recursion
Date:
Message-ID: <87y6u3iwwe.fsf@galatea.local>
pereges <·······@gmail.com> writes:
> Hi, I'm working on this particular problem in my text:
>
> Define a recursive function double that takes a list in which all
> atoms are numbers. The function doubles all numbers at every level in
> the list.
>
> Tests of the function double:
>
> (double NIL) ; NIL
> (double 3) ; 6
> (double '(1 2 3)) ; (2 4 6)
> (double ' (1 (2 3) ((4) (5 6 (7))))) ; (2 (4 6) ((8) (10 12
> (14))))
>
>
>
> And here's what I worked out:
>
> (defun double (lst)
> (if (null lst)
> Nil
> (if (atom (first lst))
> (cons (* 2 (first lst)) (double (cdr lst)))
> (cons (double (first lst)) (double (cdr lst))))))
>
> I tried out a few of the examples given above and seem to get correct
> answers:
>
> [42]> (double NIL)
> NIL
> [43]> (double '(1 2 3))
> (2 4 6)
> [44]> (double ' (1 (2 3) ((4) (5 6 (7)))))
> (2 (4 6) ((8) (10 12 (14))))
>
> What I would like to know is if I can write this program in a better
> way ?
Yes.
You could slightly generalize double, and accept any atoms. This would
allow you to simplify it.
You could also use emacs and let it do the indentation for you!
(defun double (object)
(typecase object
(cons (cons (double (car object)) (double (cdr object))))
(number (* 2 object))
(t object)))
(mapcar (function double)
'( () abc 123 (1 2.0 #C(3 4) a b c (5/2 6 d e f) 7 8 9) ))
--> (NIL ABC 246 (2 4.0 #C(6 8) A B C (5 12 D E F) 14 16 18))
--
__Pascal Bourguignon__
thanks for all suggestions!
can someone also help me with a similar problem:
4. Define an iterative function idouble that takes a list. The
function idouble doubles every number at the top level in its argument
and does not alter other members of the argument.
Tests of idouble:
(idouble nil) ; NIL
(idouble '(1 2 3)) ; (2 4 6)
(idouble '(1 (2) 3)) ; (2 (2) 6)
(idouble '(1 4 a e b 6)) ; (2 8 A E B 12)
In this problem I cannot figure out how to iterate through a list
while at the same time modify its contents. This is the code I tried:
(defun idouble (lst)
(if (null lst)
NIL
(dolist (x lst)
(if (number p x)
(cons (* 2 x) (cdr lst))
(cons x (cdr lst)))))
On Apr 14, 2:43 pm, pereges <·······@gmail.com> wrote:
> thanks for all suggestions!
>
> can someone also help me with a similar problem:
>
> 4. Define an iterative function idouble that takes a list. The
> function idouble doubles every number at the top level in its argument
> and does not alter other members of the argument.
> Tests of idouble:
And again, in newLISP:
(define (idouble (x))
(if (list? x)
(map idouble x)
(if (not (nil? x))
(if (< (sys-info 3) 12)
(if (number? x)
(* x 2)
x
)
x
)
)
)
)
(idouble nil) ; nil
(idouble '(1 2 3)) ; (2 4 6)
(idouble '(1 (2) 3)) ; (2 (2) 6)
(idouble '(1 4 a e b 6)) ; (2 8 a e b 12)
I fancy there's a better way than checking the recursion depth, but I
don't yet know what that might be.
Kind regards,
Bruce.
On Apr 13, 8:43 pm, pereges <·······@gmail.com> wrote:
> thanks for all suggestions!
>
> can someone also help me with a similar problem:
>
> 4. Define an iterative function idouble that takes a list. The
> function idouble doubles every number at the top level in its argument
> and does not alter other members of the argument.
> Tests of idouble:
>
> (idouble nil) ; NIL
> (idouble '(1 2 3)) ; (2 4 6)
> (idouble '(1 (2) 3)) ; (2 (2) 6)
> (idouble '(1 4 a e b 6)) ; (2 8 A E B 12)
>
> In this problem I cannot figure out how to iterate through a list
> while at the same time modify its contents. This is the code I tried:
>
> (defun idouble (lst)
> (if (null lst)
> NIL
> (dolist (x lst)
> (if (number p x)
> (cons (* 2 x) (cdr lst))
> (cons x (cdr lst)))))
You need to be careful about the language you're using to describe the
goal because it will affect how you approach it. Your text may have
gotten you started down the wrong path by talking about altering the
argument. But what you are trying to do is not so much modify the
elements of a list but rather create a new list containing transformed
elements of the first list. This transformation process is known as a
mapping. For example, we can map the list (1 2 3 4) to its successors
(2 3 4 5) by creating a new list with 1 added to each element of the
input.
You want to take a look at the Common Lisp mapping functions,
specifically the one that operates on the elements of a list (rather
than the sublists of a list). This mapping function also requires you
to mention what sort of transformation you want done. In other words,
you have to provide it with a function that transforms elements. In
this case your transformation has two considerations: elements that
are numbers get doubled and other elements are simply gathered "as
is".
Aloha,
David Sletten
From: Thomas A. Russ
Subject: Re: doubling list elements at every level using recursion
Date:
Message-ID: <ymid4bfgkil.fsf@blackcat.isi.edu>
pereges <·······@gmail.com> writes:
> thanks for all suggestions!
>
> can someone also help me with a similar problem:
>
> 4. Define an iterative function idouble that takes a list. The
> function idouble doubles every number at the top level in its argument
> and does not alter other members of the argument.
> Tests of idouble:
>
> (idouble nil) ; NIL
> (idouble '(1 2 3)) ; (2 4 6)
> (idouble '(1 (2) 3)) ; (2 (2) 6)
> (idouble '(1 4 a e b 6)) ; (2 8 A E B 12)
>
>
> In this problem I cannot figure out how to iterate through a list
> while at the same time modify its contents. This is the code I tried:
>
Indenting the code helps readability:
> (defun idouble (lst)
> (if (null lst)
> NIL
> (dolist (x lst)
> (if (numberp x)
> (cons (* 2 x) (cdr lst))
> (cons x (cdr lst))))))
OK.
The fundamental problem that you are having is that the IF statement in
the DOLIST form is computing what you want. But you aren't saving that
answer anywhere. It is being computed and then ignored.
For an iterative solution, you have to arrange to somehow collect the
values that you are computing. That will often require that you
establish a variable binding using LET and then appropriately manipulate
that variable.
One standard method is to iterate down a list and collect the answer
backwards, followed by a reverse at the end. This is done because it is
much more efficient than trying to always add on to the end of the
list using APPEND. You might want to look at the PUSH macro and the
REVERSE function for that.
Use append and you end up like Schlemiel the painter:
http://discuss.fogcreek.com/techInterview/default.asp?cmd=show&ixPost=153
http://en.wikipedia.org/wiki/Schlemiel_the_painter's_Algorithm
Other alternatives are to use LOOP which does this for you with the
COLLECT clause, or to use MAPCAR, which is perhaps even simpler for this
particular problem, particularly if you encapsulate your transformation
into a function:
(defun double-number (x)
(if (numberp x)
(* 2 x)
x))
--
Thomas A. Russ, USC/Information Sciences Institute
On Apr 14, 8:43 am, pereges <·······@gmail.com> wrote:
> thanks for all suggestions!
>
> can someone also help me with a similar problem:
>
> 4. Define an iterative function idouble that takes a list. The
> function idouble doubles every number at the top level in its argument
> and does not alter other members of the argument.
> Tests of idouble:
>
> (idouble nil) ; NIL
> (idouble '(1 2 3)) ; (2 4 6)
> (idouble '(1 (2) 3)) ; (2 (2) 6)
> (idouble '(1 4 a e b 6)) ; (2 8 A E B 12)
>
> In this problem I cannot figure out how to iterate through a list
> while at the same time modify its contents. This is the code I tried:
>
> (defun idouble (lst)
> (if (null lst)
> NIL
> (dolist (x lst)
> (if (number p x)
> (cons (* 2 x) (cdr lst))
> (cons x (cdr lst)))))
I hope this isn't a homework
(defun idouble (x)
(mapcar #'(lambda (n) (if (numberp n) (* 2 n) n)) x))
CL-USER 2 > (idouble nil)
NIL
CL-USER 3 > (idouble '(1 2 3))
(2 4 6)
CL-USER 4 > (idouble '(1 (2) 3))
(2 (2) 6)
CL-USER 5 > (idouble '(1 4 a e b 6))
(2 8 A E B 12)
bobi
http://tourdelisp.blogspot.com/
On Apr 14, 8:53 pm, Slobodan Blazeski <·················@gmail.com>
wrote:
> On Apr 14, 8:43 am, pereges <·······@gmail.com> wrote:
>
>
>
>
>
> > thanks for all suggestions!
>
> > can someone also help me with a similar problem:
>
> > 4. Define an iterative function idouble that takes a list. The
> > function idouble doubles every number at the top level in its argument
> > and does not alter other members of the argument.
> > Tests of idouble:
>
> > (idouble nil) ; NIL
> > (idouble '(1 2 3)) ; (2 4 6)
> > (idouble '(1 (2) 3)) ; (2 (2) 6)
> > (idouble '(1 4 a e b 6)) ; (2 8 A E B 12)
>
> > In this problem I cannot figure out how to iterate through a list
> > while at the same time modify its contents. This is the code I tried:
>
> > (defun idouble (lst)
> > (if (null lst)
> > NIL
> > (dolist (x lst)
> > (if (number p x)
> > (cons (* 2 x) (cdr lst))
> > (cons x (cdr lst)))))
>
> I hope this isn't a homework
> (defun idouble (x)
> (mapcar #'(lambda (n) (if (numberp n) (* 2 n) n)) x))
>
> CL-USER 2 > (idouble nil)
> NIL
>
> CL-USER 3 > (idouble '(1 2 3))
> (2 4 6)
>
> CL-USER 4 > (idouble '(1 (2) 3))
> (2 (2) 6)
>
> CL-USER 5 > (idouble '(1 4 a e b 6))
> (2 8 A E B 12)
>
> bobihttp://tourdelisp.blogspot.com/
Wait the minute what do you mean by iterative solution?
(defun idouble (x)
(let (res)
(dolist (e x (nreverse res))
(push (if (numberp e) (* 2 e) e) res))))
bobi
From: Giorgos Keramidas
Subject: Re: doubling list elements at every level using recursion
Date:
Message-ID: <87k55neqet.fsf@kobe.laptop>
On Mon, 13 Apr 2009 22:22:39 -0700 (PDT), pereges <·······@gmail.com> wrote:
> Hi, I'm working on this particular problem in my text:
>
> Define a recursive function double that takes a list in which all
> atoms are numbers. The function doubles all numbers at every level in
> the list.
>
> Tests of the function double:
>
> (double NIL) ; NIL
> (double 3) ; 6
> (double '(1 2 3)) ; (2 4 6)
> (double ' (1 (2 3) ((4) (5 6 (7))))) ; (2 (4 6) ((8) (10 12 (14))))
>
> And here's what I worked out:
>
> (defun double (lst)
> (if (null lst)
> nil
> (if (atom (first lst))
> (cons (* 2 (first lst)) (double (cdr lst)))
> (cons (double (first lst)) (double (cdr lst))))))
...
> What I would like to know is if I can write this program in a better
> way ?
Whenever I see a nested list of IF expressions I stop a bit and try to
think if there is a way to use COND for the same result:
> (defun double (list)
(cond ((null list) nil)
((atom list) (* 2 list))
(t (cons (double (car list))
(double (cdr list))))))
DOUBLE
> (defun test-double (input expected)
(equal (double input) expected))
TEST-DOUBLE
> (mapcar (lambda (pair)
(apply #'test-double pair))
'((nil nil)
(3 6)
((1 2 3) (2 4 6))
((1 (2 3) ((4) (5 6 (7))))
(2 (4 6) ((8) (10 12 (14)))))))
(T T T T)
> What I would like to know is if I can write this program in a better way ?
Abstraction is your friend. Here we can abstract out the idea of
recursively applying a function to the leaves of a tree:
(defun mapleaves (fn tree)
(when tree
(if (consp tree)
(cons
(mapleaves fn (car tree))
(mapleaves fn (cdr tree)))
(funcall fn tree))))
And now, doubling every number in a list of lists becomes trivial:
(defun double (tree)
(mapleaves (lambda (x) (* 2 x)) tree))
Testing:
[3]> (double '(nil 1 2 ((3 (4 ((5) 6))) 7 nil) nil))
(NIL 2 4 ((6 (8 ((10) 12))) 14 NIL) NIL)
> can someone also help me with a similar problem ... In this problem I cannot figure out how to iterate through a list while at the same time modify its contents.
(defun idouble (list)
(loop for item in list collect (if (numberp item) (* 2 item) item)))
(defun idouble (list)
(mapcar (lambda (item) (if (numberp item) (* 2 item) item)))
If you actually have a reason to *modify* the list instead of consing
up a new one, it's much more difficult.
On Apr 14, 7:32 pm, main <·············@gmail.com> wrote:
> > What I would like to know is if I can write this program in a better way ?
>
> Abstraction is your friend. Here we can abstract out the idea of
> recursively applying a function to the leaves of a tree:
>
> (defun mapleaves (fn tree)
> (when tree
> (if (consp tree)
> (cons
> (mapleaves fn (car tree))
> (mapleaves fn (cdr tree)))
> (funcall fn tree))))
>
> And now, doubling every number in a list of lists becomes trivial:
>
> (defun double (tree)
> (mapleaves (lambda (x) (* 2 x)) tree))
>
> Testing:
>
> [3]> (double '(nil 1 2 ((3 (4 ((5) 6))) 7 nil) nil))
> (NIL 2 4 ((6 (8 ((10) 12))) 14 NIL) NIL)
>
> > can someone also help me with a similar problem ... In this problem I cannot figure out how to iterate through a list while at the same time modify its contents.
>
> (defun idouble (list)
> (loop for item in list collect (if (numberp item) (* 2 item) item)))
>
> (defun idouble (list)
> (mapcar (lambda (item) (if (numberp item) (* 2 item) item)))
>
> If you actually have a reason to *modify* the list instead of consing
> up a new one, it's much more difficult.
Sorry should have read the rest of the thread before posting :)
bobi
From: William James
Subject: Re: doubling list elements at every level using recursion
Date:
Message-ID: <gs82r101rir@enews4.newsguy.com>
main wrote:
> Abstraction is your friend. Here we can abstract out the idea of
> recursively applying a function to the leaves of a tree:
>
> (defun mapleaves (fn tree)
> (when tree
> (if (consp tree)
> (cons
> (mapleaves fn (car tree))
> (mapleaves fn (cdr tree)))
> (funcall fn tree))))
>
> And now, doubling every number in a list of lists becomes trivial:
>
> (defun double (tree)
> (mapleaves (lambda (x) (* 2 x)) tree))
>
> Testing:
>
> [3]> (double '(nil 1 2 ((3 (4 ((5) 6))) 7 nil) nil))
> (NIL 2 4 ((6 (8 ((10) 12))) 14 NIL) NIL)
For mapping, use map.
Ruby:
def map_leaves tree, &block
tree.map{ |x|
if x.class == Array
map_leaves x, &block
else
yield x
end }
end
==>nil
map_leaves( [1,[2,[3]],4] ){|n| n * 2}
==>[2, [4, [6]], 8]
--
Common Lisp is a significantly ugly language. --- Dick Gabriel
The good news is, it's not Lisp that sucks, but Common Lisp.
--- Paul Graham
Common LISP is the PL/I of Lisps. --- Jeffrey M. Jacobs
On Apr 16, 10:01 pm, "William James" <> wrote:
> main wrote:
> > Abstraction is your friend. Here we can abstract out the idea of
> > recursively applying a function to the leaves of a tree:
>
> > (defun mapleaves (fn tree)
> > (when tree
> > (if (consp tree)
> > (cons
> > (mapleaves fn (car tree))
> > (mapleaves fn (cdr tree)))
> > (funcall fn tree))))
>
> > And now, doubling every number in a list of lists becomes trivial:
>
> > (defun double (tree)
> > (mapleaves (lambda (x) (* 2 x)) tree))
>
> > Testing:
>
> > [3]> (double '(nil 1 2 ((3 (4 ((5) 6))) 7 nil) nil))
> > (NIL 2 4 ((6 (8 ((10) 12))) 14 NIL) NIL)
>
> For mapping, use map.
>
> Ruby:
>
> def map_leaves tree, &block
> tree.map{ |x|
> if x.class == Array
> map_leaves x, &block
> else
> yield x
> end }
> end
> ==>nil
> map_leaves( [1,[2,[3]],4] ){|n| n * 2}
> ==>[2, [4, [6]], 8]
>
> --
> Common Lisp is a significantly ugly language. --- Dick Gabriel
> The good news is, it's not Lisp that sucks, but Common Lisp.
> --- Paul Graham
> Common LISP is the PL/I of Lisps. --- Jeffrey M. Jacobs
Yes. But Gabriel, Graham and Jacobs did their homework! You have
not handed in a single line of of it.
Cheers
--
Marco
From: eric-and-jane-smith
Subject: Re: doubling list elements at every level using recursion
Date:
Message-ID: <1rVFl.17289$g%5.8332@newsfe23.iad>
"William James" <> wrote in ················@enews4.newsguy.com:
> Common Lisp is a significantly ugly language. --- Dick Gabriel
If Common Lisp is too ugly for you, you should try Commune Lisp. It's
much prettier.
> The good news is, it's not Lisp that sucks, but Common Lisp.
> --- Paul Graham
Ask PG how much Ruby sucks. And ask him why, if Common Lisp really
sucks, he used it to earn his fortune. It's wise to pay more attention
to what people do than to what they say.
> Common LISP is the PL/I of Lisps. --- Jeffrey M. Jacobs
I liked PL/I, but I like CL more.
The goal of any good programming language is that most of the programming
work should be done by the computer, so the programmer's efforts are
leveraged as much as possible. That's what programming productivity
really is. When the computer does most of your work for you, you have a
lot of spare time. You can then spend that spare time working on ways to
make the computer do even more of your work for you. That's the big
advantage of CL. It doesn't matter how ugly it is, only how much time
and money it saves. Programming should not be an end in itself, but a
means to an end, and therefore the beauty of the language is incidental.
Ruby is nice for quick and dirty scripting, but not for serious
programming. The bigger the project, the more you need Common Lisp, and
the more time and money it could save you.
From: Thomas A. Russ
Subject: Re: doubling list elements at every level using recursion
Date:
Message-ID: <ymihc0rgkxb.fsf@blackcat.isi.edu>
pereges <·······@gmail.com> writes:
> Hi, I'm working on this particular problem in my text:
>
> Define a recursive function double that takes a list in which all
> atoms are numbers. The function doubles all numbers at every level in
> the list.
>
> Tests of the function double:
> ..
> (double 3) ; 6
> ...
> And here's what I worked out:
>
> (defun double (lst)
> (if (null lst)
> Nil
> (if (atom (first lst))
> (cons (* 2 (first lst)) (double (cdr lst)))
> (cons (double (first lst)) (double (cdr lst))))))
>
> I tried out a few of the examples given above and seem to get correct
> answers:
But you didn't try it on
(double 3)
It will fail, so you have a small bug in your code.
> [42]> (double NIL)
> NIL
> [43]> (double '(1 2 3))
> (2 4 6)
> [44]> (double ' (1 (2 3) ((4) (5 6 (7)))))
> (2 (4 6) ((8) (10 12 (14))))
>
> What I would like to know is if I can write this program in a better
> way ?
--
Thomas A. Russ, USC/Information Sciences Institute