(* Section 4
Emily Fortuna
*)
(** Simple use of modules for namespace management **)
(* A simple signature *)
signature DICT =
sig
exception NotFound
type (''a,'b) dict (* note we don't show how it's implemented *)
val empty : (''a,'b) dict
val add : (''a * 'b) -> (''a, 'b) dict -> (''a, 'b) dict
val remove : ''a -> (''a, 'b) dict -> (''a, 'b) dict
val find : ''a -> (''a, 'b) dict -> 'b
end
(* An implementation of this *)
structure ListDict :> DICT =
struct
exception NotFound
type (''a,'b) dict = (''a * 'b) list
val empty = []
(* Note the partial application of test. *)
fun test key (k,_) = k <> key (* test for equality *)
fun remove key dict =
List.filter (test key) dict
fun add (k, v) dict =
let
val dict' = remove k dict
in
(k,v)::dict'
end
fun find k dict =
case List.find
(fn (key, _) => k = key)
dict
of
NONE => raise NotFound
| SOME (_,v) => v
(* this function is hidden (everyone outside of this
structure can't call it). Useful for helper functions
that you don't want to show externally. *)
fun hidden () = 3
end
(* An entirely different implementation *)
structure FunDict :> DICT =
struct
exception NotFound
type (''a, 'b) dict = ''a -> 'b
fun empty k = raise NotFound
fun add (k,v) dict =
fn k' =>
if k = k'
then v
else dict k'
fun find k dict = dict k
fun remove k dict =
fn k' =>
if k = k'
then raise NotFound
else dict k'
(* this function is also hidden *)
fun alsoHiddenHelper x = x
end
(* Mutual recursion *)
fun everyother l =
case l of
[] => []
| h::t => h::(everyother' t)
and everyother' l =
case l of
[] => []
| h::t => (everyother t)
(* a made-up datatype representing webpages (URL and content) and
their contents (essentially lists of words and links). note the two
datatypes are mutually recursive *)
datatype webtext = Empty
| Link of webpage * string * webtext
| Word of string * webtext
and webpage = Found of string * webtext
| Unfound of string
(* modules to the rescue! *)
signature EO =
sig
val everyother : 'a list -> 'a list
end
structure Eo :> EO =
struct
fun everyother l =
case l of
[] => []
| h::t => h::(everyother' t)
and everyother' l =
case l of
[] => []
| h::t => (everyother t)
end
(* let polymorphism *)
fun f x = x
fun g f =
let
val _ = f 6
in
f
end
(* sees type of f, and can conclude type of f' *)
val f' = g f
(* mutual recursion and polymorphism play awkwardly together *)
(* *should* be 'a -> 'a *)
fun id x = x
and break i = 1 + id i
(***** more currying and function typing review *****)
(* How does ML know it's encountered a function application? *)
fun foo(x) = x;
foo (3, 4) ;(*<-- one thing (parentheses tell the interpreter that this whole value should be passed to foo)*)
foo 3;
foo (fn x => 3 * x); (* <--- also "one thing" (note the parentheses) *)
(* So what's going on here? What type does ndef have? *)
(* ndef 5 3 *)
int -> int -> 'a
(*
So the deal with currying is you're passing the function one value, and it returns a new function that can process that value, while using some of the data you gave it So, like this:
fun foo x = fn y => x + y
So say I wanted to pass (3, 4) again to this newer version of foo:
val addThreeFunction = foo 3
(The type checker tells you "hey look, addThreeFunction is a function!")
val addThreeFunction = fn : int -> int
You can then call
addThreeFunction 4
to get the result of 7, just like you did before.
Naming all of these intermediary functions can get annoying, especially if you have many parameters to pass. So you can do this without naming the return function:
foo 3 4
This is the same as
(foo 3) 4
*)
(* What's the difference between
int -> int -> int -> int
and
((int -> int)-> int) -> int ?
Write a function that has each signature.
*)
fun newFunc x y = x + y
(* what's this function's type? *)
(* Write a function called "clone_add" of type
int list -> (fn:int -> int) list
That returns a list of functions. The function at
location i accepts a number and adds the value of
the element at index i in the int list *)
(* method 1 (not using map) *)
fun clone_add lst =
case lst of
[] => []
| head::tail => (fn x => x + head)::clone_add(tail)
fun clone_add lst =
List.map (fn element => (fn x => element + x)) lst
(* Write a function called "double" that applies clone_add
to a list *)
fun double lst =
let val result = clone_add lst
in
case (result, lst) of
([],[]) => []
| (headFunc::tailFunc, head2::tail2) => (headFunc head2)::(double tail2)
end
(* Write a function that uses fold to compute the average of an int list (integer division is fine.)*)
fun avg lst =
(List.foldl (fn (x, y) => x+y) 0 lst)
div
(List.length lst)
datatype 'a tree =
Node of 'a tree * 'a * 'a tree
| Leaf
(* Write the function fold_tree starting with *)
func -> ('a, 'b, 'a)
fun fold_tree func init tree =
case tree of
Leaf => init
| Node (left, v, right) =>
func ((fold_tree func init left),
v,
(fold_tree func init right))
fun foo (x, y, z) = x + y + z;
(* complete the following function "weird" to call foo (defined above)*)
fun foo x y = x + y
(*val weird = *)
(* ---- section 1 ------ left over from last week *)
(* Practice: use fold to define append, which juxtaposes the items of two lists or, equivalently, replaces [] at the end of the first list with the second list *)
(* define map using fold. *)