(* Nick Mooney
CSE 341
Section 4
*)
(* check if a list of integers consists of alternating 1's and 0's *)
(* uses higher order functions (f passed to one_v1), but there is a better way *)
(* notice that we're using curried syntax *)
fun one_v1 _ [] = true
| one_v1 f (1::tail) = f tail
| one_v1 _ _ = false
fun zero_v1 ([]) = true
| zero_v1 (0::tail) = one_v1 zero_v1 tail
| zero_v1 _ = false
fun is_alternating_v1 (1::tail) = zero_v1 tail
| is_alternating_v1 (0::tail) = one_v1 zero_v1 tail
| is_alternating_v1 [] = true
| is_alternating_v1 _ = false
(* the above was a little redundant -- why don't we just
not make assumptions about the start element of the list *)
fun is_alt xs = one_v1 zero_v1 xs orelse zero_v1 xs
(* this works! *)
(* ML gives us special syntax for mutual recursion *)
fun one [] = true
| one (1::tail) = zero tail
| one _ = false
and zero [] = true
| zero (0::tail) = one tail
| zero _ = false
fun is_alternating (1::tail) = zero tail
| is_alternating (0::tail) = one tail
| is_alternating [] = true
| is_alternating _ = false
fun is_alt' xs = one xs orelse zero xs
(* Aaand as a little segue. Let's put this in a module *)
signature FSM =
sig
val is_alternating : int list -> bool
end
structure MyFSM :> FSM =
struct
fun one [] = true
| one (1::tail) = zero tail
| one _ = false
and zero [] = true
| zero (0::tail) = one tail
| zero _ = false
fun is_alternating (1::tail) = zero tail
| is_alternating (0::tail) = one tail
| is_alternating [] = true
| is_alternating _ = false
fun is_alt xs = one xs orelse zero xs
end
(* This signature allows only authenticated users to query their account
balance, protecting their sensitive information *)
signature ACCOUNT =
sig
type authentication
type account = int
val authenticate : string * string -> authentication option
val query_balance : account * authentication -> int
end
(* This implementation would ideally be in another file, hidden from the user *)
structure BankAccount :> ACCOUNT =
struct
type authentication = string * string
type account = int
val private_data = [("Nick", "Password"),
("Dan Grossman", "Dadjoke"),
("Paul Allen", "Saul Ellen"),
("Doug Evans", "Juice!")]
fun authenticate (uname, passwd) =
List.find (fn (a,b) => (a = uname) andalso (b = passwd)) private_data
(* In this bank, everyone has a constant bank balance of 42. *)
fun query_balance (acc, auth) = 42
(* I am not very good at computer.
However -- notice that the ONLY way to get a value of type
"authentication" is if authenticate returns a SOME. You
cannot construct one from outside the structure. *)
end
(* Currying and High order functions *)
val numbers = [1, 1, 2, 3, 4, 5, 6, 7, 9, 13, 11, 81]
fun is_valid (x, y) = (x + y = 17)
val all_pairs = List.map (fn x => List.map (fn y => (x, y)) numbers) numbers
val valid_pairs = List.map (List.filter is_valid) all_pairs
val non_empty = List.filter (fn x => not(null x)) valid_pairs
val flattened = List.foldl (fn (x, acc) => (x @ acc)) [] non_empty
(* Only flattens lists that are one nested once. Remember, in SML all the elements
in a list must be of the same type. The depth of all of the lists will be the
same *)
(* flatten is already in the List standard library as List.concat but is here
for practice. *)
(* Type of the list is supplied to get around the "value restriction"
warning. *)
val flatten = List.foldr (fn (x : (int * int) list, acc) => x @ acc) []
(* This might look like unnecessary function wrapping but it is used to get
around the "value restriction" waring as well. This one works for types
'a list list *)
fun flatten2 xs = List.foldr (fn (x, acc) => x @ acc) [] xs