#lang scribble/doc
@(require "mz.rkt")

@title[#:tag "for"]{Iterations and Comprehensions: @racket[for], @racket[for/list], ...}

@guideintro["for"]{iterations and comprehensions}

The @racket[for] iteration forms are based on SRFI-42
@cite["SRFI-42"].


@section{Iteration and Comprehension Forms}

@defform/subs[(for (for-clause ...) body ...+)
              ([for-clause [id seq-expr]
                           [(id ...) seq-expr]
                           (code:line #:when guard-expr)
                           (code:line #:unless guard-expr)])
              #:contracts ([seq-expr sequence?])]{

Iteratively evaluates @racket[body]. The @racket[for-clause]s
introduce bindings whose scope includes @racket[body] and that
determine the number of times that @racket[body] is evaluated.

In the simple case, each @racket[for-clause] has one of its first two
forms, where @racket[[id seq-expr]] is a shorthand for @racket[[(id)
seq-expr]].  In this simple case, the @racket[seq-expr]s are evaluated
left-to-right, and each must produce a sequence value (see
@secref["sequences"]).

The @racket[for] form iterates by drawing an element from each
sequence; if any sequence is empty, then the iteration stops, and
@|void-const| is the result of the @racket[for] expression. Otherwise
a location is created for each @racket[id] to hold the values of each
element; the sequence produced by a @racket[seq-expr] must return as
many values for each iteration as corresponding @racket[id]s.

The @racket[id]s are then bound in the @racket[body], which is
evaluated, and whose results are ignored. Iteration continues with the
next element in each sequence and with fresh locations for each
@racket[id].

A @racket[for] form with zero @racket[for-clause]s is equivalent to a
single @racket[for-clause] that binds an unreferenced @racket[id] to
a sequence containing a single element. All of the @racket[id]s must
be distinct according to @racket[bound-identifier=?].

If any @racket[for-clause] has the form @racket[#:when guard-expr],
then only the preceding clauses (containing no @racket[#:when] or @racket[#:unless])
determine iteration as above, and the @racket[body] is effectively
wrapped as

@racketblock[
(when guard-expr
  (for (for-clause ...) body ...+))
]

using the remaining @racket[for-clauses]. A @racket[for-clause] of
the form @racket[#:unless guard-expr] corresponds to the same transformation
with @racket[unless] in place of @racket[when].

@examples[
(for ([i '(1 2 3)]
      [j "abc"]
      #:when (odd? i)
      [k #2(#t #f)])
  (display (list i j k)))
(for ([(i j) #hash(("a" . 1) ("b" . 20))])
  (display (list i j)))
(for ()
  (display "here"))
(for ([i '()])
  (error "doesn't get here"))
]}

@defform[(for/list (for-clause ...) body ...+)]{ Iterates like
@racket[for], but that the last expression in the @racket[body]s must
produce a single value, and the result of the @racket[for/list]
expression is a list of the results in order.
When evaluation of a @racket[body] is skipped due to a @racket[#:when]
or @racket[#:unless] clause, the result list includes no corresponding
element.

@examples[
(for/list ([i '(1 2 3)]
           [j "abc"]
           #:when (odd? i)
           [k #2(#t #f)])
  (list i j k))
(for/list () 'any)
(for/list ([i '()])
  (error "doesn't get here"))
]}

@defform*[((for/vector (for-clause ...) body ...+)
           (for/vector #:length length-expr (for-clause ...) body ...+))]{

Iterates like @racket[for/list], but the result are accumulated into
a vector instead of a list.  If the optional @racket[#:length]
form is used, then @racket[length-expr] must evaluate to an
@racket[exact-nonnegative-integer?], and the result vector is
constructed with this length.  In this case, the iteration can be
performed more efficiently, and terminates when the vector is full or
the requested number of iterations have been performed, whichever
comes first.  If the provided @racket[length-expr] evaluates to a
length longer than the number of iterations then the remaining slots
of the vector are intialized to the default argument of
@racket[make-vector].}

@deftogether[(
@defform[(for/hash (for-clause ...) body ...+)]
@defform[(for/hasheq (for-clause ...) body ...+)]
@defform[(for/hasheqv (for-clause ...) body ...+)]
)]{

Like @racket[for/list], but the result is an immutable @tech{hash
table}; @racket[for/hash] creates a table using @racket[equal?] to
distinguish keys, @racket[for/hasheq] produces a table using
@racket[eq?], and @racket[for/hasheqv] produces a table using
@racket[eqv?]. The last expression in the @racket[body]s must return
two values: a key and a value to extend the hash table accumulated by
the iteration.

@examples[
(for/hash ([i '(1 2 3)])
  (values i (number->string i)))
]}


@defform[(for/and (for-clause ...) body ...+)]{ Iterates like
@racket[for], but when last expression of @racket[body] produces
@racket[#f], then iteration terminates, and the result of the
@racket[for/and] expression is @racket[#f]. If the @racket[body]
is never evaluated, then the result of the @racket[for/and]
expression is @racket[#t]. Otherwise, the result is the (single)
result from the last evaluation of @racket[body].

@examples[
(for/and ([i '(1 2 3 "x")])
  (i . < . 3))
(for/and ([i '(1 2 3 4)])
  i)
(for/and ([i '()])
  (error "doesn't get here"))
]}

@defform[(for/or (for-clause ...) body ...+)]{ Iterates like
@racket[for], but when last expression of @racket[body] produces
a value other than @racket[#f], then iteration terminates, and
the result of the @racket[for/or] expression is the same
(single) value. If the @racket[body] is never evaluated, then the
result of the @racket[for/or] expression is
@racket[#f]. Otherwise, the result is @racket[#f].

@examples[
(for/or ([i '(1 2 3 "x")])
  (i . < . 3))
(for/or ([i '(1 2 3 4)])
  i)
(for/or ([i '()])
  (error "doesn't get here"))
]}

@deftogether[(
@defform[(for/sum (for-clause ...) body ...+)]
)]{

Iterates like @racket[for], but each result of the last @racket[body]
is accumulated into a result with @racket[+].

@examples[
(for/sum ([i '(1 2 3 4)]) i)
]}


@deftogether[(
@defform[(for/product (for-clause ...) body ...+)]
)]{

Iterates like @racket[for], but each result of the last @racket[body]
is accumulated into a result with @racket[*].

@examples[
(for/product ([i '(1 2 3 4)]) i)
]}


@defform[(for/lists (id ...) (for-clause ...) body ...+)]{

Similar to @racket[for/list], but the last @racket[body] expression
should produce as many values as given @racket[id]s, and the result is
as many lists as supplied @racket[id]s. The @racket[id]s are bound to
the lists accumulated so far in the @racket[for-clause]s and
@racket[body]s.}


@defform[(for/first (for-clause ...) body ...+)]{ Iterates like
@racket[for], but after @racket[body] is evaluated the first
time, then the iteration terminates, and the @racket[for/first]
result is the (single) result of @racket[body]. If the
@racket[body] is never evaluated, then the result of the
@racket[for/first] expression is @racket[#f].

@examples[
(for/first ([i '(1 2 3 "x")]
            #:when (even? i))
   (number->string i))
(for/first ([i '()])
  (error "doesn't get here"))
]}

@defform[(for/last (for-clause ...) body ...+)]{ Iterates like
@racket[for], but the @racket[for/last] result is the (single)
result of the last evaluation of @racket[body]. If the
@racket[body] is never evaluated, then the result of the
@racket[for/last] expression is @racket[#f].

@examples[
(for/last ([i '(1 2 3 4 5)]
            #:when (even? i))
   (number->string i))
(for/last ([i '()])
  (error "doesn't get here"))
]}

@defform[(for/fold ([accum-id init-expr] ...) (for-clause ...) . body)]{

Iterates like @racket[for]. Before iteration starts, the
@racket[init-expr]s are evaluated to produce initial accumulator
values. At the start of each iteration, a location is generated
for each @racket[accum-id], and the corresponding current accumulator
value is placed into the location. The last expression in
@racket[body] must produce as many values as @racket[accum-id]s, and
those values become the current accumulator values. When iteration
terminates, the results of the @racket[fold/for] expression are the
accumulator values.

@examples[
(for/fold ([sum 0]
           [rev-roots null])
          ([i '(1 2 3 4)])
  (values (+ sum i) (cons (sqrt i) rev-roots)))
]}

@defform[(for* (for-clause ...) body ...+)]{
Like @racket[for], but with an implicit @racket[#:when #t] between
each pair of @racket[for-clauses], so that all sequence iterations are
nested.

@examples[
(for* ([i '(1 2)]
       [j "ab"])
  (display (list i j)))
]}

@deftogether[(
@defform[(for*/list (for-clause ...) body ...+)]
@defform[(for*/lists (id ...) (for-clause ...) body ...+)]
@defform*[((for*/vector (for-clause ...) body ...+)
           (for*/vector #:length length-expr (for-clause ...) body ...+))]
@defform[(for*/hash (for-clause ...) body ...+)]
@defform[(for*/hasheq (for-clause ...) body ...+)]
@defform[(for*/hasheqv (for-clause ...) body ...+)]
@defform[(for*/and (for-clause ...) body ...+)]
@defform[(for*/or (for-clause ...) body ...+)]
@defform[(for*/sum (for-clause ...) body ...+)]
@defform[(for*/product (for-clause ...) body ...+)]
@defform[(for*/first (for-clause ...) body ...+)]
@defform[(for*/last (for-clause ...) body ...+)]
@defform[(for*/fold ([accum-id init-expr] ...) (for-clause ...) body ...+)]
)]{

Like @racket[for/list], etc., but with the implicit nesting of
@racket[for*].

@examples[
(for*/list ([i '(1 2)]
            [j "ab"])
  (list i j))
]}

@;------------------------------------------------------------------------
@section{Deriving New Iteration Forms}

@defform[(for/fold/derived orig-datum
           ([accum-id init-expr] ...) (for-clause ...) body ...+)]{
Like @racket[for/fold], but the extra @racket[orig-datum] is used as the source for all syntax errors.

@mz-examples[
(define-syntax (for/digits stx)
  (syntax-case stx ()
    [(_ clauses . defs+exprs)
     (with-syntax ([original stx])
       #'(let-values
           ([(n k)
             (for/fold/derived original ([n 0] [k 1]) clauses
               (define d (let () . defs+exprs))
               (values (+ n (* d k)) (* k 10)))])
           n))]))

(for/digits
    [a (in-list '(1 2 3))]
    [b (in-list '(4 5 6))]
  (+ a b))

(for/digits
    ([a (in-list '(1 2 3))]
     [b (in-list '(2 4 6))])
  (+ a b))
]
}

@defform[(for*/fold/derived orig-datum
           ([accum-id init-expr] ...) (for-clause ...) body ...+)]{
Like @racket[for*/fold], but the extra @racket[orig-datum] is used as the source for all syntax errors.

@mz-examples[
(define-syntax (for*/digits stx)
  (syntax-case stx ()
    [(_ clauses . defs+exprs)
     (with-syntax ([original stx])
       #'(let-values
           ([(n k)
             (for*/fold/derived original ([n 0] [k 1]) clauses
               (define d (let () . defs+exprs))
               (values (+ n (* d k)) (* k 10)))])
           n))]))

(for*/digits
    [ds (in-list '((8 3) (1 1)))]
    [d (in-list ds)]
  d)

(for*/digits
    ([ds (in-list '((8 3) (1 1)))]
     [d (in-list ds)])
  d)
]

}

@defform[(define-sequence-syntax id
           expr-transform-expr
           clause-transform-expr)
         #:contracts
         ([expr-transform-expr (or/c (-> identifier?)
                                     (syntax? . -> . syntax?))]
          [clause-transform-expr (syntax? . -> . syntax?)])]{

Defines @racket[id] as syntax. An @racket[(id . _rest)] form is
treated specially when used to generate a sequence in a
@racket[_clause] of @racket[for] (or one of its variants). In that
case, the procedure result of @racket[clause-transform-expr] is called
to transform the clause.

When @racket[id] is used in any other expression position, the result
of @racket[expr-transform-expr] is used. If it is a procedure of zero
arguments, then the result must be an identifier @racket[_other-id],
and any use of @racket[id] is converted to a use of
@racket[_other-id]. Otherwise,@racket[expr-transform-expr] must
produce a procedure (of one argument) that is used as a macro
transformer.

When the @racket[clause-transform-expr] transformer is used, it is
given a @racket[_clause] as an argument, where the clause's form is
normalized so that the left-hand side is a parenthesized sequence of
identifiers. The right-hand side is of the form @racket[(id . _rest)].
The result can be either @racket[#f], to indicate that the forms
should not be treated specially (perhaps because the number of bound
identifiers is inconsistent with the @racket[(id . _rest)] form), or a
new @racket[_clause] to replace the given one. The new clause might
use @racket[:do-in]. To protect identifiers in the result of 
@racket[clause-transform-expr], use @racket[for-clause-syntax-protect]
instead of @racket[syntax-protect].

@mz-examples[
(define-sequence-syntax in-digits
  (lambda () #'in-digits/proc)
  (lambda (stx)
    (syntax-case stx ()
      [[(d) (_ nat)]
       #'[(d)
          (:do-in
            ([(n) nat])
            (unless (exact-nonnegative-integer? n)
              (raise-type-error 'in-digits "exact non-negative integer" n))
            ([i n])
            (not (zero? i))
            ([(j d) (quotient/remainder i 10)])
            #true
            #true
            [j])]])))

(define (in-digits/proc n [b 10])
  (for/list ([d (in-digits n)]) d))

(for/list ([d (in-digits 1138)]) d)

(map in-digits (list 137 216))
]}

@defform[(:do-in ([(outer-id ...) outer-expr] ...)
                 outer-check
                 ([loop-id loop-expr] ...)
                 pos-guard
                 ([(inner-id ...) inner-expr] ...)
                 pre-guard
                 post-guard
                 (loop-arg ...))]{

A form that can only be used as a @racket[_seq-expr] in a
@racket[_clause] of @racket[for] (or one of its variants).

Within a @racket[for], the pieces of the @racket[:do-in] form are
spliced into the iteration essentially as follows:

@racketblock[
(let-values ([(outer-id ...) outer-expr] ...)
  outer-check
  (let loop ([loop-id loop-expr] ...)
    (if pos-guard
        (let-values ([(inner-id ...) inner-expr] ...)
          (if pre-guard
              (let _body-bindings
                   (if post-guard
                       (loop loop-arg ...)
                       _done-expr))
              _done-expr))
         _done-expr)))
]

where @racket[_body-bindings] and @racket[_done-expr] are from the
context of the @racket[:do-in] use. The identifiers bound by the
@racket[for] clause are typically part of the @racket[([(inner-id ...)
inner-expr] ...)] section.

The actual @racket[loop] binding and call has additional loop
arguments to support iterations in parallel with the @racket[:do-in]
form, and the other pieces are similarly accompanied by pieces from
parallel iterations.

For an example of @racket[:do-in], see @racket[define-sequence-syntax].}

@defproc[(for-clause-syntax-protect [stx syntax?]) syntax?]{

Provided @racket[for-syntax]: Like @racket[syntax-protect], but allows
the @racket[for] expander to @tech{disarm} the result syntax object,
and arms the pieces of a clause instead of the entire syntax object.

Use this function to protect the result of a
@racket[_clause-transform-expr] that is bound by
@racket[define-sequence-syntax].}


@section{Do Loops}

@defform/subs[(do ([id init-expr step-expr-maybe] ...)
                  (stop?-expr finish-expr ...)
                expr ...)
              ([step-expr-maybe code:blank
                                step-expr])]{

Iteratively evaluates the @racket[expr]s for as long as
@racket[stop?-expr] returns @racket[#f].

To initialize the loop, the @racket[init-expr]s are evaluated in order
and bound to the corresponding @racket[id]s. The @racket[id]s are
bound in all expressions within the form other than the
@racket[init-expr]s.

After the @racket[id]s have been bound, the @racket[stop?-expr] is
evaluated. If it produces @racket[#f], each @racket[expr] is evaluated
for its side-effect. The @racket[id]s are then effectively updated
with the values of the @racket[step-expr]s, where the default
@racket[step-expr] for @racket[id] is just @racket[id]; more
precisely, iteration continues with fresh locations for the
@racket[id]s that are initialized with the values of the corresponding
@racket[step-expr]s.

When @racket[stop?-expr] produces a true value, then the
@racket[finish-expr]s are evaluated in order, and the last one is
evaluated in tail position to produce the overall value for the
@racket[do] form. If no @racket[finish-expr] is provided, the value of
the @racket[do] form is @|void-const|.}
