CS1 Supervision 2.sml

(* 3.1 *)

(* This uses O(n) memory and time *)
fun sumBadly []    = 0
  | sumBadly (x::xs) = x + sumBadly xs;

sumBadly [1, 2, 3, 4, 5];
(* val it = 15: int *)


(* This uses O(1) memory but still O(n) time *)
fun sumStateful total []      = total
  | sumStateful total (x::xs) = sumStateful (total+x) xs;

val sum = sumStateful 0;

sum [1, 2, 3, 4, 5];
(* val it = 15: int *)



(* 3.2 *)

(* This takes O(n) time, and is required to *)
fun last []      = raise Match
  | last [x]     = x
  | last (x::xs) = last xs;



(* 3.3 *)

fun evenItemsStateful _ accum []  = accum
  | evenItemsStateful true  accum (v::vs) = evenItemsStateful false (v::accum) vs
  | evenItemsStateful false accum (v::vs) = evenItemsStateful true      accum  vs;

(* Why not curry? Well, I tried, but this is hardly Haskell, is it?

   Namely

        val evenItems = evenItemsStateful true [];

   throws an "informative"

        Warning-The type of (evenItems) contains a free type variable. Setting it to a unique
        monotype.

    Gee, thanks. I guess I *did* want my pattens to only match types that no objects have! *)

fun evenItems vs = evenItemsStateful true [] vs;



(* 4.1 *)

(* Really should do a merge on `sorted xs` and `sorted ys`
   because that takes O(ln xs + ln ys) time, not O(n²).

   But... there's no built-in sort, AFAICT. Really, now? *)

fun member item = List.exists (fn x => x = item);

fun uniqueStateful accum []      = accum
  | uniqueStateful accum (x::xs) =
        uniqueStateful (if member x accum then accum else x::accum) xs;

(* Sigh... *)
fun unique xs = uniqueStateful [] xs;

fun union xs ys = unique (xs @ ys);




(* 4.2 *)

val seperateSignsProper = List.partition (fn x => x >= 0);

seperateSignsProper [1, 2, 0, 4, 5, ~1, ~4, 2, ~1, 5];

(* val it = ([1, 2, 0, 4, 5, 2, 5], [~1, ~4, ~1]): int list * int list *)


(* Nah, you can't count that as cheating... Whatever... *)

fun seperateSignsImproper xs =
    (
        List.filter (fn x => x >= 0) xs,
        List.filter (fn x => x < 0) xs
    );

seperateSignsImproper [1, 2, 0, 4, 5, ~1, ~4, 2, ~1, 5];

(* val it = ([1, 2, 0, 4, 5, 2, 5], [~1, ~4, ~1]): int list * int list *)


(* What, still not happy? Fine... *)

fun seperateSignsAtrociousStateful cache [] = cache
  | seperateSignsAtrociousStateful (gte, lt) (x::xs) =
        seperateSignsAtrociousStateful
            (if x < 0 then (gte, x::lt) else (x::gte, lt))
            xs
    
val seperateSignsAtrocious = seperateSignsAtrociousStateful ([], []);

seperateSignsAtrocious [1, 2, 0, 4, 5, ~1, ~4, 2, ~1, 5];

(* val it = ([1, 2, 0, 4, 5, 2, 5], [~1, ~4, ~1]): int list * int list *)



(* Extension *)

fun nRotations 0     xs  = []
  | nRotations n (x::xs) = (x::xs) :: nRotations (n-1) (xs @ [x]);

fun rotations xs = nRotations (length xs) xs;