Lab #1: Haskell Orientation and Exploration

Assigned: Wednesday 26 Jan 2005
Due: Wednesday 2 February 2005

Our first lab this semester is intended to help familiarize you with the logistics of using Haskell (via the Hugs interpreter) and to provide you with a number of shorter exercises involving functions and simple types. These two goals are realized in separate sections below: the first section is geared towards inspiring some open-ended investigation and should be followed up with short replies phrased in English, whereas the second lists specific questions that are best answered with short programs or expressions written in Haskell. All your answers should be combined in a text file ready for demonstration in the lab on the due date.

Make use of this lab to try out the programming environment using the Hugs interpreter, Wordpad and the various documents available from the new links page.

The new CS 454 Haskell links page

While documentation can be helpful, your best approach to getting started is to watch the demonstrations in lecture and then experiment on your own. Get in the habit of trying out your ideas interactively, as this is the best way to learn Haskell and FP.

A. Short questions to inspire investigation

  1. What is the difference between the (infix, arithmetic) operators "**", "^^" and "^" in Haskell?

    (hint: consider typings, but also try a few sample arguments; use the ":t" command to find out the type of an expression, and rememebr to put infix operators in parenthese for this purpose)

  2. What is the associativity of these operators in Haskell (i.e., either left-associative or right-associative)?

  3. What is the meaning of the "const" function in Haskell (i.e., what does it compute, based on its arguments)?

    (hint: try applying it to two successive arguments, as in "const 3 5")

  4. What is the definition (i.e., program text) of the "sum" operator in Haskell? How about the "maximum" operator?
    (hint: look in the library file "Prelude.hs": you can do this by having only the Prelude loaded and then typing the ":e" command)

  5. Using the Hugs reduction count feature (with command ":s +s"), see if you can determine a rule for how many reductions are performed when an integer arithmetic expression with n operators is evaluated. (Express your answer as a function of n.) For example, the expression "2 + 3 * 5" has two operators, whereas "17 * (12 - 4) + 6 / 3" has 4 operators.

    Does the rule change if the literal values are of type Float rather than integers? (Use literals like "4.5" to get Float values.)

  6. Where in the Haskell libraries is the list of all primes defined (under that name) and what is its definition? (This is really more an exercise in seraching the libraries: you might either try some of the documentation tools or search "by hand" through the libraries in the "C:\Haskell\Hugs" directory.)

  7. Name three identifiers that you cannot use in Haskell programs because they are reserved. (Really an exercise in finding the right part of the documentation files.)

B. Short programming exercises

Our next few labs will consist, like this section, of several relatively simple exercises. Although the solutions to the exercises will be fairly short (compared to, say, Java), they will still take some time to write, as you are learning both a new language and a new style (or "paradigm). Here are some tips and strategies for developing code:

Note: For the exercises involving lists, try to find pre-defined functions from which you can build a solution. We haven't yet seen how to define functions on lists "explicitly", by taking apart and putting together the lists, item by item. All the functions requested here can be written more simply by just "gluing" together other functions.

  1. The following function twice applies its function argument twice to a value:
    twice f x = f (f x)
    Show how twice can be defined without reference to a second argument (i.e., without the "x" or any other variable in its place).

  2. Consider the following functions defined using twice; for each one, describe what it does in plain English. Also give an example application and result for each (not just "<<function>>").
    nice = twice twice
    slice = twice (twice twice)
    dice = (twice twice) twice

  3. Give alternate, simpler definitions for each of the following (they should be equivalent to the ones given here):
    foo = twice (take 10)
    bar = twice (drop 10)

  4. Write a function stutter which will take a number n and a string s and return a new string which consists of n copies of s joined together. You will want to use the concat function (defined in the prelude) which joins together a list of strings as follows:
    > concat ["this", "is", "a", "test"]
    "thisisatest"

    Your function should behave as follows:

    > stutter 3 "foobar"
    "foobarfoobarfoobar"

  5. Write another function stammer which will take a number n and a string s and return a new string which consists of all the characters from s, in order, but with each one repeated n times. You may want to use the map function (as defined in the prelude and demo'ed in lecture). Remember also that a string is really just a list of characters.

    Your function should behave as follows:

    > stammer 3 "foobar"
    "fffoooooobbbaaarrr"

  6. It's often said that two wrongs don't make a right. On the other hand, sometimes two applications of a function get us right back where we started from (for example, two applications of the logical "not" is just the identity on booleans). Explain how the following functions differ, and which one is really just an identity function:
    flop = twice flip
    flap = flip flip

    Hint: once again, the types will be helpful.

  7. Define a function count which, when given a predicate (i.e., a boolean-valued function) and a list, will count how many items in the list satisfy the predicate. For example, we should have:
    > count even [1..10]
    5
    > count (>8) [1..10]
    2

    (Hint: I showed this briefly in class the other day, before the WinHugs environment melted down on me.)

  8. The two prelude functions words and unwords can be used to break a string into a list of words and to combine a list of words back into a single string, respectively. For what arguments, then, will the following function not be (quite) the identity function?
    almostID = unwords . words