CS 154 Lab 2: Some more simple functions, emphasis on lists

Here are a few more exercises in Haskell, focussing now on functions that involve lists in their arguments or results: you should be able to solve them with what you've learned in lecture and from the textbook ... but be sure to look for useful Prelude functions to help! (See below.)

  1. Define a Haskell function count which will tell you how many elements of a list meet some given criterion. For example (here pal is a simpler version of palindrome):
    Main> count pal ["bob", "sam", "otto", "fred", "eve"]
    Main> count isAlpha "l33t"
    Main> count (all isAlpha) ["bob", "sam", "l33t", "foo37"]

    PS: if you want to actually use functions like pal for testing, you'll need to define it. Here's a workable definition of pal, a less fussy version of the palindrome function we saw early on in class (but quicker to type in); just add this to your file of definitions:

    pal str = str == reverse str
    (This version of pal doesn't bother with spaces, punctuation and capitalization issues.)

    To get access to the isAlpha function and other character-oriented tools, make sure you define a name for your module and put an import at the top, by adding these lines at the top of your file:

    module Lab2 where
    import Char
    You would add this to the very top of your script file; use a name like "Lab2" for a file named "Lab2.hs" (in general, the name of the module, like "Lab2", should be capitalized, a single word, and use only letters and numbers (no spaces!). The corresponding file should have the exact same name but with ".hs" at the end, as in "Lab2.hs").

    (Once you have the import Char line in your file, you’ll have access to all the definitions of that module in your Haskell window when you load the file.)

    (Hint: consider using the Prelude function filter!)

  2. Write a function title which will take a string as argument and return a new string with all initial letters uppercase and all non-initial letters lowercase:
    > title "now is THE time, For aLL good men."
    "Now Is The Time, For All Good Men."
    You should leave punctuation unchanged, but you can eliminate redundant word spacing (Hint: recall the words, head and tail functions; try working in two stages). You’ll also want to look at the toUpper and toLower functions from the Char module.
  3. Define a function longest which returns all the longest words (as defined by the words function, see below) in its String argument. In other words, all those words which have the maximum length of any word in the original text. For example, we should have:

    longest "the biggest words here have seven letters"
    	==> ["biggest", "letters"]
    since each of these words (“biggest” and “longest”) has 7 letters.

    Hint: this one is probably most easily solved using a series of “sub-definitions”. The easiest way to do this might be to set up a specific example text as a definition in a file, then work on it interactively, developing new pieces of the definition as you go, so that your file looks something like this:

    text = "this is some sample text"
    y = ... text ...
    f x = ...
    z = .... f text ...

  4. The elem function from the Prelude allows us to treat lists roughly like mathematical sets: specifically, it allows us to test whether the first argument is an element (or member) of the second argument (which must be a list):

    Hugs> elem 3 [1..5]
    Hugs> elem 'z' "hello"

    Write a function subset :: Eq a => [a] -> [a] -> Bool which 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. (Hint: use elem!)


    Hugs> subset "ABBA" "ABC"
    Hugs> subset "97301 USA" ['0'..'9']

  5. In a related vein, we might want to generate the "powerset" of a list (maybe the “powerlist”?). Write a function power :: [a] -> [[a]] which will return a list of lists such that every list that is a sublist of the original argument will be an element of the result list. “But what about duplication and order, which are relevant for lists, but not for sets?” you might ask. If there are distinct-but-equal occurrences of elements in the argument list, it's easiest to treat them as distinct for the result. As for order, just preserve the same order as in the original list, if possible.

    One way to think of it is that each member of the result comes from the original list by striking one or more (perhaps even all) of the members of the original list: do this in every possible way and you have the result. Of course, it's easier to build the list up to get the same result than to take things out ... (see the hint implicit in the formatted example below).

    Here are some examples—there's a big hint in how the first one is formatted!


    Hugs> power "abc"
     [ "",  "c",  "b",  "bc",
      "a", "ac", "ab", "abc"]
    Hugs> power [2,2,2]
    (Remember, the order of elements in your results might differ from these examples!)

Be prepared to tell the types of your functions (which you can easily get by asking your Haskell system (Hugs, WinHugs or GHCi). You should also be able to describe their types in words. Which one(s) might work on numbers, which on text, which on both? Why? You should be able to show an example or two that illustrate these possibilities.

Some useful Prelude functions

Just for reference, here are some explanations and examples of a few useful functions from the Prelude and from the Char module.

			A higher-order function which takes a predicate 
			argument (i.e., a boolean-valued function) and a list, 
			and which returns a list of all elements for which the
			predicate is True. (More specifically, it respects order
			and repetition, so in essence it "deletes" only those
			elements for which the predicate returns False.)
			filter :: (a -> Bool) -> [a] -> [a]
			So in the application "filter p xs", we have 
			p :: a -> Bool a predicate and xs :: [a] a list; the 
			result has elements from xs in the same order, with
			repetitions, but without any elements for which p 
			returns False.
				filter even [1, 2, 3, 4, 4, 3, 2, 1]
					==>  [2, 4, 4, 2]

			A higher-order predicate which tests if its predicate 
			argument (i.e., a boolean-valued function) is true of all 
			the elements in a list.
			all :: (a -> Bool) -> [a] -> Bool
			So in the application "all p xs", we have p :: a -> Bool
			a predicate and xs :: [a] a list; the result tells if 
			all the elements of xs return True for p.
				all even [2,4..8]
					==>  all even [2, 4, 6, 8]
					==>  True

			A predicate which tells of a character whether or not it
			is an alphabetic character (i.e., whether or not it is a
			isAlpha :: Char -> Bool
				map isAlpha "x #"
					==>  [isAlpha 'x', isAlpha ' ', isAlpha '#']
					==>  [True, False, False]

			A predicate which tells of a character whether or not it
			is a lowercase alphabetic letter.
			isLower :: Char -> Bool
				map isLower "aA@"
					==>  [isAlpha 'a', isAlpha 'A', isAlpha '@']
					==>  [True, False, False]


			A function which pairs up the elements of two lists into
			a list of pairs. (Think of a zipper being pulled closed.)
			If one of the lists is too short, then its elements are 
			"cut off" in the result.
			zip :: [a] -> [b] -> [(a,b)]
				zip [1..5] "abc"
					==>  [(1,'a'), (2,'b'), (3,'c')]

			A function which breaks a String up into a list of 
			Strings ("words" from the original argument) by 
			breaking at (and dropping) runs of whitespace.
			words :: String -> [String]
				words "This is a test"
					==>  ["This", "is", "a", "test"]

			A function which applies its function argument (say f)
			to every element of its list argument in order to
			produce a list of results.
			map :: (a -> b) -> [a] -> [b]
				map isLower "aA@"
					==>  [isAlpha 'a', isAlpha 'A', isAlpha '@']
					==>  [True, False, False]

			A function on lists of numbers which returns the 
			maximum element of the list.
			maximum :: Ord a => [a] -> a
			           {don't worry too much about that Ord business; it means
			            roughly that the elements of the list are, in Java's 
			            terms, Comparable}
				maximum (words "We who are about to fry salute you")
					==>  maximum ["We","who","are","about","to","fry","salute","you"]
					==>  "you"
					     {exercise: what ordering is being used here?}

	takeWhile, dropWhile
			Two functions which take or drop items from the front of a list, but
			only while a given predicate is True. In other words,
			this function takes one predicate argument and one 
			list argument, and returns either a prefix or suffix of the list such
			that every element in the prefix meets the test of 
			the predicate (for takeWhile) or a suffix whiose first element specifically
			fails the test.
			takeWhile :: (a -> Bool) -> [a] -> [a]
			dropWhile :: (a -> Bool) -> [a] -> [a]

				takeWhile (<5) [1..]
					==>  [1,2,3,4]
				dropWhile (<5) [1..10]
					==>  [5,6,7,8,9,10]