CS 154 Lab 4: More Exercises, Some Recursion

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):

A traditional programming challenge is to write a function that compares two strings to find their longest common prefix: a prefix is some part of a string occurring at the front: so "foo" is a prefix of "foobar". A common prefix of two strings is a prefix they both share: the strings "elephant" and "elevator" share the common prefixes "ele", "el", "e" and even the empty string "" ... but of course the longest common prefix, namely "ele", is in some sense the most significant of these. (By the way, mixing elephants and elevators? Not especially recommended …)

Anyway, you should write a function lcp that takes two strings and returns the string which is their longest common prefix—note that since the empty string is always possible (if a little disappointing) the function is at least well-defined and should always return a string.
Example:
Hugs> lcp "bogus" "bodacious" "bo" Hugs> lcp "promethea" "promontory" "prom"
Now write an extended version of the longest common prefix that will apply to a whole list of arguments, returning the longest prefix which is common to all the (string) elements of the list. You can call it lcps using the Haskell convention (English, too!) of adding an "s" to get a plural form. (You can pronounce it "el-cee-pees", but no connection to bovine bodily functions should be inferred ()).
Example:
Hugs> lcps ["bonnie", "bovine", "bowlers", "borrowed"] "bo" Hugs> lcps ["gargantuan", "garrulous", "garfish"] "gar"
Of course, it seems only fair to also define the longest common suffix function as well. The intended meaning should be clear: the lcs of two strings is a string that is a suffix occurring at the end of each word.

(Hint: go through the looking glass, do your thing, then come back through the looking glass again.)

Example:
Hugs> lcs "Elsie" "Bessie" "sie"
And, finally, you should define the lcss function, by obvious analogy with lcps. (This final one is actually the motivating example that occurred to me while grabbing lunch after class the other day.)
Example:
Hugs> lcss ["dos", "Doritos", "Locos", "Tacos"] "os"
Write a function that will return a list of all the even-numbered elements of a list; in other words, every other element, starting with the "zero-th" one. (In Haskell, as in most computer languages, we number the elements of "collections" like lists starting from index 0 (zero) and work up from there. So the indices of the elements in the example below are 'a' at index 0, 'b' at index 1, 'c' at index '2', 'd' at index 3, etc.)
Your function should be of this type: evens :: [a] -> [a].
Example:
Hugs> evens "abcdefg" "aceg"
(This might make good use of nested patterns such as (x:y:zs).)
In lecture we saw the until function from the Prelude that applied a function to some initial "seed" value repeatedly, until it produced a result that met some predicate; write a while function of the same type, but which returns the first value that "breaks" the rule.
(Just to be clear, the idea here is that while p f x means that we want to "keep f-ing x while it is still p" or, less crudely, that we want to "keep applying f to (successive results of) x while the value of p x is still True", then return the first value for which this test fails. Note that, just as with until in lecture, there is always the possibility of "f-ing" zero times, since x may already fail the p test (in the case of while) or pass the p test (in the case of until.)

Example:
Hugs> while (<100) (*2) 1 -- while the answer is less than 100, 128 -- keep doubling it, starting at 1; -- answer is the first result *not* less than 100
Hmmm, what were those intermediate values generated by 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.
Example:
Hugs> during (<100) (*2) 1 [1,2,4,8,16,32,64]
Write a function called perms: given a list xs, it should produce the list of all permutations of the elements in xs, i.e., a list of all lists which are a re-ordering of the elements in xs. If there are duplicate elements, they should be considered effectively different (just like in the power function): in other words, what matters is that you permute in some sense the positions in the list, not the specific elements (although of course your answer lists will contain the original elements).
perms :: [a] -> [[a]] Hugs> perms "abc" ["abc","bac","bca","acb","cab","cba"] Hugs> perms "aba" ["aba","baa","baa","aab","aab","aba"] -- note treatment of duplicates

(This one is pretty hard: it's sort of like the perms example from the last lab, but maybe a little tougher. Think about writing one main function, perms, and one "helper function" to insert items in all possible positions in a list. You might want to remember the Prelude function concat :: [[a]] -> [a], which combines out one level of list. And remember to keep track of your list levels in general: types are handy for this, but the compiler will oh-so-helpfully let you know if you get it wrong .)