[plt-scheme] PLT v 4.0 discussion - sequences

From: Mark Engelberg (mark.engelberg at gmail.com)
Date: Thu Jun 5 19:59:15 EDT 2008

Eli wrote:

> This sounds to me like a good idea at a first glance, but of further
> thought I don't see any practical use for it.  IIUC, your suggestion
> is that I can do something like this:
>
>  ;; print n^2 for all even numbers
>  (for ([i (for/sequence ([i (in-naturals)]) (* 2 i))])
>    (printf ">>> ~s\n" (* i i)))
>
> The two big problems with this is that it's more complex to write (the
> nesting is awkward), and that in practical situations I'd almost
> always try to avoid the extra cost.  Plus, in at least cases that I
> imagined (like the above), refactoring the code is straightforward:
>
>  ;; print n^2 for all even numbers
>  (for ([i (in-naturals)])
>    (let ([i (* 2 i)])
>      (printf ">>> ~s\n" (* i i))))

If you're just going to turn around and use the sequence locally, then
yes.  But your argument is like saying that we don't need to be able
to do (define (square x) (* x x)) because you could just as easily use
(lambda (x) (* x x)) every time you want to square something.
Obviously, that's absurd, because the value comes from being able to
name for reuse, pass around, and use the function.  The same goes for
sequences.  If I want to name and pass around a generating sequence of
even numbers, I should be able to easily do that.  And for more
complex sorts of sequences, this becomes even more valuable.

Consider the common problem of needing to "visit" every permutation of
a list in lexicographic order, perhaps looking for a specific
permutation that obeys a certain property.  Creating a list of all the
permutations is wasteful, because I don't really need to use up all
that space and store them all at once.  I really just want to iterate
through the permutations.  Generated sequences are perfect for that,
and I should be able to define it as follows:

(define (in-permutations l)
  (cond
    [(empty? l) (list empty)]
    [else (for*/sequence ((i l) (perm (in-permutations (remove i l))))
(cons i perm))]))

Then, I can use it later:
(for ((perm (in-permutations '(1 2 3)))) (display perm))

So I feel that for/sequence adds real value.

I've been giving some more thought this afternoon to what other
Scheme-like ways could be used to generate sequences.  Yes, a yield
like construct, based on continuations, is one way to generate
sequences.  But perhaps adding the option of an accumulator to
for/sequence would be enough to cover common cases without the
overhead of continuations.

Here's an example of what I've been thinking about:

(define (in-fibonacci)
  (for/sequence
   ((a 1) (b 1))          ;;accumulators
   ((n (in-naturals))) ;;generator (in this example, we don't really
use n, but it makes the sequence infinite)
   a                          ;; value to collect in sequence
   (values b (+ a b))))  ;;update the accumulators

Then, you have an easy way to iterate through all the fibonacci
numbers using the comprehension syntax.

--Mark


Posted on the users mailing list.