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
share the common prefixes
"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.
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
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 ()).
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
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.)
Hugs> lcs "Elsie" "Bessie" "sie"
And, finally, you should define the
lcss function, by obvious analogy
lcps. (This final one is actually the motivating example that occurred
to me while grabbing lunch after class the other day.)
Hugs> lcss ["dos", "Doritos", "Locos", "Tacos"] "os"
evens :: [a] -> [a].
(This might make good use of nested patterns such as
Hugs> evens "abcdefg" "aceg"
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.
(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
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
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]
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
powerfunction): 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,
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