List Comprehensions

[Phil Bewig]

Welcome to Scheme!
> (define (fold-left f b l)
(if (null? l) b (fold-left f (f b (car l)) (cdr l))))
> (define-syntax list-of
(syntax-rules ()
((list-of expr ...)
(reverse (list-of-tail '() expr ...)))))
> (define-syntax list-of-tail
(syntax-rules (in)
((list-of-tail base expr)
(cons expr base))
((list-of-tail base expr (var in generator) rest ...)
(let* ((z (gensym))
(f (lambda (z var) (list-of-tail z expr rest ...))))
(fold-left f base generator)))
((list-of-tail base expr pred? rest ...)
(if pred? (list-of-tail base expr rest ...) base))))
> (list-of (* x x) (x in '(1 2 3 4 5)))
(1 4 9 16 25)
> (define (upto a b) (if (< b a) '() (cons a (upto (+ a 1) b))))
> (upto 1 5)
(1 2 3 4 5)
> (define (squares n) (list-of (* x x) (x in (upto 1 n))))
> (squares 5)
(1 4 9 16 25)
> (define (qsort lt? lst)
(if (null? lst) '()
(append
(qsort lt? (list-of x (x in (cdr lst)) (lt? x (car lst))))
(list (car lst))
(qsort lt? (list-of x (x in (cdr lst)) (not (lt? x (car lst))))))))
> (qsort < '(3 1 4 1 5 9 2 6 5 4))
(1 1 2 3 4 4 5 5 6 9)
> (define (pyth n)
(list-of (list a b c)
(a in (upto 1 n))
(b in (upto a n))
(c in (upto b n))
(= (+ (* a a) (* b b)) (* c c))))
> (pyth 20)
((3 4 5) (5 12 13) (6 8 10) (8 15 17) (9 12 15) (12 16 20))
> (exit)

[Al Petrofsky]

pbe...@swbell.net (Phil Bewig) writes:

> > (define-syntax list-of-tail
> (syntax-rules (in)
> ((list-of-tail base expr)
> (cons expr base))
> ((list-of-tail base expr (var in generator) rest ...)
> (let* ((z (gensym))
> (f (lambda (z var) (list-of-tail z expr rest ...))))
> (fold-left f base generator)))
> ((list-of-tail base expr pred? rest ...)
> (if pred? (list-of-tail base expr rest ...) base))))

I don't think that (z (gensym)) is doing what you think it is doing.
Try leaving it out, and you'll see that it wasn't doing anything.

> > (define (pyth n)
> (list-of (list a b c)
> (a in (upto 1 n))
> (b in (upto a n))
> (c in (upto b n))
> (= (+ (* a a) (* b b)) (* c c))))
> > (pyth 20)
> ((3 4 5) (5 12 13) (6 8 10) (8 15 17) (9 12 15) (12 16 20))

Ain't macros fun? I seem to recall SICP1 used a macro named COLLECT
similar to this, but they didn't show how to implement it.

-al

[Phil Bewig]

Oops! Although this code works, the gensym was a remnant from an
earlier experiment and is of course not necessary. Here is the
corrected macro, which changes in only two lines:

(define (fold-left f b l)
(if (null? l) b (fold-left f (f b (car l)) (cdr l))))
(define-syntax list-of
(syntax-rules ()
((list-of expr ...)
(reverse (list-of-tail '() expr ...)))))
(define-syntax list-of-tail
(syntax-rules (in)
((list-of-tail base expr)
(cons expr base))
((list-of-tail base expr (var in generator) rest ...)

(let* ((f (lambda (z var) (list-of-tail z expr rest ...))))