Exercises using Hugs

These are a series of small programming exercises using Haskell. There are several Haskell implementations available, but I suggest you use Hugs for these problems. Hugs is a fast interactive interpreter with good error diagnostics.

Contents

Running Hugs

 To run Hugs give the command 
hugs
which starts up the interpreter. In response to the question mark prompt you can type an expression, and hugs will evaluate it.

When you want to define your own functions, you will need to place your definitions in a file. Do so by giving hugs the command 

:edit Hugs.hs
which starts editing the file Hugs.hs. Insert a definition (for example the sq function) and save the edit. When you quit the editor you will come back to hugs. Now you can load your file (make the definitions available to hugs) by giving hugs the command 
 :load Hugs.hs
From now on you can use your new functions in expressions you give hugs to evaluate.

In future you can edit your definitions just with the command 

:edit
and they will be automatically reloaded after editing.

To see the list of commands available, type 

:?
A particularly useful command is 
:find

Sorting

 Your first problem is to define a sorting function: one which takes a list to be sorted as an argument, and returns a sorted list as its result. Use the Quicksort algorithm: to sort a list, Call your function mySort (to avoid a name clash with the standard sorting function).

You will need to write a recursive function, but you should be able to use filter at some point. Hint: try evaluating 

map (<5) [1..10]
to get some ideas.

Make sure your sort function works for lists with duplicate elements! mySort [1,1,1] should be [1,1,1], not [1]!

Can you define a sort function which can be used to sort any kind of data into any order? For example, strings into reverse alphabetic order?

Prime Numbers

Your next problem is to compute lists of prime numbers, using a method known as Eratosthenes' sieve.

The method is as follows:

Define a function sieve which implements this algorithm, such that sieve [2..10] = [2,3,5,7].

You will need to test whether one number is a multiple of another. Use the function 

relprime p n = n `mod` p > 0
which returns true if n is relatively prime to p. Try evaluating 
map (relprime 3) [1..10]
to get some ideas.

Here are some interesting expressions to evaluate:

You will need to interrupt the evaluation of some of them: use control-C.

Searching for a word

In this exercise, you develop a simple version of the UNIX utility grep, which searches for occurrences of strings in files. The problem is to define a function search, which finds all the lines in a file which contain a given word. For example, if a file called input contains 
Mary had a little lamb
Its fleece was white as snow
And everywhere that Mary went
That lamb was sure to go
then calling 
search "Mary" "input"
should return 
["Mary had a little lamb", "And everywhere that Mary went"]
You will need a function to read a file. In the lecture, I used a function called 
file :: [Char] -> [Char]
whose argument is a file name, and whose result is the list of characters in that file. This function is not standard in Hugs. To use it, you must import it into your program. Do as follows: Another very useful function for this exercise is elem, which tests whether an element occurs in a list. For example, 
elem 2 [1, 2, 3]   ---->    True
elem 'x' "hello"   ---->    False
You will also probably use lines, words, map and filter.

If you would like to print out the result of your search more prettily, then define 

printSearch w f = putStr (unlines (search w f))
and try calling 
printSearch "Mary" "input"
What does unlines do?

A Rhyming Dictionary

Ordinary dictionaries list words in alphabetical order. Rhyming dictionaries list words in `rhyming order', where words with the same ending appear together; first words ending in 'a', then words ending in 'b', and so on. Define a function 
rhyming :: [[Char]] -> [[Char]]
which sorts a list of words into rhyming order. Hint: Haskell already provides alphabetic ordering on words using the usual comparison operators, for example "apple" < "banana".

Use rhyming to extract all the words from a file and produce a rhyming dictionary from them. You may wish to remove duplicate elements from a list: if you add 

import List
at the top of your definitions, then you can do so using the function nub.

A Larger Project: Checking Web Pages for Broken Links

This is a larger, more difficult exercise: don't worry if you don't have time to attack it.

It can be fun to write programs which read web pages, as well as which read files. The module EasyIO which you downloaded earlier also includes a function to do just that: 

web :: [Char] -> [Char]
takes a URL as an argument, and returns the contents of the web page as its result. If the URL does not exist, then the result is the empty list, so you can test whether a URL is broken by calling null (web url).

A URL ending in "html" refers to an HTML web page; you will see that web returns a string containing many 'tags' (between '<' and '>'). As a first step, try writing a function to extract all the tags from a web page. Hint: use break..

Links are tags of the form 

<a href="url">
Define a function to extract the URL from a link tag.

You will also need a function to test whether a tag is a link. You may find the function isPrefixOf useful for this. If you want to use it, you must add import List at the top of your function definitions.

Now you should be able to define a function which takes the URL of a web page, and returns a list of the broken links on that page.

Last modified: Fri May 12 13:06:59 MET DST 2000