King Fahd University of Petroleum and Minerals
Department of Information and Computer Science
ICS 313: Fundamentals of Programming Languages
Fall 1999-2000
Date: 27th November 1999 Programming Assignment # 2: Functional Programming using Haskell Due date: 12th December 1999
Deliverables and Submission guidelines

Download this assignment from the course page and take it on a floppy. If you open it in a browser, you will have the advantage of easy navigation to some web documents through hot links. Deliverables and Submission guidelines are provided on-line.
Before You Start
After downloading this softcopy and taking a print out, you may consider following the strategy given below. 
1.	Set aside about 15-30 hours (depending upon how much you grasped from the extra sessions on Haskell) of your schedule during the two-week interval exclusively catered for this assignment. For best results, allocate it in sufficiently large chunks; say three or more hours each, so that you can start a problem, solve it and take its annotated sessions.
2.	Read through this whole document slowly and carefully, noting down what you consider to be important details. If any statements are not clear, get them clarified as soon as possible.
3.	Dwell upon the scope and plan of the project. Review your background on directed graphs from any of the books from your earlier courses.
4.	Prepare an initial sketch on paper with a pencil on what you need to do for each of the problems. You may sketch high-level functions with signatures.
5.	Go through the two tutorials that are part of the handout you were given and take a note of relevant functions you may be needing in your solution. For each such, just try it out interactively, figuring out and logging into your notebook a sample usage.  You may find the slides as well as softcopy handout from the extra session helpful.
6.	Revise the initial sketch of functions and their signatures you prepared in step 4, in view of the available facilities you encountered in step 5.
7.	If you follow the style recommended in the Haskell session, have separate windows for the functions being tested, another for holding literate Haskell scripts for tested functions, it can cut down the development time significantly. Methodically, try to develop one function at a time and transfer them to the tested lhs file. In the first pass, complete the required questions.
8.	Prepare a project report according the spelled out requirements for project reports.
9.	Take a checkpoint of all your work.
10.	Take a look into the optional extra credit questions, which are logical generalizations of the basic problems you have already completed. Attempt to tackle as many as you can in view of your time budget. You are expected to be creative in devising solutions and suggesting and doing alternatives for these extra credit questions. There are fewer restrictions on adherence to guidelines. However they have to work well within the framework you’re developing.
11.	After one or two days of break, reflect on the full activity of the project, your state at the beginning, major transitions, costly mistakes etc. 
12.	Prepare a final project report that includes all these components. One cannot over emphasize the need for the section on reflections (you will be doing this for yourself and not to the grader or your instructor), which will help you better-organized next time.

On-line Exploration and Reading Part

Exercise 1 [Online Reference Section]:
Examine the local Haskell Reference Section thoroughly. You will be saving a good amount of time by going through the tutorials that were given as part of the hardcopy handout. While you’re doing that, keep trying out examples. They will be handy later.

Programming Part

The project has been broken down into simple logical units to help you work through it systematically and developing useful functions to be used in the later parts. The first two sections should be straightforward and they are placed there to help you develop some basic experience in handling list operations. You are advised to follow the exercises in the order given for a smooth flow.

Some of the functions that you should write in Questions 5 and 6 require some background knowledge on graph algorithms.  If need be, you may update your knowledge on these basic algorithms by consulting any Textbook of data structures.  A sample list of possible references is given in the footnote. The goal of the project is to enable you develop “functional” thinking through the development of a nice collection of functions that enable one to define, manipulate and query directed graphs. Doing the equivalent in imperative paradigm would probably be more involved, time consuming, and less enjoyable.

Series 1:: Basics I: Manipulating Lists of Integers
Write the following functions for handling simple lists in the Haskell programming language. 

> entryExists :: Int -> [Int] -> Bool
Given an integer and a list of integers decides whether or not the given integer occurs in the list.

> addEntry :: Int -> [Int] -> [Int]
Given an integer and a list of integers adds the integer in the list if it was not already inside the list.

> dropEntry :: Int -> [Int] -> [Int]
Given an integer and a list of integers removes the integer from the list if it was ther otherwise leaves the list unchanged.

> joinLists :: [Int] -> [Int] -> [Int]
Given integer lists, this function combines the two lists removing any duplicate values.

> filterEntries :: (Int -> Bool) -> [Int] -> [Int]
Given a predicate and an integer list, this function should remove from the list all the values that do not satisfy the predicate. For example, if the predicate is "isEven :: Int -> Bool" and the list is "[1..10]", filterEntries should return the result "[2,4,6,8,10]".

Series 2 :: Basics II: Manipulating Lists of Pairs of Integers
Write a variant of each of the above-mentioned functions to work on a list of pairs of integers.

Series 3:: Utilities I: Manipulating Lists of Vertices
This exercise is a direct and simple extension of functions in Series 1.  The only difference is that the list elements are now constructed using the Vertex constructor of the algebraic data type Vertex defined below. Write the following functions accordingly.

> data Vertex = Vertex Int deriving (Eq, Ord, Show)
> vertexExists::Vertex -> [Vertex] -> Bool
> addVertex :: Vertex -> [Vertex] -> [Vertex]
> dropVertex :: Vertex -> [Vertex] -> [Vertex]
> joinVertices :: [Vertex] -> [Vertex] -> [Vertex]
> filterVertices :: (Vertex -> Bool) -> [Vertex] -> [Vertex]

Series 4 :: Utilities II: Manipulating Lists of Edges
This exercise is, similarly, a direct extension of functions in Series 2.  The only difference is that the list elements are now constructed using the Edge constructor of the algebraic data type Edge defined below. Write the following functions accordingly.

> data Edge   = Edge Int Int deriving (Eq, Ord, Show)
> edgeExists :: Edge -> [Edge] -> Bool
> addEdge :: Edge -> [Edge] -> [Edge]
> dropEdge :: Edge -> [Edge] -> [Edge]
> joinEdges :: [Edge] -> [Edge] -> [Edge]
> filterEdges :: (Edge -> Bool) -> [Edge] -> [Edge]
> incidentEdges :: Vertex -> [Edge] -> [Edge]
Given a vertex v and a list of edges, this function returns a list of edges that have v as the first component.
 
> neighboursOf :: Vertex -> [Edge] -> [Vertex]
Finds the vertices that are adjacent to a given vertex (i.e., those that have direct connections to them from the given vertex).

> whoseNeighbours :: Vertex -> [Edge] -> [Vertex]
Finds the vertices to which a giver vertex is adjacent  (i.e., those from which there are direct connections to the given vertex).

> findPath :: Vertex -> Vertex -> [Edge] -> [Vertex]
Given two vertices, finds the list of vertices that form a path from the first to the second.  If no path exists between them an empty list is returned.

> indirect:: [Vertex] -> Vertex -> [Edge] -> [Vertex]
A subsidiary of  the function findPath. Used when there is no direct path between two given vertices v and w. The firs vertex list is the list of the vertices adjacent to v.  This function determines whether there is a path from any of these intermediate vertices to w.  If such a path exists, it returns the vertices list and a null list otherwise.

> reachable :: Vertex -> Vertex -> [Edge] -> Bool
Given two vertices, determines whether there is a path from the first to the second.

> diffList :: (Eq a) => [a] -> [a] -> [a] 
Given any two lists, finds the elements that are in the first list that are not in the second list.

Series 5 :: Graph Algorithms I: Manipulating Graphs
In this question you will make use of the functions that you already defined in Series  3 and 4 above.  Most of these functions should be clear from the name, but a one line summary follows each function signature.

> data Graph  = Graph [Vertex] [Edge] deriving (Eq, Ord, Show)
Representation of a graph.

> addVertex2Graph :: Graph -> Vertex -> Graph
Adds a vertex to the vertices list in a graph

> dropVertexFromGraph :: Graph -> Vertex -> Graph
Removes a vertex from the vertices list in a graph

> addEdge2Graph :: Graph -> Edge -> Graph
Adds an edge to the edges list in a graph

> dropEdgeFromGraph :: Graph -> Edge -> Graph
Removes an edge from the edges list in a graph

> isEmptyGraph :: Graph -> Bool
A predicate that tests whether a graph is empty

> vertices :: Graph -> [Vertex]
Collects the list of vertices of a graph

> n:: Graph -> Int
Returns the number of vertices in a given graph

> m:: Graph -> Int
Returns the number of edges in a given graph

> edges :: Graph -> [Edge]
Collects the list of edges of a graph

> isCompleteGraph :: Graph -> Bool
A predicate that tests whether a graph is completely connected

> inDegreeSequence :: Graph -> [Int]
The indigree of a vertex  v is the number of vertices from which there is a direct link to v. This function returns the list of indegrees of all vertices in a graph

> outDegreeSequence :: Graph -> [Int]
The outdigree of a vertex  v is the number of  vertices to which there is a direct link from v. This function returns the list of outdegrees of all vertices in a graph

> buildGraph:: [[Int]] -> Graph
Constructs a graph from a list of lists of integers.

> readGraph :: String -> Graph 		(  Extra Credit )
Reads a graph (in some form) from a file

> writeGraph :: Graph -> String -> Bool	(  Extra Credit )
Writes a graph (in some form) into a file

> graphUnion :: Graph -> Graph -> Graph
Joins two graphs

> isConnectedGraph :: Graph -> Bool
A predicate that tests a graph for connectivity.

Series 6:: Graph Algorithms II: 
Modify the Edge type to include cost information, which is required for the implementation of the following algorithms.

Various kinds of spanning trees:

> breadthFirstSpanningTree :: Graph -> Graph

> depthFirstSpanningTree :: Graph -> Graph	(  Extra Credit )
> primsMinCostSpanningTree :: Graph -> Graph	(  Extra Credit )

> topologicalSort :: Graph -> [Vertex]
Sorts the vertices of a graph into topological order.

The following is optional: After developing the above, noticing the similarity of signatures a well as computation,
see if you can come up with a higher-order spanning tree algorithm that takes the specific algorithm parameters.

> spanningTree :: Graph -> Graph 		(  Extra Credit )
Computes different kinds of spanning trees from a graph

> placeGraph :: Graph -> Vertex -> [Vertex]	(  Extra Credit )
Computes the placement of vertices according to a layered breadth-first embedding starting from the given vertex.

> shortestPath :: Graph -> Vertex -> Vertex -> [Vertex]	(  Extra Credit )
Computes the shortest path between the two given vertices.

> shortestPathsToAll :: Graph -> Vertex -> [[Vertex]] 	(  Extra Credit )
Computes the shortest paths from a given vertex to all other vertices.

> allPairsShortestPaths :: Graph -> [[[Vertex]]] 	(  Extra Credit )
Computes the shortest paths from every vertex to every other vertex.

Organizational Part

Exercise 1 [Filing and Organization]:
Keep all your work related to this assignment in the folder: 
ics313991-ProgrammingLanguages\Submissions\Project2-FunctionalParadigm 
in the directory structure you prepared in the first assignment. 
Keep all the programs related to this assignment in the folder: 
ics313991-ProgrammingLanguages\Programming\Haskell
Keep all the class files related to this assignment in the folder: 
ics313991-ProgrammingLanguages\Library\Haskell
Update the search path in the Options  Set  Search Path of winhugs on your machine to include the above path. This will allow the reuse of your functions.
As in the previous assignment keep two versions of your files, one in rtf format for good layout as the primary/reference copy and the other in html format facilitating easy browsing. Make a copy of the template for sampleIndex.html and sampleIndex.txt that you prepared in Assignment # 1 as:
   ics313991-ProgrammingLanguages\Submissions\Project2-FunctionalParadigm\index.html
overwriting the existing place holder page. Update both index.html and index.txt so that they adequately represent the contents of all the folders whose contents you altered.