Home > Archive > Scheme > April 2006 > how to use cons
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
|
|
| mike13610@gmail.com 2006-04-25, 7:15 pm |
| How do I take the following and write it with cons instead of append?
(define (hanoi n)
(if (= n 1) (list 1)
(append (hanoi (- n 1))
(list n)
(hanoi (- n 1)))))
| |
| Pascal Bourguignon 2006-04-25, 7:15 pm |
| mike13610@gmail.com writes:
> How do I take the following and write it with cons instead of append?
>
> (define (hanoi n)
> (if (= n 1) (list 1)
> (append (hanoi (- n 1))
> (list n)
> (hanoi (- n 1)))))
>
(define (function-using-cons-instead-of-append . args)
(cond ((null? args) '())
((null? (car args))
(apply function-using-cons-instead-of-append (cdr args)))
(else (cons (car (car args))
(apply function-using-cons-instead-of-append
(cdr (car args))
(cdr args))))))
(define (hanoi n)
(if (= n 1) (list 1)
(function-using-cons-instead-of-append
(hanoi (- n 1))
(list n)
(hanoi (- n 1)))))
--
__Pascal Bourguignon__ http://www.informatimago.com/
READ THIS BEFORE OPENING PACKAGE: According to certain suggested
versions of the Grand Unified Theory, the primary particles
constituting this product may decay to nothingness within the next
four hundred million years.
| |
| Abdulaziz Ghuloum 2006-04-25, 7:15 pm |
| Pascal Bourguignon wrote:
> mike13610@gmail.com writes:
>
> (define (function-using-cons-instead-of-append . args)
> (cond ((null? args) '())
> ((null? (car args))
> (apply function-using-cons-instead-of-append (cdr args)))
> (else (cons (car (car args))
> (apply function-using-cons-instead-of-append
> (cdr (car args))
> (cdr args))))))
Wow! This is like someone asking ``how do I nail a frame without using
a hammer'' and you reply with ``hold the nail next to the wall and run
through it with your car at 60 miles per hour''.
Now back to not using append, apply, or varargs: Use an accumilator to
hold the rest of the list. I won't say how to do hannoi, but here is
how to do flatten:
(define (flatten x) ; using append
(cond
((null? x) '())
((pair? x)
(append (flatten (car x)) (flatten (cdr x))))
(else (list x))))
(flatten '((((x y) z) 1 2) (3 4) 5))
=>
(x y z 1 2 3 4 5)
Now with an accumilator:
(define (flatten-helper x ac) ; using cons only
(cond
((null? x) ac)
((pair? x)
(flatten-helper (car x) (flatten-helper (cdr x) ac)))
(else (cons x ac))))
(define (flatten x)
(flatten-helper x '()))
(flatten '((((x y) z) 1 2) (3 4) 5))
=>
(x y z 1 2 3 4 5)
Hanoi can easily be converted to this style.
Aziz,,,
| |
| Pascal Bourguignon 2006-04-25, 7:15 pm |
| Abdulaziz Ghuloum <aghuloum@c-s-remove-dashes.indiana.edu> writes:
> Pascal Bourguignon wrote:
>
> Wow! This is like someone asking ``how do I nail a frame without using
> a hammer'' and you reply with ``hold the nail next to the wall and run
> through it with your car at 60 miles per hour''.
Not exactly. It's rather: "go find a hammer, name it 'not a hammer',
and then nail your frame with it."
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we. -- Georges W. Bush
| |
| mike13610@gmail.com 2006-04-25, 7:15 pm |
|
> Hanoi can easily be converted to this style.
>
I've tried for several minutes to understand you post and cannot,
because I'm trying to figure out how now to use append, and yet in the
first procedure you use append. I've no idea what the general concept
is, nor how to apply it to my specific problem...thanks for helping,
I'm not getting it though.
| |
| Abdulaziz Ghuloum 2006-04-25, 7:15 pm |
| mike13610@gmail.com wrote:
>
>
> I've tried for several minutes to understand you post and cannot,
> because I'm trying to figure out how now to use append, and yet in the
> first procedure you use append. I've no idea what the general concept
> is, nor how to apply it to my specific problem...thanks for helping,
> I'm not getting it though.
Yes, the first one uses append just like the procedure you posted uses
append. The second one accomplishes the same task but does not use
append. Try to understand how the second one works (or does it?), then
try to figure out how I transformed the first program (the one that uses
append) to the second. Once you know how that was done, you can apply
the same technique to your problem.
Aziz,,,
| |
| mike13610@gmail.com 2006-04-25, 7:15 pm |
|
> Yes, the first one uses append just like the procedure you posted uses
> append. The second one accomplishes the same task but does not use
> append. Try to understand how the second one works (or does it?), then
> try to figure out how I transformed the first program (the one that uses
> append) to the second. Once you know how that was done, you can apply
> the same technique to your problem.
>
What do x and ac stand for? I can't figure out what those arguments are
supposed to be.
| |
| Max Hailperin 2006-04-25, 7:15 pm |
| mike13610@gmail.com writes:
>
> What do x and ac stand for? I can't figure out what those arguments are
> supposed to be.
Aziz's x is a list, some of the elements of which may themselves be
lists, and so forth to any arbitrary nesting depth. The
flatten-helper might be renamed "flatten-onto" -- it flattens the list
x onto the front of ac. The name "ac" presumably is short for
"accumulator"; if you think of flattening x onto the front of
something, I'm not sure what the "something" should be called -- I
usually call it a tail, so I would rename flatten-helper to
flatten-onto and rename ac to tail. This isn't to imply there is
anything wrong with using a different mnemonic, if it works for you.
You can find two more examples of this style in the the text of
Concrete Abstracions. Chapter 7 (on lists) shows how to rewrite
reverse to use reverse-onto so as to avoid append. Chapter 8 (on
trees) shows how to rewrite preorder to use preorder-onto so as to
avoid append. This book is available for free on the web; just google
"Concrete Abstractions". -max
| |
| mike13610@gmail.com 2006-04-25, 7:15 pm |
|
> You can find two more examples of this style in the the text of
> Concrete Abstracions. Chapter 7 (on lists) shows how to rewrite
> reverse to use reverse-onto so as to avoid append. Chapter 8 (on
> trees) shows how to rewrite preorder to use preorder-onto so as to
> avoid append. This book is available for free on the web; just google
> "Concrete Abstractions". -max
Wow. thanks for the pointer. This is exactly what I was looking for.
:-).
|
|
|
|
|