2.5 Abstraction: "abstraction.rkt"

Matthias Felleisen

package: htdp-lib

The abstract.rkt teachpack provides some additional abstraction facilities: comprehensions and loops, matching, and algebraic data types. Most of these are restricted versions of full-featured constructs in other members of the Racket family so that students of HtDP/2e don’t stumble across syntactic oddities.

HtDP/2e introduces loops and matching in an intermezzo, with the sole purpose of acknowledging the existence of powerful linguistic mechanisms.

Algebraic data types are provided for those who think teaching the features of functional programming is more important than teaching universally applicable ideas of program design.

Added in version 1.1 of package htdp-lib.

2.5.1 Loops and Comprehensions

syntax
(for/list (comprehension-clause comprehension-clause ...) body-expr)

comprehension-clause = (name clause-expr)

evaluates body-expr for the parallel sequences of values determined by the comprehension-clauses.

Each comprehension-clause binds its name in body-expr.

The for/list expression evaluates all clause-expr to generate sequences of values. If a clause-expr evaluates to a

list, its items make up the sequence values;
natural number n, the sequence of values consists of the numbers 0, 1, ..., (- n 1);
string, its one-character strings are the sequence items.

For sequences generated by in-range and in-naturals, see below.

Finally, for/list evaluates body-expr with name ... successively bound to the values of the sequences determined by clause-expr ...

> (for/list ((i 10))
    i)
'(0 1 2 3 4 5 6 7 8 9)
> (for/list ((i 2) (j '(a b)))
    (list i j))
'((0 a) (1 b))
> (for/list ((c "abc"))
    c)
'("a" "b" "c")

The evaluation stops when the shortest sequence is exhausted.

> (for/list ((i 2) (j '(a b c d e)))
(list i j))
'((0 a) (1 b))

syntax
(for*/list (comprehension-clause comprehension-clause ...) body-expr)

evaluates body-expr for the nested sequences of values determined by the comprehension-clauses.

Each comprehension-clause binds its name in the expressions of the following comprehension-clauses as well as body-expr.

> (for*/list ((i 2) (j '(a b)))
(list i j))
'((0 a) (0 b) (1 a) (1 b))
> (for*/list ((i 5) (j i))
(list i j))
'((1 0) (2 0) (2 1) (3 0) (3 1) (3 2) (4 0) (4 1) (4 2) (4 3))

With nesting, the evaluation does not stop when the shortest sequence is exhausted because comprehension-clauses are evaluated in order:

> (for*/list ((i 2) (j '(a b c d e)))
(list i j))
'((0 a) (0 b) (0 c) (0 d) (0 e) (1 a) (1 b) (1 c) (1 d) (1 e))

syntax
(for/or (comprehension-clause comprehension-clause ...) body-expr)

iterates over the sequences generated by the comprehension-clauses like for/list. It produces the first non-#false value, if any, and #false otherwise.

> (for/or ([c "abcd"])
(if (string=? "x" c) c #false))
#f
> (for/or ([c (list #false 1 #false 2)])
c)
1

syntax
(for*/or (comprehension-clause comprehension-clause ...) body-expr)

iterates over the sequences generated by the comprehension-clauses like for*/list. It produces the first non-#false value, if any, and #false otherwise.

> (for*/or ([i 2][j i])
(if (> j i) (list i j) #false))
#f

syntax
(for/and (comprehension-clause comprehension-clause ...) body-expr)

iterates over the sequences generated by the comprehension-clauses like for/list. If any evaluation of body-expr produces #false, the loop stops and returns #false, too; otherwise, the loop produces the result of the last evaluation of body-expr.

> (for/and ([c '(1 2 3)])
(if (> c 4) c #false))
#f
> (for/and ([c '(1 2 3)])
(if (< c 4) c #false))
3

syntax
(for*/and (comprehension-clause comprehension-clause ...) body-expr)

iterates over the sequences generated by the comprehension-clauses like for*/list. If any evaluation of body-expr produces #false, the loop stops and returns #false, too; otherwise, the loop produces the result of the last evaluation of body-expr.

> (for*/and ([i 2][j i])
(if (< j i) (list i j) #false))
'(1 0)

syntax
(for/sum (comprehension-clause comprehension-clause ...) body-expr)

iterates over the sequences generated by the comprehension-clauses like for/list. It adds up the numbers that body-expr evaluates to.

> (for/sum ([i 2][j 8])
(max i j))
1

syntax
(for*/sum (comprehension-clause comprehension-clause ...) body-expr)

iterates over the sequences generated by the comprehension-clauses like for*/list. It adds up the numbers that body-expr evaluates to.

> (for*/sum ([i 2][j i])
(min i j))
0

syntax
(for/product (comprehension-clause comprehension-clause ...) body-expr)

iterates over the sequences generated by the comprehension-clauses like for/list. It multiplies the numbers that body-expr evaluates to.

> (for/product ([i 2][j 3])
(+ i j 1))
3

syntax
(for*/product (comprehension-clause comprehension-clause ...) body-expr)

iterates over the sequences generated by the comprehension-clauses like for*/list. It multiplies the numbers that body-expr evaluates to.

> (for*/product ([i 2][j i])
(+ i j 1))
2

syntax
(for/string (comprehension-clause comprehension-clause ...) body-expr)

iterates over the sequences generated by the comprehension-clauses like for/list. It collects the one-character strings that body-expr evaluates to with implode.

> (for/string ([i "abc"])
(int->string (+ (string->int i) 1)))
"bcd"

syntax
(for*/string (comprehension-clause comprehension-clause ...) body-expr)

iterates over the sequences generated by the comprehension-clauses like for/list. It collects the one-character strings that body-expr evaluates to with implode.

> (for*/string ([i "ab"][j (- (string->int i) 90)])
(int->string (+ (string->int i) j)))
"abcdefgbcdefghi"

procedure
(in-range start end step) → sequence?
  start : natural-number/c
  end : natural-number/c
  step : natural-number/c
(in-range end) → sequence?
  end : natural-number/c

generates a finite sequence of natural numbers.

If start, end, and step are provided, the sequence consists of start, (+ start step), (+ start step step), ... until the sum is greater than or equal to end.

> (for/list ([i (in-range 1 10 3)]) i)
'(1 4 7)

If only end is provided, start defaults to 0 and step to 1:

> (for/list ([i (in-range 3)])
i)
'(0 1 2)
> (for/list ([i (in-range 0 3 1)])
i)
'(0 1 2)

procedure
(in-naturals start) → sequence?
start : natural-number/c

generates an infinite sequence of natural numbers, starting with start.

> (define (enumerate a-list)
(for/list ([x a-list][i (in-naturals 1)])
(list i x)))
> (enumerate '(Maxwell Einstein Planck Heisenberg Feynman))
'((1 Maxwell) (2 Einstein) (3 Planck) (4 Heisenberg) (5 Feynman))
> (enumerate '("Pinot noir" "Pinot gris" "Pinot blanc"))
'((1 "Pinot noir") (2 "Pinot gris") (3 "Pinot blanc"))

2.5.2 Pattern Matching

syntax
(match case-expr (pattern body-expr) ...)

pattern = name
| literal-constant
| (cons pattern pattern)
| (name pattern ...)
| (? name)

dispatches like a cond, matching the result of case-expr sequentially against all patterns. The first successful match triggers the evaluation of the matching body-expr, whose value is the result of the entire match expression.

The literal constants commonly used are numbers, strings, symbols, and '().

Each pattern that contains names binds these names in the corresponding body-expr.

Matching a value with a pattern proceeds according to the following rules. If the pattern is a

name, it matches any value;
literal-constant, it matches only the literal constant;
(cons pattern_1 pattern_2), it matches when the value is an instance of cons, and its first/rest fields match pattern_1 and pattern_2, respectively;
(name pattern ...), it matches when the value is an instance of the name structure type, and its field values match pattern ...;
(? name), it matches when name refers to a predicate function and the latter produces #true on the given value.

Furthermore, if the given pattern is name and the value is V, name stands for V during the evaluation of the corresponding body-expr.

The following match expression distinguishes conses with '() in the second position from all others:

> (define (last-item l)
     (match l
       [(cons lst '()) lst]
       [(cons fst rst) (last-item rst)]))
> (last-item '(a b c))
'c

With ?, a match can use a predicate to distinguish arbitrary values:

> (define (is-it-odd-or-even l)
     (match l
       [(? even?) 'even]
       [(? odd?)  'odd]))
> (is-it-odd-or-even '1)
'odd
> (is-it-odd-or-even '2)
'even

A match expression can also deal with structure instances:

> (define-struct doll (layer))
> (define (inside a-doll)
    (match a-doll
      [(? symbol?) a-doll]
      [(doll below) (inside below)]))
> (inside (make-doll (make-doll 'wood)))
'wood

Note, however, that the pattern uses just doll, the name of the structure type, not make-doll, the constructor name.

2.5.3 Algebraic Data Types

syntax
(define-type type (variant (field predicate) ...) ...)

type = name

variant = name

field = name

predicate = name

defines structure types variant ... with fields field ..., respectively. In addition, it defines constructors that enforce that the field values satisfy the specified predicate. Finally, it introduce the name type as the name for the union of all variant structure types and type? as a predicate that determines whether a value belongs to this class of values.

Consider the following type definition:

(define-type BTree
(leaf (info number?))
(node (left BTree?) (right BTree?)))

It defines two structure types:

(define-struct leaf (info))
(define-struct node (left right))

The make-leaf constructor signals an error when applied to any other values but numbers, while make-node accepts only instances of BTree. Finally, BTree? is a predicate that recognizes such instances:

> (make-leaf 42)
(leaf 42)
> (make-node (make-leaf 42) (make-leaf 21))
(node (leaf 42) (leaf 21))
> (BTree? (make-node (make-leaf 42) (make-leaf 21)))
#t

And here is how a constructor fails when applied to the wrong kind of values:

> (make-leaf 'four)
make-leaf: contract violation
  expected: (or/c undefined? number?)
  given: 'four
  in: the 1st argument of
      (-> (or/c undefined? number?) leaf?)
  contract from: make-leaf
  blaming: use
   (assuming the contract is correct)
  at: program:2.0

syntax
(type-case type case-expr (variant (field ...) body-expr) ...)

dispatches like a cond, matching the result of case-expr sequentially against all variants. The first successful match triggers the evaluation of the matching body-expr, whose value is the result of the entire type-case expression.

A type-case expression also ensures that (1) the collection variant cases covers all variant structure type definitions in type and (2) that each variant clauses specifies as many fields as the definition of type specifies.

Assume that the following definition is placed in the scope of the above type definition for BTree:

(define (depth t)
  (type-case BTree t
    [leaf (info) 0]
    [node (left right) (+ (max (depth left) (depth right)) 1)]))

This function definition uses a type-case for BTree and the latter consists of two clauses: one for leafs and one for nodes. The function computes the depth of the given tree.

> (depth (make-leaf 42))
0
> (depth (make-node (make-leaf 42) (make-leaf 21)))
1

top ← prev up next →

2.1	Batch Input/ Output: "batch-io.rkt"
2.2	Image Guide
2.3	Images: "image.rkt"
2.4	Worlds and the Universe: "universe.rkt"
2.5	Abstraction: "abstraction.rkt"
2.6	Planet Cute Images
2.7	Porting World Programs to Universe

2.5.1	Loops and Comprehensions
2.5.2	Pattern Matching
2.5.3	Algebraic Data Types