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

**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 *m*^{2} – *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 = 2^{3} · 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
*[(p _{1},m_{1}),...,(p_{k},m_{k})]* where
k ≥ 0, every p

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.