<commit_before>#reader(lib "docreader.ss" "scribble")
@require[(lib "manual.ss" "scribble")]
@require[(lib "eval.ss" "scribble")]
@require[(lib "bnf.ss" "scribble")]
@require["guide-utils.ss"]

@interaction-eval[(require (lib "list.ss"))]
@interaction-eval[(require (lib "for.ss"))]
@define[step @elem{=}]

@title{Lists, Iteration, and Recursion}

Scheme is a dialect of the language Lisp, whose name originally stood
for ``LISt Processor.'' The built-in list datatype remains a prominent
feature of the language.

The @scheme[list] procedure takes any number of values and returns
a list containing the values:

@interaction[(list "red" "green" "blue")
             (list 1 2 3 4 5)]

As you can see, a list result prints in the REPL as a pair of
parentheses wrapped around the printed form of the list
elements. There's an opportunity for confusion here, because
parentheses are used for both expressions, such as @scheme[(list "red"
"green" "blue")], and printed results, such as @schemeresult[("red"
"green" "blue")]. Rememeber that, in the documentation and in
DrScheme, parentheses for results are printed in blue, whereas
parentheses for expressions are brown.

Many predefined procedures operate on lists. Here are a few examples:

@interaction[
(code:line (length (list "a" "b" "c"))        (code:comment #, @t{count the elements}))
(code:line (list-ref (list "a" "b" "c") 0)    (code:comment #, @t{extract by position}))
(list-ref (list "a" "b" "c") 1)
(code:line (append (list "a" "b") (list "c")) (code:comment #, @t{combine lists}))
(code:line (reverse (list "a" "b" "c"))       (code:comment #, @t{reverse order}))
(code:line (member "d" (list "a" "b" "c"))    (code:comment #, @t{check for an element}))
]

@;------------------------------------------------------------------------
@section{Predefined List Loops}

In addition to simple operations like @scheme[append], Scheme includes
procedures that iterate over the elements of a list. These iteration
procedures play much the same role as @tt{for} in Java and other
languages. The body of a Scheme iteration is packaged into a procedure
to be applied to each element, so the @scheme[lambda] form becomes
particularly handy in combination with iteration procedures.

Different list-iteration procedures combine iteration results in
different ways. The @scheme[map] procedure uses the per-element
results to create a new list:

@interaction[
(map sqrt (list 1 4 9 16))
(map (lambda (i)
       (string-append i "!"))
     (list "peanuts" "popcorn" "crackerjack"))
]

The @scheme[andmap] and @scheme[ormap] procedures combine the results
by @scheme[and]ing or @scheme[or]ing:

@interaction[
(andmap string? (list "a" "b" "c"))
(andmap string? (list "a" "b" 6))
(ormap number? (list "a" "b" 6))
]

The @scheme[filter] procedure keeps elements for which the body result
is true, and discards elements for which it is @scheme[#f]:

@interaction[
(filter string? (list "a" "b" 6))
(filter positive? (list 1 -2 6 7 0))
]

The @scheme[map], @scheme[andmap], @scheme[ormap], and @scheme[filter]
procedures can all handle multiple lists, instead of just a single
list. The lists must all have the same length, and the given procedure
must accept one argument for each list:

@interaction[
(map (lambda (s n) (substring s 0 n))
     (list "peanuts" "popcorn" "crackerjack")
     (list 6 3 7))
]

The @scheme[foldl] procedure generalizes some iteration procedures. It
uses the per-element procedure to both process an element and combine
it with the ``current'' value, so the per-element procedure takes an
extra first argument. Also, a starting ``current'' value must be
provided before the lists:

@interaction[
(foldl (lambda (v elem)
         (+ v (* elem elem)))
       0
       '(1 2 3))
]

Despite its generality, @scheme[foldl] is not as popular as the other
procedures. One reason is that @scheme[map], @scheme[ormap],
@scheme[andmap], and @scheme[filter] cover the most common kinds of
list loops.

@;------------------------------------------------------------------------
@section{Iterative Folds and Comprehensions: @scheme[fold-for] and @scheme[list-for]}

Besides iteration procedures like @scheme[foldl], Scheme provides a
syntactic form for iteration that more closely resembles the syntax of
other languages. The @scheme[foldl] example above can be written with
the @scheme[fold-for] syntax as follows:

@interaction[
(fold-for ([sum 0])
          ([elem (list 1 2 3)])
  (+ sum (* elem elem)))
]

Compare to analogous Java code, where @scheme[(list 1 2 3)] is
replaced by a collection @scheme[lst]:

@verbatim[
#<<EOS
  int sum = 0;
  for (Object elem : lst) {
    sum = sum + elem * elem;
  }
  return sum;
EOS
]

The only significant difference is that the updating of @scheme[sum]
and the return of @scheme[sum]'s value are implicit. Those implicit
actions are why the form is called @scheme[fold-for] instead of just
@scheme[for].

Along similar lines, the @scheme[list-for] form iterates through a list
and implicitly accumulates each result into a list:

@interaction[
(list-for ([i (list "peanuts" "popcorn" "crackerjack")])
  (string-append i "!"))
]

The @scheme[list-for] form is a @defterm{list compherension} form, as
in Haskell, Ruby, Python, and other languages. One advantage over
@scheme[map] is that it can iterate over more things than just lists.
For example, @scheme[list-for] can iterate over a range of numbers:

@interaction[
(list-for ([i (range 0 10)])
  i)
]

The @scheme[list-for] form can even iterate over a list and a range of
numbers in parallel:

@interaction[
(list-for ([s (list "a" "b" "c")]
           [n (range 0 3)])
  (if (= n 2)
      "oops!"
       s))
]

Note that the binding syntax of @scheme[fold-for] and
@scheme[list-for] is similar to that of @scheme[let] (as introduced in
@secref["local-binding-intro"]). In the same way that @scheme[let*]
supports nested bindings, @scheme[list-for*] supports nested
iterations:

@interaction[
(list-for* ([s (list "a" "b" "c")]
            [n (list "x" "y" "z")])
  (string-append s n))
]

Unlike the @scheme[list-for], the nested iteration of
@scheme[list-for*] covers patterns with lists not as easily expressed
with @scheme[map]. When procedures like @scheme[map] suffice, however,
Scheme programmers tend to use them, partly because the syntax is
simpler (just a procedure call).
<commit_msg>in-range insteda of range in doc<commit_after>#reader(lib "docreader.ss" "scribble")
@require[(lib "manual.ss" "scribble")]
@require[(lib "eval.ss" "scribble")]
@require[(lib "bnf.ss" "scribble")]
@require["guide-utils.ss"]

@interaction-eval[(require (lib "list.ss"))]
@interaction-eval[(require (lib "for.ss"))]
@define[step @elem{=}]

@title{Lists, Iteration, and Recursion}

Scheme is a dialect of the language Lisp, whose name originally stood
for ``LISt Processor.'' The built-in list datatype remains a prominent
feature of the language.

The @scheme[list] procedure takes any number of values and returns
a list containing the values:

@interaction[(list "red" "green" "blue")
             (list 1 2 3 4 5)]

As you can see, a list result prints in the REPL as a pair of
parentheses wrapped around the printed form of the list
elements. There's an opportunity for confusion here, because
parentheses are used for both expressions, such as @scheme[(list "red"
"green" "blue")], and printed results, such as @schemeresult[("red"
"green" "blue")]. Rememeber that, in the documentation and in
DrScheme, parentheses for results are printed in blue, whereas
parentheses for expressions are brown.

Many predefined procedures operate on lists. Here are a few examples:

@interaction[
(code:line (length (list "a" "b" "c"))        (code:comment #, @t{count the elements}))
(code:line (list-ref (list "a" "b" "c") 0)    (code:comment #, @t{extract by position}))
(list-ref (list "a" "b" "c") 1)
(code:line (append (list "a" "b") (list "c")) (code:comment #, @t{combine lists}))
(code:line (reverse (list "a" "b" "c"))       (code:comment #, @t{reverse order}))
(code:line (member "d" (list "a" "b" "c"))    (code:comment #, @t{check for an element}))
]

@;------------------------------------------------------------------------
@section{Predefined List Loops}

In addition to simple operations like @scheme[append], Scheme includes
procedures that iterate over the elements of a list. These iteration
procedures play much the same role as @tt{for} in Java and other
languages. The body of a Scheme iteration is packaged into a procedure
to be applied to each element, so the @scheme[lambda] form becomes
particularly handy in combination with iteration procedures.

Different list-iteration procedures combine iteration results in
different ways. The @scheme[map] procedure uses the per-element
results to create a new list:

@interaction[
(map sqrt (list 1 4 9 16))
(map (lambda (i)
       (string-append i "!"))
     (list "peanuts" "popcorn" "crackerjack"))
]

The @scheme[andmap] and @scheme[ormap] procedures combine the results
by @scheme[and]ing or @scheme[or]ing:

@interaction[
(andmap string? (list "a" "b" "c"))
(andmap string? (list "a" "b" 6))
(ormap number? (list "a" "b" 6))
]

The @scheme[filter] procedure keeps elements for which the body result
is true, and discards elements for which it is @scheme[#f]:

@interaction[
(filter string? (list "a" "b" 6))
(filter positive? (list 1 -2 6 7 0))
]

The @scheme[map], @scheme[andmap], @scheme[ormap], and @scheme[filter]
procedures can all handle multiple lists, instead of just a single
list. The lists must all have the same length, and the given procedure
must accept one argument for each list:

@interaction[
(map (lambda (s n) (substring s 0 n))
     (list "peanuts" "popcorn" "crackerjack")
     (list 6 3 7))
]

The @scheme[foldl] procedure generalizes some iteration procedures. It
uses the per-element procedure to both process an element and combine
it with the ``current'' value, so the per-element procedure takes an
extra first argument. Also, a starting ``current'' value must be
provided before the lists:

@interaction[
(foldl (lambda (v elem)
         (+ v (* elem elem)))
       0
       '(1 2 3))
]

Despite its generality, @scheme[foldl] is not as popular as the other
procedures. One reason is that @scheme[map], @scheme[ormap],
@scheme[andmap], and @scheme[filter] cover the most common kinds of
list loops.

@;------------------------------------------------------------------------
@section{Iterative Folds and Comprehensions: @scheme[fold-for] and @scheme[list-for]}

Besides iteration procedures like @scheme[foldl], Scheme provides a
syntactic form for iteration that more closely resembles the syntax of
other languages. The @scheme[foldl] example above can be written with
the @scheme[fold-for] syntax as follows:

@interaction[
(fold-for ([sum 0])
          ([elem (list 1 2 3)])
  (+ sum (* elem elem)))
]

Compare to analogous Java code, where @scheme[(list 1 2 3)] is
replaced by a collection @scheme[lst]:

@verbatim[
#<<EOS
  int sum = 0;
  for (Object elem : lst) {
    sum = sum + elem * elem;
  }
  return sum;
EOS
]

The only significant difference is that the updating of @scheme[sum]
and the return of @scheme[sum]'s value are implicit. Those implicit
actions are why the form is called @scheme[fold-for] instead of just
@scheme[for].

Along similar lines, the @scheme[list-for] form iterates through a list
and implicitly accumulates each result into a list:

@interaction[
(list-for ([i (list "peanuts" "popcorn" "crackerjack")])
  (string-append i "!"))
]

The @scheme[list-for] form is a @defterm{list compherension} form, as
in Haskell, Ruby, Python, and other languages. One advantage over
@scheme[map] is that it can iterate over more things than just lists.
For example, @scheme[list-for] can iterate over a range of numbers:

@interaction[
(list-for ([i (in-range 0 10)])
  i)
]

The @scheme[list-for] form can even iterate over a list and a range of
numbers in parallel:

@interaction[
(list-for ([s (list "a" "b" "c")]
           [n (in-range 0 3)])
  (if (= n 2)
      "oops!"
       s))
]

Note that the binding syntax of @scheme[fold-for] and
@scheme[list-for] is similar to that of @scheme[let] (as introduced in
@secref["local-binding-intro"]). In the same way that @scheme[let*]
supports nested bindings, @scheme[list-for*] supports nested
iterations:

@interaction[
(list-for* ([s (list "a" "b" "c")]
            [n (list "x" "y" "z")])
  (string-append s n))
]

Unlike the @scheme[list-for], the nested iteration of
@scheme[list-for*] covers patterns with lists not as easily expressed
with @scheme[map]. When procedures like @scheme[map] suffice, however,
Scheme programmers tend to use them, partly because the syntax is
simpler (just a procedure call).

{'fraction_non_alphanumeric': 0.14346289752650176, 'fraction_numerical': 0.006595995288574794, 'mean_word_length': 4.035982601818901, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6423794', 'n_tokens_mistral': 4053, 'n_tokens_neox': 3848, 'n_words': 1681}