Standard ML

Lists Exam Questions

(and solutions)

---

exercise 1

Implement map using foldl

val foldl = fn : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b;
val map = fn : ('a -> 'b) -> 'a list -> 'b list;

fun map f inpList = foldl
    _
    _
    inpList
;

map (fn x => x * 2) [1, 2, 3, 4];

exercise 1 - solution

fun map f inpList = foldl
    (fn (v, l) => l @ [f v])
    []
    inpList
;

map (fn x => x * 2) [1, 2, 3, 4];
(* val it = [2, 4, 6, 8] : int list *)

exercise 2

insSort (insertion sort) sorts a list according to a given less-then function.

val foldr = fn : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b;
val insSort : ('a * 'a -> bool) -> 'a list -> 'a list;

fun insSort lt inpList = foldr
    _
    _
    inpList
;

insSort (op<) [1, ~3, 5, 0];

exercise 2 - solution

fun insSort lt inpList = foldr
    (let fun ins v [] = [v]
       	   | ins v (x :: xs) = if lt (v, x) then v :: x :: xs else x :: (ins v xs)
     in (fn (a, l) => ins a l) end)
    []
    inpList
;

insSort (op<) [1, ~3, 5, 0];
(* val it = [~3, 0, 1, 5] : int list *)

exercise 3

Let’s define:

fun upto m n = if (m > n)
    then []
    else m :: (upto (m + 1) n)
;

infix o;
fun f o g = fn x => f (g x);

exercise 3a

What will be printed?

val a = map (upto 2) (upto 2 5);

exercise 3a - solution

val a = map (upto 2) (upto 2 5);
(* val a = [[2], [2, 3], [2, 3, 4],[2, 3, 4, 5]] : int list list *)

exercise 3b

What will be printed?

map
    (
        (fn f => null (f ()))
        o
        (fn t => fn () => tl t)
    )
    a
;

exercise 3b - solution

map
    (
        (fn f => null (f ()))
        o
        (fn t => fn () => tl t)
    )
    a
;
(* val it = [true, false, false, false] : bool list *)

exercise 3c

What will be printed?

map
    (List.filter (fn t => t mod 2 = 0))
    a
;

exercise 3c - solution

map
    (List.filter (fn t => t mod 2 = 0))
    a
;
(* val it = [[2], [2], [2, 4], [2, 4]] : int list list *)

exercise 4

Implement a tail recursive append

fun append ...

append ([1, 2, 3], [4, 5, 6]);

reminder:

infix @;
fun []      @ ys = ys
  | (x::xs) @ ys = x :: (xs @ ys);

exercise 4 - solution

local
  fun aux([], ys) = ys
    | aux(x :: xs, ys) = aux (xs, x :: ys)
in
  fun append (xs, ys) = aux (aux (xs, []), ys)
end;

append ([1, 2, 3], [4, 5, 6]);
(* val it = [1, 2, 3, 4, 5, 6] : int list *)

exercise 5

Implement flatten using foldr

flatten : 'a list list -> 'a list;

fun flatten ...

flatten [[1, 2, 3], [4, 5, 6], [], [7, 8, 9]];

exercise 5 - solution

fun flatten xs = foldr (op@) [] xs;

flatten [[1, 2, 3], [4, 5, 6], [], [7, 8, 9]];
(* val it = [1, 2, 3, 4, 5, 6, 7, 8, 9] : int list *)