RU beehive logo ITEC dept promo banner
ITEC 380
2014 fall
ibarland

most recent semester

hw06
tail recursion; map, filter

Due: due Nov.02 (Sun) 23:59 on D2L (including a .java file for #1a); bring hardcopy to class. (For hardcopy, you may paste just the one Java method as a racket comment, and only print that one file.)

  1. (0pts) Reading: §6.6, and §10.1-10.2.
    (Additional recommended, but not required, background reading: all of Chpt.6, and §10.3. Additional, non-required, challenge-reading: § 10.5.)
  2. Write count-bigs-v2, which is like count-bigs from hw05a-soln.rkt:
    1. (5pts) Write it in Java, using a while-loop, and updating an accumulator (“so-far”) variable, and updating the list by using java.util.List#subList. (Similar to sum_v2 in the Java class notes.)
    2. (5pts) Write it as a tail-recursive function in racket (similar to sum-v2 in the racket class notes.)
      3. The two versions should be as similar as possible, doing the same thing in the same way, and using the same names for corresponding variables/functions, Between the two versions, use the same name for any variables/functions that correspond, up to idiomatic spelling — e.g. in the notes’ sum_v2, the Java variable sumSoFar corresponded to the Racket variable sum-so-far.
  3. (2pts) What is the signature for map?                                                             
    (that is, the version of map we wrote in class, and that is in the student languages). Give your answer in a comment.

    Note: “function” is not a specific-enough type, although something like “number → boolean” is. Similarly, “list” is not specific enough1, but “(listof string)” is.

  4. (5pts) Write upcase-string, by: calling string->list, then using map to upcase-char-upcase each letter, following by calling list->string. (You should be in intermediate-student with lambda, for this.) 
    (check-expect (upcase-string "Hello?!") "HELLO?!")
    Include a few other trivial check-expects: the empty string, a liststring of length 1 (lowercase), a liststring of length 1 (non-lowercase).

  5. (5pts) Write mask-non-alphabetic, which turns all non-alphabetic characters in a string into undercores: 

    (check-expect (mask-non-alphabetic "hello?!") "hello__")
(check-expect (mask-non-alphabetic "He said 'What?'?!") "He_said__What____")
    Also include four more “trivial” check-expects: test the empty string, a string-of-length-one which is alphabetic, a string-of-length-one which is not alphabetic, and a test case including an underscore.

    Do not use the template for a list-processing function; instead your function should call map, passing it a lambda expression. (It will also call string->list and list->string, along with char-alphabetic?.)

  6. (5pts) Write map-if, which applies (maps) a function to every each element of a list if it that meets some condition (and leaving it unchanged otherwise). Your implementation should consist entirely of a call to map, whichwith a lambda-expression. 
    (check-expect (map-if even? sqr (list 2 3 4 5)) (list 4 3 16 5))
(check-expect (map-if negative? (lambda (k) 0) (list 2 -2 3 -3)) (list 2 0 3 0))

; For the next test, download char-shift.rkt and place it in the same directory,
; and then uncomment the next two lines:

#;(require "char-shift.rkt")
#;(check-expect (list->string (map-if char-alphabetic?
                                    (lambda (c) (shift-char c -3)) 
                                    (string->list "Careful; eavesdroppers!")))
              "Zxobcri; bxsbpaolmmbop!")
  7. (5pts) Write the following function, based on the data-definition anc-tree.rkt as discussed in ../Lectures/lect26-ancestor-tree.rkt: 
    ; subst-colors : symbol symbol anc-tree  →  anc-tree
; Return a tree like `a-tree`, except every `old-col` eye-colors is
; replaced with the eye-color `new-col`.
;
(define (subst-colors old-col new-col a-tree)
  …)
  
; using names defined in the anc-tree data-definition  
(check-expect (subst-colors 'orange 'teal bart) bart)
(check-expect (subst-colors 'brown 'hazel bart)
              (make-child "Bart" 
                          1979
                          'hazel
                          marge
                          (make-child "Homer" 
                                      1955
                                      'hazel
                                      (make-child "Mona" 1929 'hazel 'unknown 'unknown)
                                      abe)))
    Provide additional check-expects involving 'brown to 'hazel in: 'unknown, the anc-tree jackie, the anc-tree marge, and the anc-tree homer.
    Note that you can (require "anc-tree.rkt"),
  8. (Extra credit) Write reverse, which reverses the elements of a list: 
    (check-expect (reverse-v1 (list 'a 'b 'c)) (list 'c 'b 'a))
    Write two versions of this function:
    1. (5pts) reverse-v1, which follows the usual design recipe. You'll need to create a helper-function to do this. (That helper function will itself follow the design recipe, of course!) (Do not use the built-in function append.)
    2. (5pts) as a tail-recursive function. (Call this version reverse-v2 or such.)
    3. (3pts) Time2 these two versions on some long lists and explain the timing results. Hint: in general, tail-recursion does not change the asymptotic running time of a function. However, processing elements left-to-right vs. right-to-left may change the big-Oh running-time. For creating longer cases, you might use the function nums-down-from from lecture.

1 The reason is fairly solid: (map expt (list "hello" (list 2 3) true)) is certainly taking in a function and a list, but it is fraught with type errors.      ↩

2See time, or time-apply.      ↩

most recent semester

©2014, Ian Barland, Radford University
Last modified 2014.Aug.30 (Sun)		 Please mail any suggestions
(incl. typos, broken links)
to ibarlandradford.edu		 Rendered by Racket.