Web Pages for B522

Assignment 1 (Haskell)

Due 20 January

Submit an electronic copy by email

References

Download either Hugs or ghc to your personal computers if you want to work remotely. Both systems are available from www.haskell.org. Both systems are also available on the CS machines (See ghc and hugs in the CS software database.) More information about Haskell is available at:

haskell.org, extensive web site with all kinds of resources.
The Haskell 98 report (for the brave, except for the index of standard functions).
A "cheat sheet" briefly explaining the most important standard functions.
The Haskell 98 library report, very useful documentation of the standard libraries.
A collection of important papers on the language, including the "Gentle Introduction".

1. Running Haskell

We'll be using the interactive system associated with ghc. Start your editor, and create a file Exercises.hs containing

module Exercises where
factorial n = product [1..n]

Start ghci: On a CS Unix machine, use the command "/usr/local/bin/ghci". You will see the following:

> ghci
   ___         ___ _
  / _ \ /\  /\/ __(_)
 / /_\// /_/ / /  | |      GHC Interactive, version 6.2, for Haskell 98.
/ /_\\/ __  / /___| |      http://www.haskell.org/ghc/
\____/\/ /_/\____/|_|      Type :? for help.

Loading package base ... linking ... done.
Prelude>

Now load module Exercises into the system, and test the definition of factorial.

Prelude> :l Exercises
Compiling Exercises        ( Exercises.hs, interpreted )
Ok, modules loaded: Exercises.
*Exercises> factorial 6
720
*Exercises>

To reload the module, use the command ":r". Once this works, you can experiment with small function definitions. A useful command to know is ":i", which displays information about any name.

*Exercises> :i factorial
-- factorial is a variable, defined at Exercises.hs:3
factorial :: forall a. (Num a, Enum a) => a -> a
*Exercises>

(In this case, we discover that factorial is overloaded, and can be used at any type which is both numeric and enumerable, the latter because we used an enumeration [1..n] in its definition).

2. Sets

Using a representation of sets as lists, write the following operations:

type Set a = [a]

isSubset :: Eq a => Set a -> Set a -> Bool
sameSet :: Eq a => Set a -> Set a -> Bool
powerSet :: Set a -> Set (Set a)
union :: Eq a => Set a -> Set a -> Set a 
intersection :: Set a -> Set a -> Set a
setProduct :: Set a -> Set b -> Set (a,b)
disjointUnion :: (Eq a, Eq b) => Set a -> Set b -> Set (Either a b, Either a b)
setDifference :: Eq a -> Set a -> Set a -> Set a 

*Exercises> disjointUnion [1,2,3] [1,2]
[(Left 1,Right 1),(Left 1,Right 2),
 (Left 2,Right 1),(Left 2,Right 2),
 (Left 3,Right 1),(Left 3,Right 2)]

3. Relations

Using a representation of relations as sets of pairs, write the following operations:

type Relation a b = Set (a,b)

composeRelations :: Relation a b -> Relation b c -> Relation a c 
isReflexive :: Eq a => Set a -> Relation a a -> Bool
isSymmetric :: Eq a => Relation a a -> Bool
isTransitive :: Eq a => Relation a a -> Bool
isEquivalence :: Eq a => Set a -> Relation a a -> Bool

-- Examples of relations
r1 = [(a,a) | a <- [0..10]]
r2 = [(a,b) | a <- [0..10], b <- [0..10], b > a]
r3 = [(a,a+1) | a <- [0..10]]

*Exercises> isReflexive [1..10] r1
True
*Exercises> isSymmetric r2
False

sabry ... cs indiana edu