ICS 313-02: Fundamentals of Programming Languages

Fall Semester 1999-2000

ICS313 Instructor

KFUPM ID#: 9999999
E-Mail: someaddress@ccse.kfupm.edu.sa

Section: 04

Programming Assignment # 2: Functional Programming Using Haskell

Date: 12-December-1999

Latest Revision # 2 on 27-November-1999

Synopsis

Haskell is a pure functional programming language incorporating lazy evaluation, list-comprehension. It is a strictly typed language. As is the case with several other functional programming languages functions are “first-class” citizens in Haskell. Some of the commonly used functional forms are: composition, mapping, folding, and scanning. It has support for classes. Information hiding is provided through modules that can import/export selectively.

	In this programming, to practice several of the above ideas, a package for graph operations is developed. All the solutions are developed using the literate programming style.

Information and Computer Science Department
King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia

Table of Contents
Information Gathering Part
Programming Part
Series 1:: Basics I: Manipulating Lists of Integers
Problem Statement
Solution/Design
Implementation
Testing + Example Sessions
Reflections on the Experiment in Solving this Problem
Series 2:: Basics II: Manipulating Lists of Pairs of Integers
Problem Statement
Solution/Design
Implementation
Testing + Example Sessions
Reflections on the Experiment in Solving this Problem
Series 3:: Utilities I: Manipulating Lists of Vertices
Problem Statement
Solution/Design
Implementation
Testing + Example Sessions
Reflections on the Experiment in Solving this Problem
Series 4:: Basics I: Manipulating Lists of Edges
Problem Statement
Solution/Design
Implementation
Testing + Example Sessions
Reflections on the Experiment in Solving this Problem
Series 5:: Graph Algorithms I: Manipulating Graphs
Problem Statement
Solution/Design
Implementation
Testing + Example Sessions
Reflections on the Experiment in Solving this Problem
Series 6:: Graph Algorithms II: Operations on Graphs
Problem Statement
Solution/Design
Implementation
Testing + Example Sessions
Reflections on the Experiment in Solving this Problem
Summary
Mistakes Made
Lessons Learned and Useful Tips/Hints
Effort Put in

Information Gathering Part
Notes:

<* As you are reading documentation, you will come across bits and pieces of information that will be fresh in your mind. Just take a note of it briefly so as to recall the full context and purpose when you review it. It is important that you use your own words & phrases and allow the process to mature rather than typing a few lines/paragraphs from the source mechanically. Taking such notes is not only a reinforcement to your learning, but a valuable asset that comes out handy when you have to submit homeworks, projects, or even review for your examinations. In addition, it can form a sound basis for continued expansion. 
So far as exploration part is concerned, as you browse, please keep reviewing what you've been doing from time to time and take a note of those URLs or sites where you are spending sometime. Maintain a table of such URLs and a brief description, so that you have your knowledge base handy. In a short while, you will be knowing where you need to go when you need a particular kind of information. Once you accumulate enough of such links, you can carry it with you on a floppy, so that you can be at home all the time! *>

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.

Series 1:: Basics I: Manipulating Lists of Integers

Problem Statement

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 there 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]".

Solution/Design

<* Inputs and Outputs. Pseudo code to an adequate level of detail so that even a person unfamiliar with the implementation language can follow and understand the solution. *>

Implementation

<* Well commented, i.e., literate programs in the specified language. *>

Testing + Example Sessions

<* Actual Sessions of illustrative function executions. *>

Reflections on the Experiment in Solving this Problem

<* A brief summary of major mistakes made in solving this problem and how they were rectified etc. You may also discuss the sequence of improvements & findings that might have made the solution easier and cleaner. *>

 
Series 2:: Basics II: Manipulating Lists of Pairs of Integers

Problem Statement

Write a variant of each of the above-mentioned functions to work on a list of pairs of integers.

> pairExists :: (Int, Int) -> [(Int, Int)] -> Bool
Given an integer pair and a list of integer pairs, it decides whether or not the given integer pair occurs in the list.

> addPair :: (Int, Int) -> [(Int, Int)] -> [(Int, Int)]
Given an integer pair and a list of integer pairs adds the integer pair to the list if it was not already inside the list.

> dropPair :: (Int, Int) -> [(Int, Int)] -> [(Int, Int)]
Given an integer pair and a list of integer pairs removes the integer pair from the list if it was there otherwise leaves the list unchanged.

> joinPairLists :: [(Int, Int)] -> [(Int, Int)] -> [(Int, Int)]
Given integer pair lists, this function combines the two lists of pairs of integers removing any duplicate values.

> filterPairs :: ((Int, Int) -> Bool) -> [(Int, Int)] -> [(Int, Int)]
Given a predicate and an integer pair list, this function should remove from the list all the pairs that do not satisfy the predicate. 

Solution/Design

<* Inputs and Outputs. Pseudo code to an adequate level of detail so that even a person unfamiliar with the implementation language can follow and understand the solution. *>

Implementation

<* Well commented, i.e., literate programs in the specified language. *>

Testing + Example Sessions

<* Actual Sessions of illustrative function executions. *>

Reflections on the Experiment in Solving this Problem

<* A brief summary of major mistakes made in solving this problem and how they were rectified etc. You may also discuss the sequence of improvements & findings that might have made the solution easier and cleaner. *>

Series 3:: Utilities I: Manipulating Lists of Vertices

Problem Statement

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]

Solution/Design

<* Inputs and Outputs. Pseudo code to an adequate level of detail so that even a person unfamiliar with the implementation language can follow and understand the solution. *>

Implementation

<* Well commented, i.e., literate programs in the specified language. *>

Testing + Example Sessions

<* Actual Sessions of illustrative function executions. *>

Reflections on the Experiment in Solving this Problem

<* A brief summary of major mistakes made in solving this problem and how they were rectified etc. You may also discuss the sequence of improvements & findings that might have made the solution easier and cleaner. *>

Series 4:: Basics I: Manipulating Lists of Edges

Problem Statement

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]
> neighboursOf :: Vertex -> [Edge] -> [Vertex]
Finds the vertices that are adjacent to a given node (i.e., those that have direct connections to them from 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]

> 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.

Solution/Design

<* Inputs and Outputs. Pseudo code to an adequate level of detail so that even a person unfamiliar with the implementation language can follow and understand the solution. *>

Implementation

<* Well commented, i.e., literate programs in the specified language. *>

Testing + Example Sessions

<* Actual Sessions of illustrative function executions. *>

Reflections on the Experiment in Solving this Problem

<* A brief summary of major mistakes made in solving this problem and how they were rectified etc. You may also discuss the sequence of improvements & findings that might have made the solution easier and cleaner. *>

Series 5:: Graph Algorithms I: Manipulating Graphs
Problem Statement
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]
A predicate that tests whether a graph is completely connected

> outDegreeSequence :: Graph -> [Int]

> 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.

Solution/Design

<* Inputs and Outputs. Pseudo code to an adequate level of detail so that even a person unfamiliar with the implementation language can follow and understand the solution. *>

Implementation

<* Well commented, i.e., literate programs in the specified language. *>

Testing + Example Sessions

<* Actual Sessions of illustrative function executions. *>

Reflections on the Experiment in Solving this Problem

<* A brief summary of major mistakes made in solving this problem and how they were rectified etc. You may also discuss the sequence of improvements & findings that might have made the solution easier and cleaner. *>

Series 6:: Graph Algorithms II: Operations on Graphs

Problem Statement
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.

Solution/Design

<* Inputs and Outputs. Pseudo code to an adequate level of detail so that even a person unfamiliar with the implementation language can follow and understand the solution. *>

Implementation

<* Well commented, i.e., literate programs in the specified language. *>

Testing + Example Sessions

<* Actual Sessions of illustrative function executions. *>

Reflections on the Experiment in Solving this Problem

<* A brief summary of major mistakes made in solving this problem and how they were rectified etc. You may also discuss the sequence of improvements & findings that might have made the solution easier and cleaner. *>

 

Summary
Mistakes Made

<* Document the various kinds of mistakes you made during the course of solving this assignment. 
1.	Waited till the last minute
2.	Was counting on the reliability of my machine and not keeping adequate backups
3.	Was taking easy short cuts, and ending up paying dearly all along…..
*>
Lessons Learned and Useful Tips/Hints

<* List the lessons learned that you could possibly offer to yourself and for others in future. As a rule of thumb, if you have spent more than an hour on any single item, it is a pretty good item for documentation. Take a few minutes, analyze why you spent that kind of time, and explore alternatives that you could have examined. Any tips or suggestions that you can offer out of such an experience? It is expected that the length of this section is a useful metric characterizing the amount of effort you are putting. Let your effort be productive!  *>
Effort Put in

<* Document the itemized break down of time you have spent on each part of this assignment. Such documentation will enable you plan better for similar work in future. *>

Description	Time Spent
in Hours	
Information Gathering Part (Exploration + Note taking)		
Programming Part		
Series 1:: Basics I: Manipulating Lists of Integers		
Series 2:: Basics II: Manipulating Lists of Pairs of Integers		
Series 3:: Utilities I: Manipulating Lists of Vertices		
Series 4:: Basics I: Manipulating Lists of Edges		
Series 5:: Graph Algorithms I: Manipulating Graphs		
Series 6:: Graph Algorithms II: Operations on Graphs		
Summary		
Document Preparation		
Revision 1		
* * *		
Revision n
<* Duplicate as many times as needed and remove the extra lines *>		
Total Effort in Hours Towards this Submission		
Cumulative Effort in Hours for all the Previous Submissions		
Cumulative Effort in Hours for all the Submissions so far