Curried Functions

A function of n arguments that is viewed as a function of one argument that returns a function of n-1 arguments.

Example:

fun incby x y = x + y

This is val incby = fn: int -> int -> int.

Consider this example:

fun curry f x y = f(x,y);

If $f$: $\alpha$; $x$: $\beta$; $y$: $\gamma$; $f(x,y)$: $\delta$

Then, curry: $\alpha \rightarrow \beta \rightarrow \gamma \rightarrow \delta$. Rewriting in terms of $f(x,y)$, this is curry: $((\beta * \gamma) \rightarrow \delta) \rightarrow \beta \rightarrow \gamma \rightarrow \delta$.

function application associates to the left!

Defining functions

This function should return first j elements of a list, return [] if j $\leq$ 0, and return [] if arglist is less than j.

fun take 0 arglist = []
	| take j (x::xs) = x :: (take (j-1) xs)
	| take j [] = [];

Can also use an if-then-else construct.

fun take j [] = []
    | take j (x::xs) = 
        if j > 0
        then x::( take (j-1) xs)
        else [];

Non-exhaustive match warnings

When cases in pattern-matching are non-exhaustive, potential for run-time errors. SML shows warnings.

foldl

fun foldl f e [] = e
    | foldl f e (x::xs) = foldl f (f(x,e)) xs;

This is a val foldl = fn: ('a * 'b -> 'b) -> 'b -> 'a list -> 'b list

Can be used to convert any infix operator, such as ‘+’, to a function that takes a pair by preceding it with ‘op’. Then can use foldl to apply the op.

Example:

foldl op+ 0 [1, 2, 3]

produces 6.

@

@ is a built-in infix operator to append one list to another.

Appending lists:

infixr 5 @;
fun ([] @ ys) = ys
    | (x::xs) @ ys = x::(xs @ ys);

Note the recursion in the third line; we append x to the front of the result of the combination of the remainder xs with ys.

Accumulating parameters

Move elements one by one from the input list to the accumulating list.

Sometimes, you need to explicitly give the type to ML.

fun rev2 ([], (y:'a list)) = (([]:'a list), y)
    | rev2 ((x::xs), y) = rev2(xs, x::y);

val rev2 = fn : 'a list * 'a list -> 'a list * 'a list

The type-checking algorithm has trouble with the types of empty lists.

The first argument to rev2 is the remaining input, and the second arg is the solution so far. If this is wrapped in an outer function, you get a linear time solution to reversing a list.