EBoard 19: SoLA 2

This class will be recorded! Its use is limited to members of the class. Please do not share with others.

Approximate overview

• General administrative stuff [~5 min]
• Q&A [As long as it takes, no more than 90 min]
• SoLA 2

Administrative stuff

Notes and news

• No class Friday. Take a breather. Do some work for CSC 151. Shop. Spend time with family. Whatever works best for you.
• SoLA 2 has a late due date. That is only for students who arranged an extension on SoLA 2 for specific reasons. Others who turn in work late will receive a 0.
• I hope you have fun and do well on SoLA 2.

Notes to read in next class (just so I don’t forget)

• When I ask you to post an answer in the chat (it’s rare), please do so even if someone else seems to have posted something similar. I use those as another quick check on understanding.

Tutoring reminders

• Please use our tutors! They like to work.
  • Don’t use them for help on the quizzes or learning assessments.
• Evening tutoring will be available
  • 8-10 p.m. Sundays through Thursdays
  • 3-5 p.m. Sundays
  • In the “Drop in tutoring” channel on the CS team.
  • Sam will generally not be available during these times.
• Individual tutors are temporarily unavailable. We’re recruiting more.
  • Don’t let this stop you from requesting one.

Upcoming activities

Attend (or watch recording) and send a one-paragraph reflection.

• None currently scheduled.

Upcoming work

• SoLA2: Today!
• Redo of Mini-project 2 (due Monday the 30th at 10:30 p.m. CST)
• Redo of Mini-project 3 (due Monday the 30th at 10:30 p.m. CST)
• Mini-project 4 (due December 2 at 10:30 p.m. CST)
• Reading for Wednesday
  • Numeric recursion
• Quiz Wednesday: Recursive templates and matching.

Q&A

How do I match a singleton list, binding the one value to x?

The pattern (list x) works.

The pattern (cons x '()) works.

> (match '(23)
    [(list x)
     (list x x x)])
'(23 23 23)
> (match '(11 23)
    [(list x)
     (list x x x)])
. . match: no matching clause for '(11 23)

> (match '(23)
    [(cons x '())
    w
     (list x x x)])
'(23 23 23)
> (match '(23 24)
    [(cons x '())
     (list x x x)])
. . match: no matching clause for '(23 24)

How do I rewrite vowel? without lambda?

What are the steps we want to do?

Convert it to a lowercase letter.
Find the index of the converted letter in a list of lowercase letters. Verify that the index is an integer.

When you want to do things in sequence, use o, which requires a sequence of singleton procedures. They appear in a right-to-left order. (That is, we do the rightmost, then the next-to-rightmost, etc.)

Convert to a lowercase letter: string-downcase. Yup, one parameter.

Find the index: (index-of lst val). We know the list. So we can use section to turn the two-parameter procedure into a one-parameter procedure. (section index-of (string->list "aeiou") <>).

Check if it’s an integer: integer?

  (define vowel? 
    (o integer? 
       (section index-of (string->list "aeiou") <>)
       char-downcase))

Do we have to document the procedures?

No, except on the documentation problem.

How do we decide on base cases?

When do we know that we’ve reached the base case? When is the input simple enough that I don’t need to recurse?

Typical answers for lists: Empty list. One-element list. Two-element list.

What type am I supposed to return?

What value should I return?

Example one: “largest in list”. I can’t find the largest in an empty list. I think I can find the largest in a single-element list. So I’ll use that as my base case.

If there’s only one element, it must be the largest.

Base case: If the list has one element, use that one element.

Recursive case: If the list has more than one element, it’s the larger of the first element and the largetst remaining element.

(define largest-in-list
  (lambda (lst)
    (match lst
      [(list singleton)
       singleton]
      [(cons val vals)
       (max val (largest-in-list vals))])))

(check-equal? (largest-in-list '(1 2 3)) 3 "at end")
(check-equal? (largest-in-list '(1 7 -5)) 7 "middle, include negatives")

Where did vals come from?

match binds the first and rest of the list to the names we used in the cons pattern.

How does the (list val) work?

This requires a build of delving into how match works.

When match sees a pattern, it asks if the value its given has the same form/value/etc. as the pattern.

If the pattern contains any names (unquoted words that are not procedures), match binds the corresponding part of the value to those names.

The pattern (list val) represents a list of one value. But val is a name, so it matches “anything” If the original thing we are matching (lst) is a list of one value (same form), it binds that one value to val and say it matches.

What’s the difference between writing a recursive procedure with cond vs. match?

Use whichever is easier for you.

Match has the advantage of doing some bindings automatically.

(define largest-in-list
  (lambda (lst)
    (if (null? (cdr lst)) ; Hard to read as "singleton list"
        (car lst)
        (max (car lst) (largest-in-list (cdr lst))))))

There is likely some computational overhead to match.

When there are very particular cases, use match.

(define pointless
  (lambda (lst)
    (match lst
      [(list 1)
       "We're number one"]
      [(list 2)
       "Two is better than one"]
      [(list x)
       "Singleton"]
      [(cons first rest)
       (pointless rest)])))

I’d like to know more about the bindings. How can the variable name appear within multiple blocks?

Bindings in blocks are independent.

Match binds by first looking at the structure to see if it matches and then looking within the structure to see if it matches.

Could you clarify on edge cases? What are you looking for.

Something at the “edge” of the input. Valid, but extreme. As small as you can go (if there’s a lower limit), as large as you can go (if there’s an upper limit), fairly small (if no lower limit), fairly large (if there’s no upper limit), “strange”

In some ways, similar to thinking about the base case.

Empty lists, empty strings, 0, 1, -1

In the pointless procedure above, what do first and rest refer to?

The pattern (cons first rest) matches any non-empty list and binds the first element of the list (aka the car of the list) to first and the remainder of the list (aka the cdr of the list) to rest.

The pattern (cons x xs) matches any non-empty list and binds the first element to x and the rest to xs.

What does the pattern (cons a (cons b c)) match and bind?

Matches a list of at least two elements.

Binds a with the first element of the list.

Binds b with the second element.

Binds c with the list of all remaining elements.

Explain about the makeup LAs

I just want you to get it correct once, which shows that you understood at some point this semester. You get full credit if you do so.

The questions do change, though.

Could you explain that (cons a (cons b c)) match example again?

First step in matching: Is the structure the same?

cons represents a list of one or more elements. So the outermost cons ensures that the list has at least one element

“I need a list with one or more elements whose remainder matches (cons b c)” What matches (cons b c)? A list of one or more elements whose remainder matches c.

I need something that matches c. Anything matches c.

It’s doing a recursive process for matching. Whee!

How can we do without a lambda with o and section?

Both o and section return a procedure, so we don’t need the lambda to say “this is a procedure”.

(o f g h) builds a procedure that behaves in the following way.

input goes into h, h’s output goes into g, g’s output goes into f, f’s output gets returned.

input -> h -> g -> f

We don’t explicitly mention the input.

What should we do if we turned in one of those unreadable labs?

Sam will try to fix it. Thanks for the reminder.

Do we have to stay or can we go start to SoLA?

Do whatever you want. The eboard remains. The recording remains.

When will the grade for the second mini project come?

Tonight!

Can you explain this code?

(define select-special-words
  (lambda (words)
    (filter (o (section > <> 2) count-vowels) words)))

How does it work?

We see o, so we are joining multiple procedures.

count-vowels takes a word as input and returns the number of vowels in that word.

(section > <> 2) is a quick way to write (lambda (x) (> x 2)), so it means “greater than two”

Overall, the predicate is “more than two vowels”.

With the filter, we select words with more than two vowels.

What are the key list procedures and what do they return?

filter - pulls out elements, gives us a list

map - transforms every element

tally - counts elements, returns an integer.

What would that earlier composition look like as a lambda statement?

(define special-word?
  (lambda (word)
    (> (count-vowels word) 2)))

Or

(define more-than-two
  (lambda (val)
    (> val 2)))

(define special-word?
  (lambda (word)
    (more-than-two (count-vowels word))))

How should I think about (o f g h). The parameter is implicit.

Let’s think about it in terms of tracing. Suppose foo whose definition is (o f g h).

    (foo (+ 2 3))
--> (foo 5)
--> (f (g (h 5)))

I try to avoid matching. Please help me.

Match is a variant of cond.

Like cond, it tries things in sequence until it finds one that works. (cond: the guard holds; match the pattern matches the value)

How do we tell if a pattern matches the value?

A variable matches anything. (match exp [var ...]), the var will always match. When a variable matches, it binds the value to the variable.

A (cons _ _) matches any nonempty list, provided the first element of the list matches the first parameter to the cons and the rest of the list matches the second parameter to the cons.

By implication (cons first rest), first is a variable, rest is a variable, so this matches any nonempty list.

Trace example

    (match '(5) ([x (list x x)]))
    ; Can we match `x` to `(5)`?  Yes!  `x` is a variable
    ; We have bound x '(5)
--> (list '(5) '(5))

    (match '(5) ([(list) "empty"] [(cons x xs) x] [other "other"]))
    ; Does '(5) match the empty list?  No.  Not an empty list.  Throw away.
--> (match '(5) ([(cons x xs) x] [other "other"]))
    ; Does '(5) match "a non-empty list with head x and remainder xs"?
    ; Yes, it's a nonempty list
    ; Bind x to 5 and xs to '()
    : It matched, use the body of that match
--> 5

    (match '(5) ([(list) "empty"] [(cons 1 xs) xs] [other "other"]))
    ; Does '(5) match the empty list?  No.  Not an empty list.  Throw away.
--> (match '(5) ([(cons 1 xs) x] [other "other"]))
    ; Does '(5) match a list starting with 1? No!
    ; On to the next pattern 
--> (match '(5) ([other "other"]))
    ; Does '(5) match the variable `other`?  Yes, variables match anything!
    ; When the variable matches, we bind.  `other` is now bound to '(5)
    ; We don't use it, but it's bound
    "other"

I missed some quiz makeups. Could you just extend all of them?

Sure. I’ll so after the SoLA.

Will you announce due dates in the future?

I try.

Is Sam nice?

I don’t think you understand the question.

My patner and I forgot to negotiate who was supposed to submit the lab, and neither of us did. What should we do?

Ask Sam to be generous and not mark us as late. With details.

Tokens are cheap.