Earlier we said that every function in ML takes exactly one argument, and that we can simulate multiple arguments using tuples. Actually there is one other way to simulate multiple arguments in ML (and other functional languages): we can write our function to take one argument that takes the first argument and returns an (anonymous) function that takes the second argument and returns the result. For example, we could write a function plus that looks like
fun plus (i:int) =
fn (j:int) => i + j;
Now plus has type int -> int -> int, where the arrow associates to the right. So the expression
- plus 3; val it = fn : int -> int
returns an anonymous function that takes an integer and adds 3 to it, and the expression
- plus 3 5; val it = 8 : int
does what we would expect. Thus we can use the function normally (except that we pass the arguments individually instead of packaged into a tuple) or partially evaluated as an anonymous function to be used later.
This device is called currying after the logician H.B. Curry. At this point you may be worried about the efficiency of returning an intermediate function when you're just going to pass all the arguments at once anyway. Run a test if you want (you should know how to find out how to do this), but rest assured that curried functions are entirely normal in functional languages, so there is no speed penalty worth worrying about. In fact, they're so useful and commonplace that ML provides syntactic sugar to make them as easy to define as the functions on tuples that we have been writing. A much simpler way to write our plus function is
fun plus (i:int) (j:int) : int = i + j
This is identical to our earlier definition; we can still call "plus 3 5" to compute 8, or we can call "plus 3" to compute a function that adds 3 to its argument. What are the types of these curried functions? What functions result from partial application of them?
fun lesser (a:real) (b:real) : real = if a<b then a else b
fun equals (x:int) (y:int) : bool = (x=y)
fun pair (x:'a) (y:'b) : ('a * 'b) = (x,y)
Last Thursday we saw that ML supports polymorphism, which means that we can write functions that operate on variables many types. It does this with type variables, whose names start with one single quote. Normal type variable names are 'a, 'b, etc., pronounced "alpha", "beta", etc. For example, we can write the polymorphic identity function as
fun ident (x : 'a) : 'a = x
This function has type 'a -> 'a and will return its argument regardless of type. We also had a function above that produced a polymorphic pair. How could we write a function to extract the first or second element from such a pair?
fun fst (x:'a, y:'b) : 'a = x fun snd (x:'a, y:'b) : 'b = y
What if we had written this instead?
fun fst (x:'a, y:'a) : 'a = x
We can write polymorphic datatypes, too. The simplest example is the built-in datatype option, which looks like
datatype 'a option = NONE | SOME of 'a
This is useful when a function may legitimately decide not to return a value. (If the function should always return a value under normal conditions, then the right approach is to raise an exception when something goes wrong.) For example, the SML Basis Library defines a function Int.fromString that tries to read an integer from the beginning of the string passed to it, ignoring initial whitespace. If it succeeds, it returns SOME i for some integer i. If the beginning of the string doesn't look like an integer, the function returns NONE. And if the beginning of the string looks like an integer but the number is too big to fit in type int, then the function raises an exception. Int.fromString has type string -> int option. Here's an example:
- Int.fromString("123");
val it = SOME 123 : int option
- Int.fromString("abc");
val it = NONE : int option
- Int.fromString("123123123123");
uncaught exception overflow
We'll talk more about exceptions another day, so ignore them for now. Do you see how to write a function that tries to scan an integer from the beginning of a string, square it, and convert it back to a string?
fun square_string (s:string) : string option =
case Int.fromString(s) of
NONE => NONE
| SOME i => SOME(Int.toString(i*i))
Here's an example of using this function:
- square_string("3");
val it = SOME "9" : string option
- square_string("hi");
val it = NONE : string option
Remember that the body of a polymorphic function can't make any assumptions about the types of its polymorphic arguments. You can't even assume that you can compare two elements of that type! So you'll normally see polymorphism in the functions that access general data structures, like the polymorphic lists we saw that used a datatype like
datatype 'a list = Nil | Cons of ('a * 'a list)
Polymorphic lists are so useful that they are built into ML: there is already a type 'a list and a set of functions and operators to deal with them. First of all, lists are very easy to write: just separate the elements with commas and enclose the whole thing in brackets.
- [3,4]; val it = [3,4] : int list - [3,3,4]; val it = [3,3,4] : int list - [(1,"one"),(2,"two"),(3,"three")]; val it = [(1,"one"),(2,"two"),(3,"three")] : (int * string) list - []; val it = [] : 'a list - [op+, op-, op*]; val it = [fn,fn,fn] : (int * int -> int) list
The constant nil is a synonym for the empty list, and the infix operator :: (pronounced "cons") prepends a head element onto a list very much as we have been doing using the constructor Cons. So [3,5,9] means the same as 3::[5,9], which is the same as 3::5::[9], which is the same as 3::5::9::nil. This is not the same as 3::5::9, which produces a type error because 9 is not a list.
We can pattern match on lists much as we could with datatypes. To compute the sum of an int list, we would write
fun sum (l : int list) : int =
case l of
[] => 0
| n::ns => n + sum(ns)
ML provides functions null, to determine whether a list is empty, and length, to compute the length of a list. Unlike our sum function, these functions are polymorphic. How could we write them?
fun null (l : 'a list) : bool =
case l of
[] => true
| _ => false (* also could have matched _::_ *)
fun length (l : 'a list) : int =
case l of
[] => 0
| x::xs => 1 + length(xs)
How could we write a function that appends two lists?
fun append (l1 : 'a list, l2 : 'a list) : 'a list =
case l1 of
[] => l2
| x::xs => x::(append(xs, l2))
ML provides this function for us in the form of an infix operator @. So we can write
- []@[1,3,5]; val it = [1,3,5] : int list - [1,3]@[2,4]; val it = [1,3,2,4] : int list
and so on. Remember that the :: operator (cons) takes an element and a list, but the @ operator (append) takes two lists. I had lots of bugs related to this when I was first learning ML.
One good source of lists is strings: ML provides a function explode that turns a string into a list of characters, and an inverse function implode that changes a list of characters into a string. For example,
- explode "Greg"; val it = [#"G",#"r",#"e",#"g"] : char list
We haven't worked with individual characters before, but you can see the syntax for a character. Now, how can we convert a string to all capital letters? We can look in the Basis Library and see that there is a function Char.toUpper that we can use. You saw last week in section that a standard operation on a data structure is map, which returns a new data structure containing the application of a given function to every element. Unsurprisingly, List has a map function of type ('a -> 'b) -> 'a list -> 'b list. Notice that this function is curried. So we can write
fun toUpper (s:string) : string =
implode(map Char.toUpper (explode s))
By the way, String also has a map function. What would its type be? ((char -> char) -> string -> string) Using it, we could have written
fun toUpper (s:string) : string = String.map Char.toUpper s
or even more concisely,
val toUpper = String.map Char.toUpper
Why is this equivalent?