Functional Programming

in the Maths & Natural Sciences programme (MN)

at Uppsala University, Sweden

Hint: To force SML/NJ to print long lists, insert the following into your program:

(* Set the length of lists at which ellipsis begins *)

Compiler.Control.Print.printLength := 500 ;

Example: For

- The function
`nbLeaves`counts the number of leaves of a binary tree.

Example:`nbLeaves smallIntTree = 3` - The curried predicate
`isLeafOf`returns`true`if and only if its 'first' argument is a leaf of its 'second' argument.

Example:`isLeafOf 7 smallIntTree = true` - The curried predicate
`equalBtrees`returns`true`if and only if its two binary tree arguments have the same inorder walk.

Example:`equalBtrees smallIntTree anotherSmallIntTree = false` - The curried function
`descendants`returns a list with all the descendants of its 'first' argument in its 'second' argument, and raises the exception`NotFound`if that node is not in that tree.

Example:`descendants 2 smallIntTree = [5,3,7]`

Example:`descendants 7 smallIntTree = []`

Example:`descendants 9 smallIntTree`raises`NotFound` - The function
`preorder`returns the preorder walk, as a list, of a binary tree.

Example:`preorder smallIntTree = [1,2,5,7,3,6,10,13]`

Requirements: Do*not*use any help functions. Is your function tail-recursive? Why / Why not? - The function
`preorder'`has the same specification as`preorder`.

Requirements: Perform a*descending generalisation*, that is use a help function employing the accumulator technique. Is your function tail-recursive? Why / Why not? - The function
`preorders`returns the concatenation of the preorder walks of a list of binary trees.

Note: This specification was obtained from the one for`preorder`by performing a*tupling generalisation*.

Example:`preorders [smallIntTree,anotherSmallIntTree] = [1,2,5,7,3,6,10,13,2,1,7,5,13,3,6,10]`

Requirements: Do*not*use any help functions. Each clause must have*at most one*recursive call. Is your function tail-recursive? Why / Why not? - The function
`preorder''`has the same specification as`preorder`.

Requirement: Use`preorders`as help function. - Which of the functions
`preorder`,`preorder'`, and`preorder''`is the most efficient in run-time? in memory consumption? Why?

- Re-implement the set-theoretic operations of exercise C (integer
sets) of Assignment 1 such that the
sets can be polymorphic (instead of being restricted to integers)
and that your datatype is based on binary
*search*trees (instead of ordered lists). Consider it an ADT, but declare it as a*non-abstract*datatype, just to ease the testing. - After choosing appropriate representations for sets & binary
relations and writing efficient functions for the necessary
operations,
write a curried function
`image`that, given a finite binary relation*R*and a finite set*S*, returns the set of all*y*such that*R*(*x*,*y*) holds for some*x*in*S*.

Example: The image of the set {1,3} in the relation {(1,2),(1,3),(2,5),(3,3),(3,4)} is the set {2,3,4}.

Requirement: Argue why your representation choices are appropriate. - After choosing appropriate representations for sets & directed
graphs and writing efficient functions for the necessary
operations,
write a curried function
`reachable`that, given a finite directed graph*G*and a vertex*v*, returns the set of all vertices of*G*that are reachable from*v*by following the edges of*G*.

Example: The set of vertices reachable from the vertex 1 in the graph with edge set {(1,2),(1,3),(2,5),(3,3),(3,4)} is {1,2,3,4,5}.

Requirement: Argue why your representation choices are appropriate. - After choosing an appropriate representation for binary relations
and writing efficient functions for the necessary operations,
write a predicate
`isTransitive`that, given a finite binary relation*R*, returns`true`if and only if*R*is transitive.

Example: The relation {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)} is transitive.

Requirement: Argue why your representation choice is appropriate.

Last modified: Wed 12 Nov 12:37:42 MEST 2003