Transcript ML Basics

Higher-Order Functions
cs776 (Prasad)
L2HOF
1
Higher-Order Functions
• A function that takes a function as argument
and/or returns a function as result is called
a higher-order function or a functional.
• ML/Scheme treat functions as first-class
(primitive) values.
– Can be supplied as input to functions.
» Not allowed in Ada.
– Can be created through expression evaluation.
» Not allowed in C++/Java/LISP.
– Can be stored in data structures.
cs776 (Prasad)
L2HOF
2
Nested Functional + Static Scoping
fun f x =
let
val g = fn y => 8 * x + y
in g
end;
val h = f 5;
h 2;
• Breaks stack-based storage allocation; Requires
heap-based storage allocation and garbage
collection (Closures)
cs776 (Prasad)
L2HOF
3
ML function definitions
fun
|
elem_to_list []
= []
elem_to_list (h::t) =
[h] :: (elem_to_list t)
elem_to_list [“a”] = [[“a”]]
fun inc_each_elem []
= []
| inc_each_elem (h::t)=
(h+1) :: (inc_each_elem t)
inc_each_elem [1,2,3] = [2,3,4]
cs776 (Prasad)
L2HOF
4
Abstracting Patterns of Recursion
fun
|
map
map
f
[]
= []
f (h::t) =
(f h)::(map f t)
fun
elem_to_list x =
map (fn x => [x]) x
val
inc_each_elem
=
map (fn x => x+1)
cs776 (Prasad)
L2HOF
5
Functionals : Reusable modules
Libraries usually contain functionals that can be
customized.
sort order list
Can be used for:
descending_order_sort
ascending_order_sort
sort_on_length
sort_lexicographically
sort_on_name
sort_on_salary
...
cs776 (Prasad)
L2HOF
6
Orthogonality
• Instead of defining related but separate
functions such as
remove-if
remove-if-not
process_till_p process_till_not_p
define one generalized functional
complement.
• Refer to:
cs776 (Prasad)
CommonLISP vs Scheme
L2HOF
7
Currying
fun
fun
plus (x, y)
add
x y
=
=
x + y
x + y
plus (5,3) = 8
add 5 3
= 8
add 5
= (fn x => 5+x)
• Curried functions are higher-order functions
that consume their arguments lazily.
• All ML functions are curried !
cs776 (Prasad)
L2HOF
8
Significance of Curried Functions
• Supports partial evaluation.
• Useful for customizing (instantiating)
general purpose higher-order functions
(generics).
• Succinct definitions.
• Denotational (Semantics) Specifications.
• One-argument functions sufficient.
• All ML functions are unary.
cs776 (Prasad)
L2HOF
9
fun curry f =
fn x => (fn y => f(x,y))
fun uncurry f =
fn (x,y) => (f x y)
curry (uncurry
f)
uncurry (curry f)
=
=
f
f
(Higher-order functions)
cs776 (Prasad)
L2HOF
10
Classification of functions
• Primitive
+ , * , - , etc.
• Higher-order
– Hierarchical
(sort order list),(filter pred list)
– Self-applicable
map , id
fun
cs776 (Prasad)
(E.g.,
double
f
=
L2HOF
(map (map f))
)
f o f;
composition
11
From Spec. to Impl.
• Spec:
(sqrt x) >= 0 /\ (sqrt x)^2 = x
• Computable Spec:
(sqrt x) >= 0 /\
abs((sqrt x)^2 - x) < eps
• Improving Approximations (Newton’s method):
y(n+1) = (y(n) + [x / y(n)]) / 2
cs776 (Prasad)
L2HOF
12
fun improve x y =
( y + x / y) / 2.0 ;
val eps = 1.0e~5;
fun satis x y =
abs( y*y - x)
< eps ;
fun until p f y =
if p y then
y
else until p f (f y) ;
fun sqrt x =
until (satis x) (improve x) 1.0;
cs776 (Prasad)
L2HOF
13
ML : Meta Language
• Initial Domains of Application
– Formal Specification of Languages
– Theorem Proving
• Theorems are values (terms) of an ADT.
• Theorems can only be constructed using the
functions supported by the ADT (“no spoofing”).
• ML is a mathematically clean modern
programming language for the construction
of readable and reliable programs.
• Executable Specification.
cs776 (Prasad)
L2HOF
14
•
•
•
•
•
•
•
•
•
•
Symbolic Values
Recursive Definitions
Higher-Order Functions
Strongly Typed
Static Type Inference
Polymorphic Type System
Automatic Storage Management
Pattern Matching
ADTs; Modules and Functors
Functional + Imperative features
cs776 (Prasad)
L2HOF
15
fun len []
| len (x::xs)
1 +
=
0
=
len xs
(define (len xs)
(if (null? xs)
0
(+ 1 (len (cdr xs)))
)
)
cs776 (Prasad)
L2HOF
16