For this lab we will continue with some fairly simple function definitions, but now possibly including definition by recursion, typically using patterns over lists. Of course, the functions described below can be written many ways: I would encourage you to think about each one as being written either in terms of "prior" functions (e.g., in the Prelude or some library) or in terms of explicit recursion. (It wouldn't be a bad idea to write both when you can!)
Special note: it is, however, part of point of the assignment (as it is with all our labs) that you write the functions yourself, at least at some level (i.e., allowing for some use of Prelude, etc.). In other words, you are supposed to be getting practice at writing, not practice at finding things someone else already defined somewhere on the web ☺ .
So, try to write each of these functions (let's do them all this time, even though a few are a bit more difficult):
count :: (a -> Bool) -> [a] -> Intthat will count how many elements of a list meet a certain predicate. (You might end up returning a
Integerresult, depending on how you do this one.)
Hugs> count even [1..20] 10
untilfunction from the Prelude that applied a function to some initial "seed" value repeatedly, until it produced a result that met some predicate; write a
whilefunction of the same type, but which returns the first value that "breaks" the rule.
Hugs> while (<100) (*2) 1 128
while, anyway? Write a function
during :: (a -> Bool) -> (a -> a) -> a -> [a]that will return a list of all the values "generated" during a run of
while. For this one, rather than return the value that "broke" the rule, let's only include the ones that meet it.
Hugs> during (<100) (*2) 1 [1,2,4,8,16,32,64]
elemfunction from the Prelude that allowed us to treat lists roughly like sets; write a function
subset :: Eq a => [a] -> [a] -> Boolwhich will tell if its first list argument is a subset of the second, i.e., if all the members of the first list are also members of the second.
power :: [a] -> [[a]]which will return a list of lists such that (roughly) every list that is a sublist of the original argument will be an element of the powerlist. What about duplication and order, which are relevant for lists, but not for sets? Well, let's not worry too much about order, but if there are distinct-but-equal occurrences of elements in the argument list, it's easiest to treat them as distinct for the result.
(Remember, the order of elements in your results might differ from these examples!)
Hugs> power "abc" ["","c","b","bc","a","ac","ab","abc"] Hugs> power [2,2,2] [,,,[2,2],,[2,2],[2,2],[2,2,2]]
evens :: [a] -> [a].
(This might make good use of patterns we haven't seen as of Friday's lecture: if you have trouble with it, just try again after Monday's lecture.)
Hugs> evens "abcdefg" "aceg"
rand break a list of values into "segments", where each of the successive pairs of list elements bear the relation to each other. In other words, the segments "break" the list between elements where the relation fails. This will allow us, for example, to break up a list into increasing segments (or non-decreasing ones). Your function should be realized as
segment :: (a -> a -> Bool) -> [a] -> [[a]]and should work as shown below. (This one is pretty hard!)
(What to return for an empty list as argument? Hmm, perhaps an empty list, but maybe a list containing the empty list ... which makes more sense? How would you argue for one or the other?)
Hugs> segment (<) [1,2,3,0,1,2,2,4,6,8] [[1,2,3],[0,1,2],[2,4,6,8]] Hugs> segment (<=) [1,2,3,0,1,2,2,4,6,8] [[1,2,3],[0,1,2,2,4,6,8]]
split :: [a] -> ([a],[a]). If there are excess elements, you should put the extra one in the second list, but do preserve the original order of elements.
Hugs> split "abcdefg" ("abc","defg")
riffle :: ([a],[a]) -> [a]. If either argument list is too long, just leave its elements at the end of the result.
Hugs> riffle ("abc","wxyzpqr") "awbxcyzpqr"
The last couple of functions can be combined to give a "card shuffler": just repeatedly split and riffle the "cards" (really, any list will do, e.g., numbers). It can be fun to experiment and see, for example, how many such "perfect shuffle" are required to retrun a list to its original order.