Skip to content

Instantly share code, notes, and snippets.

@Veedrac
Last active December 26, 2015 02:09
Show Gist options
  • Save Veedrac/7075974 to your computer and use it in GitHub Desktop.
Save Veedrac/7075974 to your computer and use it in GitHub Desktop.
(* 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;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment