I'm reading Harper's book, Intro to Standard ML, and am a bit confused on section 11.3, Returning Functions.
1) He defines a function that creates constant functions. He writes:
"Given a value k, the application constantly k yields a function that yields k whenever it is applied. Here's a definition of constantly:
val constantly = fn k => (fn a => k)
The function constantly has type 'a -> ('b -> 'a)." This makes sense to me: you supply a value of type 'a and it returns a function that always returns that value (of type 'a), regardless of the input (of type 'b, which may or may not be same as type 'a).
But then he says we can also define this function as:
fun constantly k a = k
This just looks like a function that takes two arguments and returns the first...but not a function that returns another function...
What am I missing?
2) A little later, Harper discusses a map function. I understand the basic map function. He then talks about a map function that will let us apply the passed-in function to many lists (instead of calling our original map function several times with the same passed-in function for each call). He writes:
fun map' f nil = nil
| map' f (h::t) = (f h) :: (map' f t)
"The function map so defined has type ('a -> 'b) -> 'a list -> 'b list. It takes a function of type 'a -> 'b as argument and yields another function of type 'a list -> 'b list as result."
I'm pretty lost here as it looks like map' just applies f to all of the elements in a list and returns the resulting list. So I would have thought it would be of type:
('a -> 'b) * 'a list -> 'b list
Where am I going wrong?
Thanks for the help, bclayman
Both of your questions arise from a lack of clarity about what arguments to a function actually are. In SML, every function (recall that functions are values) takes precisely one argument. That argument may be a tuple (of type 'a * 'b but it is still a single argument (that needs to be destructured).
In SML, fun f x1 x2 ... = T is syntactic sugar for val rec f = fn x1 => fn x2 => ... => T. So constantly k evaluates to fn a => k.
Whether you give map the type ('a -> 'b) * 'a list -> 'b list or ('a -> 'b) -> 'a list -> 'b list is a library design issue, but the effect is the same. They do the same thing, though the first takes a tuple of a function and a list, while the second takes the function first and returns a function from lists to lists. This is called "currying" in the programming languages literature. (The tuple version is "uncurried", the other is "curried".)