These exercises are modified from old exam assignments from the course on functional programming at Department of Computer Science, University of Copenhagen in the period 2007-2012. These assignments were given to students with no previous programming experience except for the 7 weeks the course took.
The 2007 assignments were made by Jakob Grue Simonsen.
They were modified by Simon Shine in slight ways for the purpose of this presentation.
Let an m-list be a list with m elements, and an m-square be a list of m number of m-lists. This can be expressed as the type 'a square. For example, the following value is a 3-square:
type 'a square = 'a list list val threesquare = [[1,2,3], [0,2,4], [5,0,1]]
Task: Declare an exception KError and a function rankK : 'a square -> int so that if xss is an m-square for some number m, then rankK xss will have the value m, while rankK xss will raise the exception KError if xss is not an m-square.
Task:: Declare a function mapK : ('a -> 'b) -> 'a square -> 'b square so that if xss is an m-square for some m, mapK f xss will form a new m-square with each element x replaced with f x.
For example, if the following function is defined:
fun stars 0 = "" | stars n = "*" ^ stars (n - 1)
Then mapK stars threesquare should give the following result:
[["*", "**", "***"], ["", "**", "****"], ["*****", "", "*"]]
An m-square can be regarded as a two-dimensional matrix with m columns and m rows. The following value:
can be viewed as a representation of the following matrix:
Task: Declare a function showK : string square -> string so that print (showK xss) prints the two-dimensional display of the m-square xss. If all elements are not equally long, they should be extended (to the right) with spaces so they all get the same length. If the longest element is t characters long, then each line in the output of showK will have m·t characters.
For example, if val starsquare = mapK stars threesquare, then print (showK starsquare) should give the following result: [["*", "**", "***"], ["", "**", "****"], ["*****", "", "*"]]
* ** *** ** **** ***** *
In an m-square, rows and columns are numbered from 0 to m – 1, so each element has a position, which is a pair (i,j) consisting of its row and column number.
The distance between two elements can be said to be of one springer's move if the row distance is 1 and the column distance is 2, or if the row distance is 2 and the column distance is 1. If an element is not too close to an edge, it will have 8 other elements within one springer's move.
Task: Construct a function springerneighbors : int -> int * int -> (int * int) so that springerneighbors m (i,j) returns the list of positions that are within one springer's move from position (i,j) on the m-square m.
A springer path on an m-square is an m-square with type int square where some of the elements are numbered 1, 2, ..., n (n > 0) in such a way that one of the corners contains a 1, and from this element there is a springer move to an element 2, and so on up to n. The number n is called the length of the springer path. The remaining m2 – n elements should all be 0.
The following is an illustration of a springer path (of length 8) on a 3-square:
Task: Declare a function checkSpringerPath : int square -> bool so it returns true exactly if its argument is a springer path.
Task: Declare a function divide : string -> string list list that gives all possible divisions of a string into non-empty substrings. The order of the result is not important, but the order of the substrings is. For example, divide "abc" could return:
[["a", "b", "c"], ["a", "bc"], ["ab", "c"], ["abc"]]
It is known that all positive integers can be written as the product of primes in an unambiguous way. For example, 120 = 23 · 3 · 5. This representation can be stored in an (int * int) list.
Task: Declare a function factorize : int -> (int * int) list so for every n > 0 then factorize n will return a list [(p1,m1),...,(pk,mk)] where k ≥ 0, every pi is a prime, every mi ≥ 1, and the produkt of all pimi = n.
Given an order relation ≤t between elements of a type t, we can define the lexicographical expansion, ≤t list, between elements of type t list. (That is, given an order relation between elements of a type t, we can define another order relation for the type t list.)
A list is lexicographically less than or equal to another list exactly when their elements, starting from the left, are pairwise equal until the first list either ends or contains an element strictly less than its corresponding element in the other list.
For example, given an order relation ≤int, it holds that [3,1] ≤int list [3,1], and it holds that [2,5] ≤int list [2,5,3], and it holds that [7,2] ≤int list [7,3].
In Standard ML, the <= operator cannot be overloaded by the programmer, but it can instead be written as a structure with the following signature:
signature ORD = sig type t val leq : t * t -> bool end
For example, we can define an ORD-structure from the built-in (overloaded) operator <= for characters:
structure OrdChar : ORD = struct type t = char val leq = op <= end
Task: Declare a functor, Lex, with the following template:
functor Lex (structure O : ORD) : ORD where type t = O.t list = struct (* write me! *) end
The order relation in the resulting structures must be exactly the lexicographical expansion of the argument structure. In particular, the following should work:
structure LexChar = Lex (structure O = OrdChar) fun leqs (s1, s2) = LexChar.leq (explode s1, explode s2)
In this case, leqs : string * string -> bool should give the same results as Standard ML's overloaded comparison operator, <=, for the type string.