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.
  1. Create a dimension for the set of strings {"Odd", "Even"}
  2. Create a dimension for the set of positive whole numbers less than 10.
  3. Create a dimension for the range Int range 5 to 10.
  4. Define an enumeration dataype for the days of the week. Create a dimension for it.
• Create sets with different kinds of associations.
  1. Define a set of pairs from the Odd-Even and the 5-10 range dimensions. Associate a Bool with each pair such that the string describes the number. For example ("Even",4)=True, ("Odd",4)=False, etc.
  2. 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.
  3. 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.
  4. 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.
  1. Boolean t => t -> t
  2. Boolean t => t -> t -> t
• Create a conditional set for a set of triples, where each component is drawn from 0-4. 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
  1. Copy the the definition of the relation p, the set of pairs of people from the file FiniteSetExamples.hs.
  2. Create a set of quaduples by using join that has the following 4 generation structure (great-grand-parent,grand-parent,parent,child).
  3. then create the binary (great-grand-parent,child) relation.
  4. Do the same thing by writing a function, step, that extends a binary relation, extending the generation one step. For example step
     (parent,child) -> (grand-parent,child),
     step(grand-parent,child) -> (great-grand-parent, 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
  1. Create the addition 3D relation such that (i,j,k) is in the relation if i+j=k for the range 0-10.
  2. Create the max 3D relation such that (i,j,k) is in the relation if k=max i j for the range 0-10.
  3. Given a (possibly cyclic) 3D relation path (place1,place2,distance1-2), 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.