I'm struggling to understand this. Problem:
I have
datatype 'a tree= Leaf of 'a | Node of 'a tree * 'a * 'a tree
I have to find value in it using binary search. Here's my code.
fun binSearch ((Leaf n), x) = if n=x then true else false
| binSearch ((Node (left, n, right)), x) =
if n=x then true else
if n>x then binSearch (left, x) else
binSearch (right, x)
But I'm supposed to write function with this signature:
val binSearch : int tree -> int -> bool
I get the int tree * int -> bool part, but how do I do 'a -> 'b -> 'c
To turn a function of type a * b -> c into a function of type a -> b -> c, replace fun f (x, y) = ... with fun f x y = ....
fun f (x, y) = ... defines a function that takes a tuple and automatically unpacks the tuple's values into the variables x and y. This is a syntactic short cut for fun f tuple = case tuple of (x, y) => .... It leads to the type a * b -> c because a * b means "a tuple containing an a and a b". The function can then be called as f (x, y) or f t where t is a tuple.
fun f x y = ... on the other hand defines a so-called curried function, which is a function that takes the parameter x and then returns another function, which takes the parameter y and then returns the result. It is a syntactic shortcut for fun f x = fn y => .... The function can then be called as f x y or g y where g has previously been set to f x.