HW 1 - List Processing, Recursion and working with Higher-order Functions

This is the first homework assignment for CIS 5520. The first two problems provide practice with the basic built-in data structures of Haskell (lists, tuples and maybes) as well as recursion and pattern matching. The second two problems provide practice with higher-order functions in Haskell. The last problem is a design exercise that puts everything together. You'll need to look at the file Kata.hs for this problem.

If you have not read the Basics module, you should do that before attempting the first two problems. The homework assignment also draws from the HigherOrder module, which is necessary for the second two problems.

Create your own private repo for the assignment by following these instructions. This page is a "literate" Haskell program, meaning that explanation is interspersed with actual Haskell code. To complete your assignment, edit HW01.hs and Kata.hs in the hw01 repository that you created and submit it through Gradescope.

When you work with this file, you can use a terminal to load the project into ghci with the command stack ghci. That will give you interactive access to all definitions in this module, as well as a function, called main, that you can use to run all of the test cases. (For this command, make sure that you are in the hw01 subdirectory in the terminal.)

> module HW01 where
> import Prelude hiding (reverse, concat, zip, (++), takeWhile, all)

The Prelude line imports all except for the functions listed (which you will write). The module Prelude is special in that it is always imported by default, so the the point of this line is not to import more functions, but rather to exclude a few functions. (Haskell does not allow functions to be redefined in the same module.)

> --------------------------------------------------------------------------------
> -- Problem (Good Style)
> --------------------------------------------------------------------------------

All of the following Haskell code does what it is supposed to do (i.e. the tests pass), but it is difficult to read. Rewrite the following expressions so that they exactly follow the style guide. Be careful: the style guide includes quite a few rules, and we've broken most of them in what follows! (You don't need to rewrite the test following each part, but you do need to make sure that you don't break the code as you refactor it!)

NOTE: Do not change the name of any of the top level declarations below, even if you think that they aren't very good (they aren't). We use automatic testing to ensure that you do not change the meaning of these functions when you rewrite them. On the other hand, local variables (such as function parameters and those bound by let and where) can and should be renamed.

NOTE: If you have set up VSCode and hlint correctly, your IDE should give you a few hints on how to improve these functions. But, it won't tell you everything.

> -- >>> abc True False True
> -- True
> -- >>> abc True False False
> -- False
> -- >>> abc False True True
> -- False
> abc x y z =
>   if x then if y then True else
>        if (x && z) then True else False
>   else False

> -- >>> arithmetic ((1,2),3) ((4,5),6)
> -- (-3,6,-3)
> -- >>> arithmetic ((3,2),1) ((4,5),6)
> -- (7,-14,7)
> arithmetic :: ((Int, Int), Int) -> ((Int,Int), Int) -> (Int, Int, Int)
> arithmetic x1 x2 =
>      let a = fst (fst x1) in
>      let b = snd (fst x1) in
>      let c = snd x1 in
>      let d = fst (fst x2) in
>      let e = snd (fst x2) in
>      let f = snd x2
>        in
>        ((((((b*f) - (c*e)), ((c*
>        d) - (a*f)
>        ), ((a*e)-(b*d))))))

> -- >>> reverse [3,2,1] 
> -- [1,2,3]
> reverse l  = reverseAux l [] where
>   reverseAux l acc =
>     if null l then acc
>        else reverseAux (tail l) (head l : acc)

> -- >>> zip "abc" [True,False,True]
> -- [('a',True),('b',False),('c',True)]
> -- >>> zip [1,2] "a"
> -- [(1,'a')]
> zip xs ys = g 0 xs ys where
>   g n xs ys = if n == length xs || n == length ys then [] else
>           (xs !! n, ys !! n) : g (n + 1) xs ys

> --------------------------------------------------------------------------------
> -- Problem (List recursion)
> --------------------------------------------------------------------------------

Now define, debug, and test the following functions that work with lists. Some of these functions are part of the Haskell standard Prelude or standard libraries like Data.List. Their solutions are readily available online or produceable by AI. You should not google for this code: instead, implement it yourself!

Do not use any library functions in this problem. These include all functions from the Prelude or from Data.List that take arguments or returns a result with a list type. Note that (:) and [] are data constructors for the list type, not functions, so you are free to use them. Please also avoid list comprehension syntax (if you have seen that before), as it actually de-sugars into list library functions!

> -- | The 'minimumMaybe` function computes the mininum value of a
> -- nonempty list. If the list is empty, it returns Nothing.
> --
> -- >>> minimumMaybe [2,1,3]
> -- Just 1
> -- >>> minimumMaybe []
> -- Nothing
> minimumMaybe = undefined

> -- | The 'startsWith' function takes two strings and returns 'True'
> -- iff the first is a prefix of the second.
> --
> -- >>> "Hello" `startsWith` "Hello World!"
> -- True
> -- >>> "World" `startsWith` "Hello World!"
> -- False
> -- >>> "Helo" `startsWith` "Hello World!"
> -- False
> startsWith :: String -> String -> Bool
> startsWith = undefined

> -- | The 'isSubsequenceOf' function takes two strings and returns 'True'
> -- iff the first is contained within the second.
> --

> -- >>> "Hello" `isSubsequenceOf` "Hello World!"
> -- True
> -- >>> "World" `isSubsequenceOf` "Hello World!"
> -- True
> -- >>> "Helo" `isSubsequenceOf` "Hello World!"
> -- True
> -- >>> "Wello" `isSubsequenceOf` "Hello World!"
> -- False

> isSubsequenceOf :: String -> String -> Bool
> isSubsequenceOf [] _ = True
> isSubsequenceOf _ [] = False
> isSubsequenceOf (x:xs) (y:ys) = x == y && isSubsequenceOf xs ys
>   || isSubsequenceOf (x:xs) ys

> -- | The 'transpose' function transposes the rows and columns of its argument.
> -- If the inner lists are not all the same length, then the extra elements
> -- are ignored.
> -- You may assume that the input list is non-empty, and that each of the sublists
> -- is also non-empty. 
> -- (i.e. we won't test your code on `transpose []` or `transpose [[]]`)
> -- Note, this function should *not* have the same behavior as the library version
> -- of transpose (i.e. the version of transpose from Data.List), which retains
> -- extra elements in the output.
> -- >>> transpose [[1,2,3],[4,5,6]]
> -- [[1,4],[2,5],[3,6]]
> -- >>> transpose [[3,4,5]]
> -- [[3],[4],[5]]
> -- >>> transpose [[1,2],[3,4,5]]
> -- [[1,3],[2,4]]

> -- (WARNING: this one is tricky!)
> transpose :: [[a]] -> [[a]]
> transpose = undefined

> -- | The 'countSub' function returns the number of (potentially overlapping)
> -- occurrences of a substring sub found in a string.
> --
> -- >>> countSub "aa" "aaa"
> -- 2
> -- >>> countSub "" "aaac"
> -- 5

Hint: You can use other functions that you have defined in this file.

> countSub :: String -> String -> Int
> countSub = undefined

> --------------------------------------------------------------------------------
> -- Problem (Defining higher-order functions)
> --------------------------------------------------------------------------------

Define, debug and test the following operations that take higher-order functions as arguments. (For extra practice, you may define these operations using foldr, but that is not required.) Other than foldr, you may not use any list library functions for this problem.

> -- | `takeWhile`, applied to a predicate `p` and a list `xs`,
> -- returns the longest prefix (possibly empty) of `xs` of elements
> -- that satisfy `p`.
> --
> -- >>> takeWhile (< 3) [1,2,3,4,1,2,3,4]
> -- [1,2]
> -- >>> takeWhile (< 9) [1,2,3]
> -- [1,2,3]
> -- >>> takeWhile (< 0) [1,2,3]
> -- []

> takeWhile :: (a -> Bool) -> [a] -> [a]
> takeWhile = undefined

> -- | `find pred lst` returns the first element of the list that
> -- satisfies the predicate. Because no element may do so, the
> -- answer is returned in a `Maybe`.
> --
> -- >>> find odd [0,2,3,4]
> -- Just 3
> -- >>> find odd [0,2,4,6]
> -- Nothing

> find :: (a -> Bool) -> [a] -> Maybe a
> find = undefined

> -- | `all pred lst` returns `False` if any element of `lst`
> -- fails to satisfy `pred` and `True` otherwise.
> --
> -- >>> all odd [1,2,3]
> -- False

> all  :: (a -> Bool) -> [a] -> Bool
> all = undefined

> -- | `map2 f xs ys` returns the list obtained by applying `f` to
> -- to each pair of corresponding elements of `xs` and `ys`. If
> -- one list is longer than the other, then the extra elements
> -- are ignored.
> -- i.e.
> --   map2 f [x1, x2, ..., xn] [y1, y2, ..., yn, yn+1]
> --        returns [f x1 y1, f x2 y2, ..., f xn yn]
> --
> -- >>> map2 (+) [1,2] [3,4]
> -- [4,6]
> --
> -- NOTE: `map2` is called `zipWith` in the Prelude

> map2 :: (a -> b -> c) -> [a] -> [b] -> [c]
> map2 = undefined

> -- | Apply a partial function to all the elements of the list,
> -- keeping only valid outputs.
> --
> -- >>> mapMaybe root [0.0, -1.0, 4.0]
> -- [0.0,2.0]
> --
> -- (where `root` is defined below.)
> mapMaybe :: (a -> Maybe b) -> [a] -> [b]
> mapMaybe = undefined

> root :: Double -> Maybe Double
> root d = if d < 0.0 then Nothing else Just $ sqrt d

> --------------------------------------------------------------------------------
> -- Problem (map and foldr practice for lists)
> --------------------------------------------------------------------------------

For the next group of functions, you are not allowed to use explicit recursion in your solutions. Instead, you must define them using one of the higher-order functions map, foldr or para (see below). These are the only list library functions that you may use on this problem. If you need any additional helper functions you may define them, but any helper functions should also use map, foldr or para instead of explicit recursion.

> -- | The concatenation of all of the elements of a list of lists
> --
> -- >>> concat [[1,2,3],[4,5,6],[7,8,9]]
> -- [1,2,3,4,5,6,7,8,9]
> --

NOTE: remember you cannot use any list functions from the Prelude or Data.List for this problem, even for use as a helper function. Instead, define it yourself.

> concat :: [[a]] -> [a]
> concat = undefined

> -- | The 'startsWithHO' function takes two strings and returns 'True'
> -- iff the first is a prefix of the second. This is the same as `startsWith` above
> -- except this time you need to use `foldr` to define it.
> --
> -- >>> "Hello" `startsWithHO` "Hello World!"
> -- True
> --
> -- >>> "Hello" `startsWithHO` "Wello Horld!"
> -- False

NOTE: use foldr for this one, but it is tricky! (Hint: the value returned by foldr can itself be a function.)

> startsWithHO :: String -> String -> Bool
> startsWithHO = undefined

> -- INTERLUDE: para

Now consider a variant of foldr called para. In the case of cons, foldr provides access to the head of the list and the result of the fold over the tail of the list. The para function should do the same, but should also provide access to the tail of the list (before it has been processed).

> -- | foldr variant that provides access to each tail of the list
> para :: (a -> [a] -> b -> b) -> b -> [a] -> b
> para _ b [] = b
> para f b (x:xs) = f x xs (para f b xs)

For example, consider the tails function.

> -- | The 'tails' function calculates all suffixes of a give list and returns them
> -- in decreasing order of length. For example:
> --
> -- >>> tails "abc"
> -- ["abc","bc","c",""]
> --
> tails :: [a] -> [[a]]
> tails []     = [[]]
> tails (x:xs) = (x:xs) : tails xs

It is a natural fit to implement tails using para. See if you can redefine the function above so that the test cases still pass.

> tails' = undefined

> -- | The 'countSubHO' function returns the number of (potentially overlapping)
> -- occurrences of a substring sub found in a string.
> --
> -- >>> countSubHO "aa" "aaa"
> -- 2
> -- >>> countSubHO "" "aaac"
> -- 5

(You may use the para and startsWithHO functions in countSubHO.)

> countSubHO  :: String -> String -> Int
> countSubHO = undefined

CIS 5520: Advanced Programming

Fall 2024

HW 1 - List Processing, Recursion and working with Higher-order Functions