Machine Problem: Folds and HOFs

Overview

The goal for this assignment is to get more comfortable with using folds in place of direct recursion, and with higher order functions. Both techniques are essential in functional programming.

Working on the assignment

All your code for this assignment should go into a file named "MP2.hs" within the "src" directory in your repository. Continue to directly load your file into a GHCi session for testing.

Exercises

In addition to any functions listed for each exercise, you may always use the following:

Warm-up exercises (1 point each). Implement each of the following functions using either a left or right fold. For these functions, use either function composition or a lambda expression to define the function used as the argument to fold (e.g., "foldr (f1 . f2) v" or "foldr (\x ys -> ...) v"). Also, endeavor to use point-free style.

  1. any' :: (a -> Bool) -> [a] -> Bool

    Returns true if the predicate returns true for any of the values in a list.

    Examples:

    > any' even [1..10]
    True
    
    > any' even [1,3..9]
    False
    
    > any' even []
    False
    
  2. all' :: (a -> Bool) -> [a] -> Bool

    Returns true if the predicate returns true for all of the values in a list.

    Examples:

    > all' even [1..10]
    False
    
    > all' even [2,4..10]
    True
    
    > all' even []
    True
    
  3. compose :: [a -> a] -> (a -> a)

    Returns the function created by composing all the functions in the given list.

    Examples:

    > compose [(*5), (/10), (+1)] 9
    5.0
    
    > compose [("hello, " ++), reverse, drop 1] "Michael"
    "hello, leahci"
    
  4. cycle' :: [a] -> [a]

    Returns an infinite list of the provided list, repeated.

    Examples:

    > take 10 $ cycle' [1..3]
    [1,2,3,1,2,3,1,2,3,1]
    
  5. scanr' :: (a -> b -> b) -> b -> [a] -> [b]

    Returns the list of values as they would be produced by a corresponding right fold.

    Examples:

    > scanr' (+) 0 [1..10]
    [55,54,52,49,45,40,34,27,19,10,0]
    
    > scanr' (:) [] "hello"
    ["hello","ello","llo","lo","o",""]
    
  6. scanl' :: (b -> a -> b) -> b -> [a] -> [b]

    Returns the list of values as they would be produced by a corresponding left fold.

    Examples:

    > scanl' (+) 0 [1..10]
    [0,1,3,6,10,15,21,28,36,45,55]
    
    > scanl' (flip (:)) [] "hello"
    ["","h","eh","leh","lleh","olleh"]
    
  7. inits :: [a] -> [[a]]

    Returns all successive starting sublists of the given list, starting with the empty list.

    Examples:

    > inits "hello"
    ["","h","he","hel","hell","hello"]
    
    > inits []
    [[]]
    
  8. tails :: [a] -> [[a]]

    Returns all successive trailing sublists of the given list, ending with the empty list.

    Examples:

    > tails "hello"
    ["hello","ello","llo","lo","o",""]
    
    > tails []
    [[]]
    

Trickier exercises (2 points each). Again, implement the following functions using either a left or right fold. For these functions, it's likely that you'll need to pass a tuple into the fold, and extract a value from the (tuple) returned by the fold to return as a result. Endeavor to use point-free style.

  1. minmax :: (Ord a) => [a] -> (a,a)

    Returns the minimum and maximum (as a tuple) of a non-empty list.

    Examples:

    > minmax [5,2,1,3,8,4]
    (1,8)
    
    > minmax [3]
    (3,3)
    

    Permitted functions: min, max

  2. gap :: (Eq a) => a -> a -> [a] -> Maybe Int

    Returns the integer distance between first appearance of two elements in a list.

    Examples:

    > gap 3 8 [1..10]
    Just 5
    
    > gap 8 3 [1..10]
    Nothing
    
    > gap 'h' 'l' "hello"
    Just 2
    
    > gap 'h' 'z' "hello"
    Nothing
    
  3. evalExpr :: String -> Int

    Evaluates a string containing a simple arithmetic expression using only single digit operands and (binary) + and - operators.

    Examples:

    > evalExpr "1"
    1
    
    > evalExpr ""
    0
    
    > evalExpr "1+2+5"
    8
    
    > evalExpr "9-5+3-8"
    -1
    
  4. words' :: String -> [String]

    Returns the space-delineated words found in a string as a list.

    Examples:

    > words' "a b c d"
    ["a","b","c","d"]
    
    > words' "   hello    how are you? "
    ["hello","how","are","you?"]
    
    > words' "   "
    []
    
  5. dropWhile' :: (a -> Bool) -> [a] -> [a]

    Removes elements from the beginning of a list that satisfy the predicate.

    Examples:

    > dropWhile' even [2,4,1,5,6,8]
    [1,5,6,8]
    
    > dropWhile' even []
    []
    
    > dropWhile' ((<= 3) . length) $ words' "I am fond of cake"
    ["fond","of","cake"]
    

MP1, redux (2 points each).: Complete exercises 1-6 from MP1 again, but this time using either a left or right fold. For the vigenere exercise, you may additionally choose to use the cycle function. Endeavor to use point-free style.

Submission

To submit your work, be sure your "MP2.hs" file is added to your repository, then commit all your changes and push your work to our shared BitBucket repository. We'll go over this in class.