Higher-order functions

• A first-order function is one whose parameters and result are all "data"

• A second-order function has one or more first-order functions as parameters or result

• In general, a higher-order function has one or more functions as parameters or result

map

• map applies a function to every element of a list and returns a list of the results

• map f [x, y, z] returns [f x, f y, f z]

• Notice that map takes a function as an argument

• An anonymous function has the form
(fun parameter -> body)

• The use of anonymous function makes the definition simpler and doesn't require exposing an auxiliary function

•

map(fn x => x*x) [1,2,3]; 

Currying

• In ML, functions are values, and there are operations on those values

• Currying absorbs a parameter into a function, creating a new function

• map takes one argument (a function), and returns one result (also a function)

Order of operations

• let add (x, y) = x + y;;

– # val add : int * int -> int = <fun>

• But also consider:

• # let add x y = x + y;;

– val add : int -> int -> int = <fun>

• add x y is grouped as (add x) y

• and int -> int -> int as int -> (int -> int

Example : A useful function: span

• span finds elements at the front of a list that satisfy a given predicate

• Example:

• span even [2;4;6;7;8;9;10] gives [2, 4; 6]

• span isn't a built-in; we have to write it

fun span f lst =
if f (hd lst)
then (hd lst)::span f (tl lst)
else [];

val span : ('a -> bool) -> 'a list -> 'a list = <fun>

span even [2;4;6;7;8;9;10];

- : int list = [2; 4; 6]

• span returns the elements at the front of a list that satisfy a predicate

Defining local values with let

• let declaration in expression

• let decl1 in let decl2 in expression

let val a = 5 in
let val b = 10 in
a + b;

• let helps avoid redundant computations

filter 
 
fun filter p nil = nil
 | filter p (x::xs) =
 if p x
 then x :: filter p xs
 else filter p xs
 
(* val filter = fn : ('a -> bool) -> ('a list -> 'a list) *)

reduce

fun reduce f u nil = u
 | reduce f u (x::xs) = f x (reduce f u xs)
 
(* val reduce = fn : ('a -> ('b -> 'b)) -> ('b -> ('a list -> 'b)) *)
 
 
foldr 
 
val foldr = reduce ;
 
(* val foldr = fn : ('a -> ('b -> 'b)) -> ('b -> ('a list -> 'b)) *)
 
 
foldr1
 
exception foldr1'
 
fun foldr1 f nil = raise foldr1'
 | foldr1 f [x] = x
 | foldr1 f (x::xs) = f x (foldr1 f xs)
 
(* val foldr1 = fn : ('a -> ('a -> 'a)) -> ('a list -> 'a) *)
 
 
foldl
 
 
fun foldl f u nil = u
 | foldl f u (x::xs) = foldl f (f u x) xs
 
(* val foldl = fn : ('a -> ('b -> 'a)) -> ('a -> ('b list -> 'a)) *)
 

Folding

Applications to sorting

fun insert (x : int) nil = [x]
 | insert x (yys as y::ys) =
 if x <= y
 then x :: yys
 else y :: insert x ys
(* val insert = fn : int -> (int list -> int list) *)
 
fun sort xs = reduce insert nil xs
(* val sort = fn : int list -> int list *)
 
fun quicksort nil : int list = nil
 | quicksort (x::xs) =
 let
 val small = filter (fn y => y<=x) xs
 val large = filter (fn y => y>x) xs
 in
 quicksort small @ [x] @ quicksort large
 end
(* val quicksort = fn : int list -> int list *)
 
fun sorted nil = true
 | sorted [x:int] = true
 | sorted (x::y::xs) = x <= y andalso sorted (y::xs)
(* val sorted = fn : int list -> bool *)