Dear all,
I'm in the early stages of teaching myself Lisp/Scheme, using (amongst
other things) the Abelson/Sussman 1986 MIT lectures
(http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/) as
a guide. In Lecture 3a, Abelson suggests that it's possible to
implement map iteratively.
I've been thinking about this, and the best I've come up with so far is:
(define (map proc lst)
; Iterator procedure
(define (iter proc lst result)
(if (null? lst)
result
(iter proc
(cdr lst)
(cons (proc (car lst)) result))))
; Process the list
(iter proc
; Un-reverse the list first
(iter (lambda(x) x) ; Identity procedure
lst
null)
null))
The iter procedure applies proc to each element of lst in turn, and
prepends to result. This reverses the order, so we have to un-reverse
the list before-hand.
This doesn't seem very satisfactory, so does anyone know a better way of
doing this?
--
Oli
Oli Filth <·····@olifilth.co.uk> writes:
> Dear all,
>
> I'm in the early stages of teaching myself Lisp/Scheme, using (amongst
> other things) the Abelson/Sussman 1986 MIT lectures
> (http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/)
> as a guide. In Lecture 3a, Abelson suggests that it's possible to
> implement map iteratively.
>
> I've been thinking about this, and the best I've come up with so far is:
>
> (define (map proc lst)
> ; Iterator procedure
> (define (iter proc lst result)
> (if (null? lst)
> result
> (iter proc
> (cdr lst)
> (cons (proc (car lst)) result))))
>
> ; Process the list
> (iter proc
> ; Un-reverse the list first
> (iter (lambda(x) x) ; Identity procedure
> lst
> null)
> null))
>
> The iter procedure applies proc to each element of lst in turn, and
> prepends to result. This reverses the order, so we have to un-reverse
> the list before-hand.
>
> This doesn't seem very satisfactory, so does anyone know a better way
> of doing this?
>
>
> --
> Oli
I could see a couple of ways similar to yours:
;; using append
(define (iter-map proc lst)
(define (iter proc lst result)
(cond
((null? lst) result)
(else (iter proc
(cdr lst)
(append result (list (proc (car lst))))))))
(iter proc lst '()))
;; using reverse
(define (iter-map proc lst)
(define (iter proc lst result)
(cond
((null? lst) result)
(else (iter proc
(cdr lst)
(cons (proc (car lst)) result)))))
(reverse (iter proc lst '())))
...and one slightly different
;; using neither append nor reverse
(define (iter-map proc lst)
(define (iter-m proc lst result)
(cond
((null? lst) result)
(else (cons (proc (car lst))
(iter-map proc (cdr lst))))))
(iter-m proc lst '()))
··@cub3.homeunix.net wrote:
> ;; using neither append nor reverse
> (define (iter-map proc lst)
> (define (iter-m proc lst result)
> (cond
> ((null? lst) result)
> (else (cons (proc (car lst))
> (iter-map proc (cdr lst))))))
> (iter-m proc lst '()))
Correct me if I'm wrong, but the call to iter-map
is not in tail position here, so this version
is not iterative.
-- JK
Joe Knapka <·········@kneuro.net> writes:
> ··@cub3.homeunix.net wrote:
>
>> ;; using neither append nor reverse
>> (define (iter-map proc lst)
>> (define (iter-m proc lst result)
>> (cond
>> ((null? lst) result)
>> (else (cons (proc (car lst))
>> (iter-map proc (cdr lst))))))
>> (iter-m proc lst '()))
>
> Correct me if I'm wrong, but the call to iter-map
> is not in tail position here, so this version
> is not iterative.
>
> -- JK
Yes, this is not tail-recursive.
Is this more acceptable "iterative" solution?
(define (iter-map proc lst)
(let loop ((lst lst) (v (make-vector (length lst))) (i 0))
(cond
((null? lst) (vector->list v))
(else (vector-set! v i (proc (car lst)))
(loop (cdr lst) v (+ 1 i))))))
Oli Filth <·····@olifilth.co.uk> writes:
> Dear all,
>
> I'm in the early stages of teaching myself Lisp/Scheme, using (amongst
> other things) the Abelson/Sussman 1986 MIT lectures
> (http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/)
> as a guide. In Lecture 3a, Abelson suggests that it's possible to
> implement map iteratively.
>
> I've been thinking about this, and the best I've come up with so far is:
>
> (define (map proc lst)
> ; Iterator procedure
> (define (iter proc lst result)
> (if (null? lst)
> result
> (iter proc
> (cdr lst)
> (cons (proc (car lst)) result))))
>
> ; Process the list
> (iter proc
> ; Un-reverse the list first
> (iter (lambda(x) x) ; Identity procedure
> lst
> null)
> null))
>
> The iter procedure applies proc to each element of lst in turn, and
> prepends to result. This reverses the order, so we have to un-reverse
> the list before-hand.
>
> This doesn't seem very satisfactory, so does anyone know a better way
> of doing this?
;; 1 ;;
(define (map proc list)
(let ((head (cons '() '())))
(let loop ((list list)
(tail head))
(if (null? list)
(cdr head)
(begin
(set-cdr! tail (cons (proc (car list)) '()))
(loop (cdr list) (cdr tail)))))))
But nowadays, I fail to see how the following is not iterative ;-) :
;; 2 ;;
(define (map proc list)
(if (null? list)
list
(cons (proc (car list)) (map proc (cdr list)))))
Reversing the list can be done with the standard procedure reverse,
you could have written in the body of your function:
(reverse (iter proc lst '()))
Or you could implement a reverse! which does it in-place, since we're
working on a newly allocated list, which we can modify:
(define (reverse! list)
(define (internal current result)
(if (null? current)
result
(internal (cdr current)
(begin (set-cdr! current result)
current))))
(internal list '()))
;; 3 ;;
(define (map proc list)
(define (internal current result)
(if (null? current)
(reverse! result)
(internal (cdr current) (cons (proc (car current)) result))))
(internal list '()))
Note that performance wise, both this version 3 of map using reverse!
and the above version 2 using set-cdr! on the tail are equivalent
(depending on the processor, version 3 might be slightly better).
On a Lambda-Calculus processor, the version 2 might be the most efficient.
On a Von Neumann processor, the version 1 or 3 might be the most efficient.
Version 3 has the advantage of abstracting the reverse! operation,
which can be used in an number of map-like procedures.
--
__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:
> Oli Filth <·····@olifilth.co.uk> writes:
>
> > Dear all,
> >
> > I'm in the early stages of teaching myself Lisp/Scheme, using (amongst
> > other things) the Abelson/Sussman 1986 MIT lectures
> > (http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/)
> > as a guide. In Lecture 3a, Abelson suggests that it's possible to
> > implement map iteratively.
> >
> > I've been thinking about this, and the best I've come up with so far is:
> >
> > (define (map proc lst)
> > ; Iterator procedure
> > (define (iter proc lst result)
> > (if (null? lst)
> > result
> > (iter proc
> > (cdr lst)
> > (cons (proc (car lst)) result))))
> >
> > ; Process the list
> > (iter proc
> > ; Un-reverse the list first
> > (iter (lambda(x) x) ; Identity procedure
> > lst
> > null)
> > null))
> >
> > The iter procedure applies proc to each element of lst in turn, and
> > prepends to result. This reverses the order, so we have to un-reverse
> > the list before-hand.
> >
> > This doesn't seem very satisfactory, so does anyone know a better way
> > of doing this?
>
> ;; 1 ;;
> (define (map proc list)
> (let ((head (cons '() '())))
> (let loop ((list list)
> (tail head))
> (if (null? list)
> (cdr head)
> (begin
> (set-cdr! tail (cons (proc (car list)) '()))
> (loop (cdr list) (cdr tail)))))))
In newLisp:
(define (imap func lst , accum)
(set 'accum '())
(dolist (e lst) (push (func e) accum))
(reverse accum))
--
Use mnemonic names. The names of all functions ... and variables
should have meaning to you and to others. [CAR and CDR are good
examples of what not to use as names.] --- Learning LISP
"William James" <·········@yahoo.com> writes:
> Pascal Bourguignon wrote:
>> Oli Filth <·····@olifilth.co.uk> writes:
>>
>> > Dear all,
>> >
>> > I'm in the early stages of teaching myself Lisp/Scheme, using (amongst
>> > other things) the Abelson/Sussman 1986 MIT lectures
>> > (http://swiss.csail.mit.edu/classes/6.001/abelson-sussman-lectures/)
>> > as a guide. In Lecture 3a, Abelson suggests that it's possible to
>> > implement map iteratively.
> [...]
> In newLisp:
>
> (define (imap func lst , accum)
> (set 'accum '())
> (dolist (e lst) (push (func e) accum))
> (reverse accum))
Yes, as soon as you provide the exercises and solution of SICP in newLISP.
--
__Pascal Bourguignon__ http://www.informatimago.com/
"Logiciels libres : nourris au code source sans farine animale."