Exercise 5: An Algebra of Sets.
Overview
In this exercise you will learn to use the FiniteSet library.
FiniteSets are a data structure which have been designed as a mechanism
for aggregating propositional formula. The operators in the library
allow programmers to create large numbers of related formulae using
a high level of abstraction. The abstraction is finite sets of tuples,
or as the databses folk call such abstractions, relations. The library
supports an interface very similar to the relational algebra, and this
exercise schools you in using these operators to construct FiniteSets
with interesting propoerties.
Learning Objectives
 Learn to create and initialize FiniteSets.
 Learn to combine sets using the operators of the library.
 Learn to state and test properties of sets.
Getting Started
You will need a few documents to get started.
 Read the notes on finite sets.
 Down load the FiniteSet library and put in your code directory.
 Study the examples from the lecture notes.
Create a small file to start with that looks like this.
Be sure you have the Prop and the FiniteSet modules where Ghci can find them.
Solution template 
 Your name in a comment
module Exercise5 where
import Prop
import FiniteSet

What to do
 Create dimensions.
 Create a dimension for the set of strings {"Odd", "Even"}
 Create a dimension for the set of positive whole numbers less than 10.
 Create a dimension for the range Int range 5 to 10.
 Define an enumeration dataype for the days of the week. Create a dimension for it.
 Create sets with different kinds of associations.
 Define a set of pairs from the OddEven and the 510 range dimensions.
Associate a Bool with each pair such that the string describes the number.
For example ("Even",4)=True, ("Odd",4)=False, etc.
 Define a set of pairs, where each component
of the pair comes from positive whole numbers less than 10, and the value associated
with the pair is the sum of the two components.
 Define the set {(i,i+1)  i < [0..4]}. Be sure tuples where the second component
isn't the successor of the first aren't in the set at all.
 Define a set of pairs, where each component
of the pair comes from the days of the week, and a pair (day1,day2) is associated
with True if day1 is the day before day2 in the time ordering.
 Study the Boolean class. Write 2 functions that are overloaded with types.
 Boolean t => t > t
 Boolean t => t > t > t
 Create a conditional set for a set of triples, where each component is drawn from 04.
For example {(0,0,0)=LetterP 0, (0,0,1)=LetterP 1, ... (4,4,4)=LetterP 124}
 Use set operations. Form the complement of several sets. Form the union and intersection of several sets.
Note, that these operations only work if the set assoicates a Boolean operation with each tuple.
(Boolean t => FiniteSet t).
 Use relational operations
 Copy the the definition of the relation p, the set of pairs
of people from the file FiniteSetExamples.hs.
 Create a set of quaduples by using join that has the following 4 generation
structure (greatgrandparent,grandparent,parent,child).
 then create the binary (greatgrandparent,child) relation.
 Do the same thing by writing a function, step, that extends a
binary relation, extending the generation one step.
For example step
(parent,child) > (grandparent,child),
step(grandparent,child) > (greatgrandparent, child).
You will have to apply this function twice.
 Write an iterate operation that applies a one step extend operation like you wrote
above n times. Could you use this to write a transitive closure operation over
a binary relation? How many times would you have to apply it? What else would
you have to do beside it apply it n times?
 Extra Credit
 Create the addition 3D relation such that (i,j,k) is in the relation if i+j=k for the range 010.
 Create the max 3D relation such that (i,j,k) is in the relation if k=max i j for the range 010.
 Given a (possibly cyclic) 3D relation path (place1,place2,distance12), could you create
a shortest path 3D relation?
What to turn in.
 Drop it in the Ex5 folder in the class drop box
 Be prepared to talk about your solution in class.
Back to the class webpage.
Back to the Course Schedule.