comp320 review questions

comp302review.sml

(* q1: *)
fun insert (v, []) = [v]
  | insert (v, (h::t)) =
    if (v < h) then v::(h::t)
    else h::(insert (v,t));

(* q2: *)
local
  fun helper [] acc = acc
    | helper (h::t) acc = helper t (insert (h, acc))
in
  fun insertionSort v = helper v []
end

(* q3: *)
fun insertionSort v = 
  List.foldr insert [] v

(* q4: *)
fun interleave_helper e [] = []
  | interleave_helper e (h::t) =
    (e::h)::(interleave_helper e t)

(* q5: *)
fun interleave k [] = [[k]]
  | interleave k (h::t) =
    [(k::(h::t))] @ (interleave_helper h (interleave k t))

(* q6: *)
fun interleave k [] = [[k]]
  | interleave k (h::t) = 
    [(k::(h::t))] @ 
      (map (fn x => h::x) (interleave k t))

(* q7: *)
fun flatten [] = []
  | flatten (h::t) = h@(flatten t)

(* q8: *)
fun flatten [] = []
  | flatten l =
    List.foldr (fn (a, b) => a@b) [] l

(* q9: *)
fun permutations [] = [[]]
  | permutations (h::t) =
    flatten 
      (map (fn x => interleave h x) (permutations t))

(* q10: *)
fun permutations l = 
  List.foldr 
    (fn (x, y) => flatten (map (fn xs => interleave x xs) y))
    [[]] l

(* q11: *)
fun repeat e 0 = []
  | repeat e n = e::(repeat e (n-1))

(* q12: *)
fun concatMap [] f = []
  | concatMap (h::t) f =
    (f h)@(concatMap t f)

(* q13: *)
fun concatMap l f =
  List.foldr (fn (a, b) => (f a)@b) [] l

(* q14: *)
fun concatMap l f =
  flatten (map f l)

(* q15: *)
fun stutter l =
  concatMap l (fn x => repeat x x)

(* q16: *)
fun pairs p1 p2 =
  concatMap p1
  (fn p =>
    (concatMap p2 (fn q => [(p, q)])))

(* q17: *)
fun map f l =
  concatMap l (fn x => [(f x)])

(* q18: *)
fun foldr f start l =
  primrec' (fn (x, xs, res) => f(x, res)) start l

(* q19: *)
exception Exception
fun primrec' f b l =
List.foldr 
 (fn ([], res) => raise Exception
   | ((h::t), res) => f(h,t,res))
 b (List.foldr (fn (a, []) => [[a]]
                 | (a, (h::t)) => (a::h)::(h::t)) [] l) 

(* q20: *)


(* q21. *)
fun zipWith f l1 l2 =
  map f (pairup l1 l2)

(* q22. - incomplete *)
fun pairup' l1 l2 =
  List.foldr (fn (x, res) => (fn y => (x,y))::res) [] l1

(* q23. *)
local
  fun helper _ [] = []
    | helper [] (h::t) = 
      (h, t) :: helper [h] t
    | helper l (h::t) =
      (h, l@t) :: helper (l@[h]) t
in
  fun splittings l = helper [] l
end

(* q24. *)
local
  fun helper _ [] cont =  cont []
    | helper [] (h::t) cont =
      helper [h] t (fn ls => cont((h,t)::ls))
    | helper l (h::t) cont =
      helper (l@[h]) t (fn ls => cont((h, l@t)::ls))
in
  fun splittings_tr l = helper [] l (fn i => i)
end

(* q25. *)
local
  fun helper acc [] = [acc]
    | helper acc (h::t) =
      (helper (acc@[h]) t) @
      (helper acc t)
in
  fun powerset [] = [[]]
    | powerset (h::t) =
      (helper [h] t)@(powerset t)
end

(* q26. *)
fun powerset l =
  List.foldr 
  (fn (x, xs) =>
    (List.map (fn p => x::p) xs) @ xs) 
  [[]] 
  l

(* q27. *)
fun any p [] = false
  | any p (h::t) = (p h) orelse any p t

(* q28. *)
fun any p l =
  List.foldr (fn (x, res) => res orelse p x) false l

(* q29. *)
fun all p [] = true
  | all p (h::t) = p h andalso all p t

(* q30. *)
fun all p l =
  List.foldr (fn (x, res) => res andalso p x) true l

(* q31. *)
fun all p l =
  not (any (fn x => not (p x)) l)

(* q32. *)
fun append l1 l2 =
  List.foldr (fn (x, xs) => x::xs) l2 l1