Functional Programming

in the Maths & Natural Sciences programme (MN)

at Uppsala University, Sweden

`nbLeaves b`: the number of leaves of binary tree`b`

Example:`nbLeaves smallIntTree = 3``isLeafOf x b`:`true`if and only if`x`is a leaf of binary tree`b`

Example:`isLeafOf 7 smallIntTree = true``descendants x b`: the list of descendants of`x`in binary tree`b`, and exception`NotFound`raised if`x`is not in`b`

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

Example:`descendants 7 smallIntTree = []`

Example:`descendants 9 smallIntTree`raises`NotFound``preorder b`: the preorder walk, as a list, of binary tree`b`

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?`preorder' b`: 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?`preorders Bs`: the concatenation of the preorder walks of the elements of the list`Bs`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?`preorder'' b`: same specification as`preorder`

Requirement: Use`preorders`as a help function

- Re-implement the set-theoretic type, value, and functions of Exercise B (Integer Sets) of
Assignment 1 such that the sets can be polymorphic (instead of
being restricted to integers) and that your representation 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.

Requirement: Either of the two approaches to polymorphism on slides 7.5 to 7.8 requires changes to some of the original specifications: justify your choice of one of these two approaches, and change those specifications accordingly. - After choosing appropriate representations for finite sets &
binary relations and writing/re-using functions for the necessary
operations, write a curried function
`image R S`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 finite sets &
directed graphs and writing/re-using functions for the necessary
operations, write a curried function
`reachable G n`that, given a finite directed graph`G`and a node`n`, returns the set of all nodes of`G`that are reachable from`n`by following the edges of`G`.

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

Requirement: Argue why your representation choices are appropriate.

Last modified: Thu 18 Nov 10:44:42 MEST 2004