ITEC 380 2008fall ibarland

home—info—lectures—exams—archive

lect05c
lect05c: accumulator, foldr

We review another example of using the design recipe 
this time, mutually recursive: a file system.
That's the "v1" versions of total-size, ls.


We have learned about map, filter, and foldl.
Note that prefix-all is really a loop -- which type of loop is it?
Write total-size-v2 which is just like total-size-v1, except that
  instead of calling prefix-all, it uses the loop idiom directly.
  (Alternately: re-write the body of size-of-am
How would we use map, to add a prefix to each path in a list-of-paths?
(See -v2.)


Okay, that was okay.
Note that size-of-many was also a loop.  What type of loop?
Let's go further, and not even call 'size-of-many',
and call that loop idiom directly!
(See -v3.)




Practice: do the same as above for ls  
(write a ls-v2 which doesn't call prefix-all;
 then write a ls-v3 which doesn't call ls*.)





-----
Okay, let's back up, to an easy example:
adding numbers in a list, using the template.

; In scheme:
(define (sum-all nums)
  (cond [(empty? nums) 0]
        [(cons?  nums) (+ (first nums) (sum-all (rest nums)))]))


// In Java:
int sumAll( List<Integer> nums ) {
  int ssf = 0;   // "sum-so-far"
  while (!nums.isEmpty()) {
    ssf = ssf + nums.get(0);
    num = nums.removeAt(0);
    }
  return ssf;
  }


How do these two implementations differ?
First, let's work the scheme version through the stepper,
on a list of 10 numbers:
- We have a stack of pending work!
- The scheme adds right-to-left, while Java adds left-to-right.
- the java is udpating (mutating) ssf, nums as we procede.
- the java might overflow int :-)

This is a big problem for scheme, building up all that stack space!

Solution: accumulators
(covered in lect06a):

(define (sum-all-v2 nums)
  (sum-all-loop nums 0))

(define (sum-all-loop nums ssf)
  (if (empty? nums)
      ssf
      (sum-all-loop (rest nums) (+ ssf (first nums)))))

This scheme code is parallel to the Java: 
the helper-function is the body of the loop,
and the inital wrapper function is the code that sets up the
initial variables.
The Java "ssf = ssf + nums.get(0)" corresponds to
  passing in (+ ssf (first nums)) as 
  the "new" value of ssf in the recursive call.
Similarly, passing in (rest nums) as the new value for nums
corresponds to [Which line of the Java code?].

home—info—lectures—exams—archive

©2008, Ian Barland, Radford University Last modified 2008.Oct.14 (Tue)

Please mail any suggestions (incl. typos, broken links) to iba�rlandrad�ford.edu