(* CSE 341 *)
(* Autumn 17 *)
(* 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
(* We don't need this syntax though *)
(* How might we do this without it? *)
(* Notice that every call is a tail call *)
(* turns out we can do this for any finite state machine *)
(* is_even *)
(* Here we hide the implementation of a function *)
signature EVEN =
sig
val is_even : int -> bool
end
structure Basic :> EVEN =
struct
fun is_even 0 = true
| is_even 1 = false
| is_even n = is_even (n-2)
end
structure Faster :> EVEN =
struct
fun is_even 0 = true
| is_even 1 = false
| is_even n = is_even (n mod 2)
end
(* This signature allows only authenticated users to query their account
balance, protecting their sensitive information *)
(* Here we hide the implementation of not only a function, but a type as well *)
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 = [("Eric", "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
(* We can use the API to authenticate and check our balance *)
val (SOME ericauth) = BankAccount.authenticate ("Eric", "Password")
val nickbalance = BankAccount.query_balance (42,ericauth)
val failure = BankAccount.authenticate ("Evil","Evil")
(* 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. *)
(* Remember flat_map from last week? *)
fun flat_map f xs =
case xs of
[] => []
| x::xs' => (f x) @ flat_map f xs'
(* There are a lot of ways to flatten a list of lists into one list. *)
(* How would we flatten the list with flat_map? *)
val flatten_with_flat_map = flat_map (fn x => x)
(* Here we can use foldr *)
(* 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