7. Review 2

Review of folding. Ch 6 material.

These exercises are written to give practice using a fold operation. Your solution should have the form

f xs = foldl fhelp initial xs
  1. (rt) Make a function to produce a reversed running total of the integers in the input as well as the count of how many numbers appeared.

     checks = [
       rt [9] == ([9,0],1)
       ,rt [9,5] == ([14,9,0],2)
       ,rt [9,5,6] == ([20,14,9,0],3)
     ]
    
    1. Write a possible signature for rt.
    2. You are required to use a fold to write the function rt. Suppose that you have already completed a working helper function called rth. Write the body of your main function rt using a fold and your helper.
    3. What signature does the helper function rth need to have?
    4. Write the helper function rth.
  2. (short) The shortener packs all of the words in a list together into one word and finds the last n letters of the result.

     checks2 = [
       short 5 ["pine"] == "pine"
       ,short 5 ["pine","x"] == "pinex"
       ,short 5 ["pine","x","yeet"] == "xyeet"
       ,short 5 ["pine","x","yeet","glues"] == "glues"
       ]
    

    You are required to use a fold to write the short function.

    1. Write the signature of short.
    2. Write short using a fold and a helper function of some kind.

Notes

What are fold functions good for? They are an example of a way to write a “streaming” or “online” algorithm. A streaming algorithm does not need all of the data present before it starts the computation. Watching videos is a common example of “streaming” (you do not download the whole video before you start watching). Computer applications that process more data than can fit in memory are another realistic example. For example, particle physics experiments easily collect a petabyte of data (1 million gigabytes) in a second.

Last modified October 29, 2024: New review material and typo correction. (a9d002b)