CSC 151.01, Class 29: Files in Scheme

Overview

• Preliminaries
  • Notes and news
  • Upcoming work
  • Extra credit
  • Questions
• Debrief on trees
• Debrief on higher-order procedures
• Lab
• Debrief (?)

Preliminaries

News / Etc.

• There are two stacks of cards, one for students who want to choose their partners on HW 7 and one for students who want random partners.
  • Please email me your partner setup asap.
• You should have received a grade report on Monday. Let me know if you did not. (Sorry for the delay in getting those out.)
• Mentor sessions Thursday at 7:00 p.m. and 9:00 p.m.
• Warning! Friday the 13th falls on a Friday this month. Please be extra careful.

Upcoming work

• Exam 3
  • Epilogue due TONIGHT via email
  • Cover sheet due in class NOW
• Lab writeup for class 29: Exercise 4.
• Reading for Friday
  • Analyzing procedures
• Flash Cards due TONIGHT at 9pm.
  • Optional.
  • Grade is percent of eight flashcard assignments you complete (capped at 100%).
• Assignment 7 due next Tuesday at 10:30 p.m.
  • You may choose to work with a particular partner
  • You may choose to get a randomly assigned partner.
  • You may talk to me individually about work alone.
• Quiz Friday
  • Vectors
  • Trees
  • Higher-order procedures
  • Excitement!

About Assignment 7

• Two options
  • Random text generation
  • (Really) Simplified machine learning
• Random text generation
  • Gather statistics about text
• SImplified machine learning
  • Predict cancer
• An excellent resource on why we shouldn’t trust machine learning Weapons of Math Destruction.

Extra credit (Academic/Artistic)

• Any one activity in the student research symposium next week.
• Water Dance performance at CERA on Saturday.
• Art and Science of field work Sunday at CERA. RSVP necessary. You should have received email.

Extra credit (Peer)

• Drag show April 14

Extra credit (Recurring peer)

• Listen to KDIC Wednesdays at 6pm - Witty banter with other personalities and/or co-host. Also Indian, Arabic, and Farsi music.
  (Up to two units of extra credit.)
• Peer editing with SS. Talk to SS about the details. Make your English Lit more literate.

Extra credit (Misc)

• Host one or more prospective students. (I think there’s one visit weekend left.)

Other good things

Questions

What’s the “best of” part on my grade report?

• 5% of your grade is the best of (average exam),(average quiz),final

Debrief on trees

Not covered in class, but included so that students can reflect/review.

• Observation: You generally can’t use tail recursion on a tree, since you have to recurse down both the left subtree and the right subtree.
  • Some exceptions, such as when you only need to use one subtree.
• Observation: We’ve tried to separate the implementation of trees (which could be with vectors or with pairs) from the use. The “clients” that work with trees need only know the basic operations: node, leaf, contents, left, right, node?, and empty?.
  • That’s similar to the idea that you only needed to know cons, car, cdr, and null? to use lists.
• Important to distinguish the two kinds of trees we’ve build
  • Generalized binary trees have no particular ordering of the values.
  • Binary search trees (bsts) have the property that smaller things are in the left subtree, larger things are in the right subtree, and both subtrees have the same property.

We’ll look at number-tree-smallest, which turns out to be nontrivial to write.

• The parameter needs to be nonempty. That means that we probably need multiple cases: No left subtree, no right subtree, neither subtree.
• Some of you tried to get around this by using zero for the empty subtree. But zero may not be smaller than everything else in the tree. In particular, we may have negative numbers.

;;; Precondition:
;;;   ntree is not empty
(define number-tree-smallest
  (lambda (ntree)
    (cond
      [(leaf? ntree)
       (contents ntree)]
      [(empty? (left ntree))
       (min (contents ntree)
            (number-tree-smallest (right ntree)))]
      [(empty? (right ntree))
       (min (contents ntree)
            (number-tree-smallest (left ntree)))]
      [else
       (min (contents ntree)
            (number-tree-smallest (left ntree))
            (number-tree-smallest (right ntree)))])))

Debrief on higher-order procedures

Not covered in class, but included so that students can reflect/review.

• Yes, you are now at the point that you can write map, filter, reduce, all, and many others.
• You can even write conjoin
• Two key issues
  • You can take procedures as parameters and apply them.
  • You can build a new procedure and return it (most frequently, with lamda)

Writing (remove val pred?) with direct recursion.

(define remove
  (lambda (lst pred?)
    (cond
      [(null? lst)
       null]
      [(pred? (car lst))
       (remove (cdr lst) pred?)]
      [else
       (cons (car lst)
             (remove (cdr lst) pred?))])))

Writing (both pred1? pred2?). We’re returning a procedure, so we need a second lambda for the procedure we are returning

(define both
  ; The first lambda defines both
  (lambda (pred1? pred2?)
    ; The next lambda defines the procedure we're returning
    (lambda (val)
       (and (pred1? val) (pred2? val)))))

Lab

How do I see what’s in the file of numbers?

• (file->lines "/home/rebelsky/.../numbers.txt")

What’s the difference between a file name, an input port, and an output port?

• A file name is a string that gives the location of the file. That’s what we’ve used in the past with file->lines and such.
• An input port links more directly to a file and includes a notion of the current position in the file. (Just as we keep track of the current position in a book or article.) You use input ports to read from a file
• An output port is much like an input port except you use it to write output.

Writeup: Exercise 4

Debrief

Hah! Even with 80-minute classes, Sam plans to much for each class period.