6.001/Recitation 7

Rob Speer

Contents 1 Type notation 2 Brain teaser 3 Questions 4 fold-left and fold-right 5 When all you have is a hammer, everything looks like a nail 6 Contrived problems 7 Story time

Type notation

Here's a summary of what can appear in type notation:

Simple types

• Number (can be Integer, Real, or Rational)
• String
• Symbol
• Boolean
• Null (also called nil or empty)

Procedures

Written as (X₁, X₂, ... → Y), where X₁, etc. represent the types of the arguments, and Y represents the type of the results.

Variable types

A, B, etc. are used as variables in type notation.

Compound types

• Pair<A, B>
• List<A>
• Occasionally you'll see a type like (A or B).

Brain teaser

As usual, this is a hard problem to work on if you're bored.

What's the type of this function? (This is out at the hairy fringes of our type notation, so there may not be one best answer.)

(λ (f) (f f))

Some thoughts that may or may not help refine your answer:

• Types are sets. Keep track of when you want supersets and when you want subsets. Equals signs may lead you astray.
• What if you can add additional constraints on types besides what you get from notation?
• What if you can use and in a type, meaning that an object has to satisfy both types simultaneously?

Questions

1. What's the type of map?
2. What's the type of filter?
3. The lecture said that the type List<A> is the same as Pair<A, List<A> or Null>. What's a more inclusive way to express the type?

fold-left and fold-right

These apply a two-argument procedure repeatedly over a list, starting with an initial value that is the initial first argument, and applying the procedure at each step to the result so far and the next item in the list. Yeah. Demonstrating on the blackboard may help.

1. The SICP book has another name for fold-right, which is accumulate. (It isn't part of R5RS Scheme, so you can't use it in DrScheme without defining it). Why does fold-right get the attention? What's "right-handed" about Scheme?
2. Write fold-right.
3. Write fold-left.
4. What is the type of each procedure?

When all you have is a hammer, everything looks like a nail

Write map using fold-right.

Write append using fold-right.

Write reverse using fold-right.

Contrived problems

1. What is the type of (lambda (f g x) ((f g) x)) ? (You saw compose in lecture, but this is different.)

2. What is the type of:

(lambda (a b c d)
  (if (a b) (b c) (d c)))

3. What does this return? Or, perhaps more reasonably, give a simpler expression that returns the same thing. (x2 and x3 are Church numerals.)

(apply (fold-right map (list x2 x3) (list x2 x3)))

If you actually try to evaluate it, I assume you will run out of memory.

Story time

In the corresponding chapter of SICP to this topic, there's a really excellent footnote I want to read about William Barton Rogers, the fovnder of MIT.