fun countdown (x : int) =
if x=0
then []
else x :: countdown (x-1)
fun append (xs : int list, ys : int list) =
case xs of
[] => ys
| x::xs' => x :: append (xs', ys)
fun rev (xs : int list) =
let fun revtail (acc : int list, xs : int list) =
case xs of
[] => acc
| x::xs' => revtail (x :: acc, xs')
in
revtail ([], xs)
end
fun map (f : int -> int, xs : int list) =
case xs of
[] => []
| x::xs' => f x :: map (f, xs')
(* Return the sum the numbers in the given list. *)
fun sum (xs : int list) = 0
(* Return list filled with numbers in this range *)
fun range (lo : int, hi : int) = []
(* Return true if x is in xs. *)
fun isMember (x : int, xs : int list) = false
(* Return a list like xs, but with x removed *)
fun remove (x : int, xs : int list) = xs
(* Return true if sorted *)
fun isSorted (xs : int list) = false
(* deduplicate all entries in xs *)
fun dedup (xs : int list) = xs
(******** RECURSION CHALLENGES ********)
(* List Convolution
*
* Take a list of the form [x1, x2, ..., xn] and a list of the form
* [y1, y2, ..., yn] and generate a list of the form [(x1,yn), (x2,
* yn-1), ... (xn, y1)] in n recursive calls without using an
* auxiliary list. (Credit: Danvy and Goldberg, There and Back Again)
*)
(* Start with a version that uses any number of recursive calls. *)
fun convEasier (xs,ys) = (xs,ys)
(* Now implement the n-call version. *)
fun conv (xs,ys) = convEasier (xs,ys)
(*
val conv1 = conv ([1,2,3,4,5],[6,7,8,9,10])
*)
(* Palindrome
*
* Given a list of unknown length n, determine whether the list is a
* palindrome using ceiling(n/2) recursive calls and no auxiliary
* list. (Credit: Danvy and Goldberg, There and Back Again)
*)
(* Start with a version that uses any number of recursive calls. *)
fun palEasier xs = false
(* Now implement a version that uses ceiling(n/2) recursive calls *)
fun pal xs = palEasier xs
(*
val pal1 = pal [1,2,3,2,1]
val pal2 = pal [1,1]
val pal3 = pal [5]
val pal4 = pal []
val pal5 = pal [4,5,5,4,3]
*)