Haskell Worksheet 4, due Monday, April 3

This worksheet focuses largely on

• function application and composition
• merge sort, and
• lazy evaluation.

These topics are covered in some detail in online readings on Higher order functions, Performance/Laziness, and Lazy Evaluation

Problems for this Worksheet 4 with Haskell

This worksheet expands experience with functional problem solving with Haskell. For this worksheet,

• all code should be written in Haskell
  • code should be typed, as it would be loaded into a Haskell environment.
  • representative output for each problem should be included.
  • Warning: Submitted output must come from the submitted code.
    (If output could not have come from submitted code, the homework may be interpreted as a possible academic honesty violation, following university policies and procedures.)
• as noted in class, the "do" construct in Haskell introduces imperative problem solving and thus contrasts to the focus of Haskell and CSCI 291 on functional and declaration problem solving. For this reason, use of the "do" construct is not allowed in Haskell functions for this course. Any use of "do" will result in an automatic score of 0 on the problem being solved.
• similarly, any construct to change a variable's value is expressively forbidden, since changes are contrary to functional problem solving. (Use recursion instead to update parameters within a new context.)
• In browsing the Web, you many discover that Haskell provides an indexing capability for lists: the expression lst !! i accesses the ith element of the list lst. While this seems similar to array access in Java or other languages, behind the scenes, this operator requires a list traversal from the beginning of the list, counting as one goes from node to node. Thus, this index operator has O(i) rather than O(1) for common array access in other languages. With this observation, use of indexing within a list should not be used for efficiency reasons, unless this is required explicitly by a specific problem.
• Within this worksheet, you should use local bindings and local functions within a function itself, excluding any parameters that may be required in the definition of the function.

Functional Application and Composition

1. Consider the following three Haskell functions:

         f x = x*x - 6*x + 9   -- note this is (x - 3)*(x - 3)
         cube x = x*x*x
       

   1. Assuming that f and cube have been defined previously, write a 1-line Haskell function h that computes the composite function cube (f (sqrt x)). The resulting expression for h should not use parentheses!
   2. Test your function on several cases, for which you can easily verify the results (e.g., with a simple hand computation).
   3. Explain briefly, in your own words, why the definition h x = cube f sqrt x does not work.

2. Transforming Items on a List and Counting How Many Meet a Stated Criterion: A common task is to consider how many items on a list satisfy a given criterion. However, in practice, this work may be divided into three steps:

   • transform a list item with a function tr
   • determine if the transformed item satisfies a predicate pred
   • count the number of validated transformed list items

   Two examples follow:

   • Example 1: a list of numbers
     • transform each number according to the function

                       f x = x*x - 6*x + 9  -- the same as (x-3)*(x-3)
                     

     • use the predicate that the transformed number must be ≤ 4.
     • Sample case: Starting with the list [0,2,4,6],
       the transformed list is [9,1,1,9],
       so the number of items ≤ 4 is 2.
   • Example 2: a list of strings
     • transform a string by looking at the first 2 characters (or the full string, if has length < 2)
     • use a predicate that determines if this substring contains the letter 'q'
     • Sample case: Starting with ["kumquats","are","quite","a","fruit"]
       the list with the first two letters of each word is ["ku","ar","qu","a","fr"]
       so the number of desired items is just 1.

   Given this framework, a natural approach is to filter the list, based on the transformation and predicate, and then count the number of items present:

         countSpecialItems tr pred lst = length  filter pred tr lst
       

   However, this line does not compile, since Haskell seems confused by the number of functions involved.

   1. Can this line be corrected, using parentheses only? If so, how? If not, explain the trouble(s).
   2. Can this line be corrected, using $ symbols only? If so, how? If not, explain the trouble(s).
   3. Can this line be corrected, using both some parentheses and some $ symbols? If so, how? If not, explain the trouble(s).

Tuples

Note: To access elements within a tuple, pattern matching can work quite well! For example, the following functions provide access to the components of a 4-tuple:

  comp1 (a, _, _, _) = a
  comp2 (_, b, _, _) = b
  comp3 (_, _, c, _) = c
  comp4 (_, _, _, d) = d

3. Points and Circles: In mathematics, points in the plane are typically identified as (x, y)— that is as a tuple or pair.

   Write a Haskell function inCircle that has three parameters:

   • 2 tuple pairs, with the first tuple pair considered the center of a circle, and the second tuple pair a point somewhere in the plane.
   • a radius of the circle.

   The function should return true if the second tuple pair lies within a circle of the given radius, centered at the first tuple pair. The function should return false otherwise.

   Programming Notes:

   • The Pythagorean Theorem or distance formula may be useful here.
   • For efficiency, the function should NOT use the square root function, and it should not use the exponential operator ^ for squaring.

4. Searching a Symbol Table: Years ago, when reading a program, compilers would keep information about symbols (variables, function names, other identifiers) in a structure, historically called a Symbol Table. (More modern usage calls this structure a Keyed Table, as this type of storage and retrieval of data applies much more generally than recording symbols and their properties within a compiler.)

   For this problem, suppose three properties are stored for each variable:

   • The symbol (i.e., variable name or identifier)—stored as a string,
   • The type of the symbol (e.g., int, float, double, character, procedure etc.)—also, stored as a string, and
   • The location of the symbol in main memory (often an address relative to the top of the run-time stack, or the start of a block of code)—stored as a signed integer.

   For this problem, suppose the information for a symbol is stored within a triple or 3-tuple, and the collection of each symbol information is stored on a list.

   Write a function that has two parameters:

   • a symbol
   • a list of symbol triples

   If information for the symbol name is stored in the list, the function should return a pair or 2-tuple containing the type and location for that variable. If the variable name is not found, the function should return the pair ("undefined", 0).

5. A Simple Course Directory: An abbreviated version of this semester's computer science offerings is shown in the following table:

   Course Number	Section	Title	Instructor	Units
   161	A	Computer Science I	Xi Chen	1.0
   161	B	Computer Science I	David Chiu	1.0
   240		Software Engineering	Xi Chen	1.0
   261	A	Computer Science II	Henry Walker	1.0
   261	B	Computer Science II	Brad Richards	1.0
   291		Programming Language Paradigms	Henry Walker	1.0
   315		Computer Graphics	Xi Chen	1.0
   395		Computing: Opportunities and Risks	Henry Walker	0.5
   440		Capstone in Computer Science	David Chiu	1.0
   475		Operating Systems	David Chiu	1.0
   481		Compilers and Compiler Writing	Brad Richards	1.0

   1. Translate this table into a list of courses, where each course is represented by a Haskell tuple with five components.
   2. Write a Haskell function that has two parameters:
      • a course number (an integer)
      • the list of courses from part a.
      and returns a list of all course tuples with the given course number.

Merge Sort and Lazy Evaluation

As background for this section, refer to the following readings from CSCI 261A:

• Reading on Merge Sort for Arrays.
• Discussion of Merge Sort for Lists from a list-based lab.

In addition, the CSCI 291 reading on Performance/Laziness discusses several approaches for the Merge Sort for lists in Haskell.

In summary, a merge sort involves the following recursive outline:

• Base case: if a list has 0 or 1 element, then it is sorted.
• Recursive case:
  • Divide a list of size n into two sublists, each with approximately n/2 elements
  • Recursively sort the sublists
  • Merge the two ordered sublists into a single ordered list.

In reviewing this recursive algorithm, two basic functions are needed:

• Cleave: Divide a list into two sublists of about half the size
• Merge: Merge two ordered sublists into a single ordered list.

The following questions consider alternative implementations of the Cleave and Merge functions.

6. The Cleave Function and Efficiency: The reading on Performance/Laziness includes the following two approaches for dividing a list into two pieces:

   • Approach 1: (using a pair or tuple for the odd and even list elements)

         cleave1 :: [a] -> ([a],[a])
         cleave1 xs = (evens xs, odds xs)
             where
                evens []  = []
                evens [x] = [x]
                evens (x:_:xs) = x : evens xs
                odds []  = []
                odds [x] = []
                odds (_:x:xs) = x : odds xs
             

   • Approach 2: (making the list parameter explicit from the reading)

         cleave2  :: [a] -> ([a],[a])
         cleave2 xs = cleave2' ([ ],[ ])  xs
             where
                cleave2' (eacc,oacc) [] = (eacc,oacc)
                cleave2' (eacc,oacc) [x] = (x:eacc,oacc)
                cleave2' (eacc,oacc) (x:x':xs) = cleave2' (x:eacc,x':oacc) xs
             

   In this section of the worksheet, two additional approaches also are considered:

   • Approach 3: (using Haskell's indexing notation ( list !! i to access the ith element of a list.)

         cleave3 lst = (evens lst, odds lst)
             where
          evens lst = [lst !! x | x <- [0, 2 .. 2*((1+length lst) `div` 2)-1]]
          odds lst  = [lst !! x | x <- [1, 3 .. 2*((length lst) `div` 2)-1]]
             

     Note: To access the ith element of a list, one must move item-by-item from the front of the list in order to get to the ith item.

   • Approach 4: (dividing the list in half by counting)

         cleave4 lst = (firstHalf lst 0, secondHalf lst 0)
             where
               sublistSize = ((1+length lst) `div` 2)
               firstHalf lst count  --- extract first half of list
                  | count == sublistSize = [ ]
                  | otherwise  = (head lst) : firstHalf (tail lst) (count+1)
               secondHalf lst count  --- extract second half of list
                  | count == sublistSize = lst
                  | otherwise = secondHalf (tail lst) (count+1)
      
     
             

   1. Run and record the output for test cases with each of these functions to determine if they properly. If the code does not work properly, make an appropriate correction.
   2. Suppose that each of these functions are applied to a list of size n. Determine the efficiency (Big-O) of each algorithm, and provide sufficient analysis to justify your answer.

7. The Merge Function, Lazy Evaluation, and Efficiency The reading on Performance/Laziness includes one approaches for merging two ordered lists into a sorted result. A common variation also is widely reported:

   • Approach 1: (from the reading)

          merge1 :: (Ord a) => [a] -> [a] -> [a]
          merge1 xs [] = xs
          merge1 [] ys = ys
          merge1 xs@(x:t) ys@(y:u)
              | x <= y    = x : merge1 t ys
              | otherwise = y : merge1 xs u
             

   • Approach 2: (a sometimes-used variation)

          merge2 :: (Ord a) => [a] -> [a] -> [a]
          merge2 xs [] = xs
          merge2 [] ys = ys
          merge2 xs@(x:t) ys@(y:u)
              | x < y     = x : merge2 t ys
              | x == y    = x : y : merge2 t u   
              | otherwise = y : merge2 xs u
              

   1. Given two lists of length n, both of these algorithms run in O(n). Briefly explain why.
   2. Although both algorithms have O(n), can anything be said about their relative efficiency? Explain briefly.

8. Sorting and infinite lists:

   1. Which, if any, of the cleave versions could be used with lazy evaluation of potentially infinite lists? Briefly justify your answer.
   2. Repeat part a for the versions of merge.

9. Stable Sorting: Following common computing terminology, a sorting algorithm is said to be stable, if when A and B are elements have the same key and A is in a collection before B prior to sorting, then A is still before B in the sorted collection. See WIkipedia's Category:Stable sorts for more details.

   Consider the four versions of Cleave and the two versions of Merge. Which combinations, if any, of these versions yield s stable sort? Explain briefly (both why any combinations are stable and why any other combinations are not).

10. Two Haskell functions are proposed for reversing the elements on a list.

    • Approach 1

          myReverse1 :: [a] -> [a]
          myReverse1 lst =
             case lst of     []     -> []
                             (x:xs) -> myReverse1 xs ++ [x]
               

    • Approach 2

          myReverse2 :: [a] -> [a]
          myReverse2 lst = kernel lst [ ]
             where kernel :: [a] -> [a] -> [a]
                   kernel  [ ]   newList = newList
                   kernel (x:xs) newList =  kernel xs  (x:newList)
                

    In analyzing this code, three observations seem relevant:

    • Examining the start of a list (e.g., either first or rest in the expression (first:rest) is an O(1) operation, as one must just look at a reference to the first element or the second element.
    • Adding a new element onto the front of a list is an O(1) operation. (The equivalent task in Scheme is cons, and this requires allocating a block of member, setting the first part of the block to the new head, and setting the second part to the tail. Each of these steps requires just a few machine operations.)
    • Adding a new element to the end of a list is an O(n) operation, where n is the length of the list. (Here, one must create a new node, traverse the list to find the last node, and set the tail of that last node to the new box.)

    Determine the efficiency (Big-O) of both Approach 1 and Approach 2 for reversing a list of n elements, and provide sufficient analysis to justify your answer.

Extra Credit Problem

11. Alternative Sorting of a Directory: Expand the list of course tuples from Problem 5, so that it has multiple sections of courses taught by the same instructor. For example, there might be another section (section C) of 161 taught by Xi Chen and two more sections of 261 (sections C and D) taught taught by Henry Walker.

    With this expansion of the course list, modify the Merge Sort, so that it sorts the list by course title. If two course sections have the same title, ordering should be determined by the instructor's name. Finally, if two courses have the same title and the same instruction, ordering should be determined by the section letter.

    Although testing should work with your expanded course tuples, the function itself should work for any directory containing courses using this tuple structure.

created 14 March 2020 revised 25-26 March 2020
For more information, please contact Henry M. Walker at walker@cs.grinnell.edu.