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.
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.
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.
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
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
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"
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]
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",""]
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"]
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 []
[[]]
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.
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
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
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
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' " "
[]
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 4-8 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.
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.