[plt-scheme] Sequences are no fun

At Mon, 30 Jun 2008 17:23:46 -0700, "Mark Engelberg" wrote:
> I'm trying to code up some higher-order functions on sequences, and
> I'm finding this to be quite tricky.  A big part of the problem is
> that there is no good way to "peek" at the head of the sequence
> without consuming it, and another big part of the problem is the sheer
> verbosity of converting sequences to generating functions and back.
> 
> As a case in point, here's what I've go so far for drop-while:
> 
> (define (sequence->list seq) (for/list ((i seq)) i))
> 
> (define (identity x) x)
> (define (const-true x) #t)
> 
> (define (drop-one seq)
>   (let-values ([(more? next) (sequence-generate seq)])
>     (next)
>     (make-do-sequence
>      (λ () (values identity (λ (x) (next)) (next) const-true
> const-true (λ (t v) (more?)))))))
> 
> (define (drop-while pred seq)
>   (let-values ([(more? next) (sequence-generate seq)])
>     (cond
>       [(not (more?)) empty]
>       [else (let ([next-value (next)])
>               (cond
>                 [(pred next-value) (drop-while pred (drop-one seq))]
>                 [else (make-do-sequence
>                        (λ () (values identity (λ (x) (next))
> next-value const-true const-true (λ (t v) (more?)))))]))])))
> 
> 
> This almost works, but a sequence formed by drop-while isn't consumed
> properly by sequence->list (try doing a sequence->list twice on
> something generated by drop-while, and you'll see what I mean).

I think the problem is that `seq' is instantiated too early. It should
be converted to a generator when the sequence produced by `drop-while'
is converted to a generator. That is, `sequence-generate' should be
called within the thunk passed to `make-do-sequence'. That's also the
point where you want to determine the first item (and whether there are
any items at all):

I'd write it like this:

 (define (drop-while pred seq)
   (make-do-sequence
    (lambda ()
      (let-values ([(more? next) (sequence-generate seq)])
        (let loop ()
          (if (more?)
              (let ([val (next)])
                (if (pred val)
                    (loop)
                    ;; sequence that starts with val:
                    (values
                     ;; pos->val:
                     (lambda (mode)
                       (case (car mode)
                         [(init) (cdr mode)]
                         [(get) (next)]))
                     ;; next-pos:
                     (lambda (mode) '(get))
                     ;; initial pos; we put `val' here instead
                     ;; of referring to it directly in the `pos->val'
                     ;; proc so that `val' can be GC'ed after it's
                     ;; used up.
                     (cons 'init val)
                     ;; continue at position?
                     (lambda (mode)
                       (case (car mode)
                         [(init) #t]
                         [(get) (more?)]))
                     ;; continue after val?
                     (lambda (val) #t)
                     ;; continue after pos + val?
                     (lambda (mode val) #t))))
              ;; Empty sequence:
              (values void void #f (lambda (pos) #f) void void)))))))


Matthew