Functional Problem Solving (CSC 151 2016S) : EBoards
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] - [FAQ] [Teaching & Learning] [Grading] [Taking Notes] [Rubric]
Current: [Assignment] [EBoard] [Lab] [Outline] [Reading]
Sections: [Assignments] [EBoards] [Labs] [Outlines] [Readings] - [Examples] [Handouts]
Reference: [Setup] [Remote] [VM] [Errors] - [Functions A-Z] [Functions By Topic] - [Racket] [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [Curtsinger (2016S)] [Davis (2013F)] [Rebelsky (2015F)] [Weinman (2014F)]
Misc: [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] - [Issue Tracker (Course)]
Overview
We've been looking at recursion, particularly recursion over lists.
In writing recursive procedures, we often find it helpful to write recursive helper procedures.
Detour: Which is more efficient?
(define sum
(lambda (lst)
(if (null? lst)
0
(+ (car lst) (sum (cdr lst))))))
vs.
(define sum
(lambda (lst)
(sum-helper 0 lst)))
(define sum-helper
(lambda (so-far remaining)
(if (null? remaining)
so-far
(sum-helper (+ so-far (car remaining))
(cdr remaining)))))
Note: Those two are more-or-less equally efficient.
Sometimes leads us to more efficient solutions.
In contrast, when defined with helper recursion, this is usually pretty efficient
(define irgb-brightest (lambda (colors) (cond ; Only one color [(null? (cdr colors)) (car colors)]
; More than one color, first color is one of the brightest
[(>= (irgb-brightness (car colors))
(irgb-brightness (irgb-brightest (cdr colors))))
(car colors)]
; More than one color, first color is not one of the brightest
[else
(irgb-brightest (cdr colors))])))
Note: We assume that there is at least one color
If we use helper recursion, we can write
(define irgb-brightest
(lambda (colors)
(irgb-brightest-helper (car colors) (cdr colors))))
(define irgb-brighest-helper
(lambda (so-far remaining)
(cond
; We've looked at all the colors
[(null? remaining)
so-far]
; The best estimate so far is at least as bright as the
; next available color
[(>= (irgb-brightness so-far) (irgb-brightness (car remaining)))
(irgb-brightest-helper so-far (cdr remaining))]
]
; The next available color is brighter
[else
(irgb-brightest-helper (car remaining) (cdr remaining))]
])))
We also use helpers because the "table method" (see the whiteboard) can help us design and implement recursive procedures.
And it's a lot easier to print out the status of your procedure.
Our past experience tells us that helpers should be local.
We'd like to write
(define irgb-brightest
(let ([irgb-brighest-helper
(lambda (so-far remaining)
(cond
; We've looked at all the colors
[(null? remaining)
so-far]
; The best estimate so far is at least as bright as the
; next available color
[(>= (irgb-brightness so-far) (irgb-brightness (car remaining)))
(irgb-brightest-helper so-far (cdr remaining))]
]
; The next available color is brighter
[else
(irgb-brightest-helper (car remaining) (cdr remaining))]
])))
(lambda (colors)
(irgb-brightest-helper (car colors) (cdr colors)))))
Problem: let doesn't work for recursive procedures.
Solution one: Use letrec instead.
Solution two: Use something that matches our table model: named let.
(define irgb-brightest
(lambda (colors)
(let irgb-brightest-helper ([so-far (car colors)]
[remaining (cdr colors)])
(cond
; We've looked at all the colors
[(null? remaining)
so-far]
; The best estimate so far is at least as bright as the
; next available color
[(>= (irgb-brightness so-far) (irgb-brightness (car remaining)))
(irgb-brightest-helper so-far (cdr remaining))]
]
; The next available color is brighter
[else
(irgb-brightest-helper (car remaining) (cdr remaining))]
])))
Start looking at the lab.