version 4, including all changes.
.
| Rev |
Author |
# |
Line |
| 1 |
GlynWebster |
1 |
Higher-order functions are functions that take other functions as parameters, create functions or return functions. |
| |
|
2 |
|
| 4 |
AristotlePagaltzis |
3 |
The use of higher-order functions with PolymorphicTypes results in a style of programming that rivals ObjectOrientation for expressiveness. Some may assert it beats it. |
| 1 |
GlynWebster |
4 |
|
| 3 |
AristotlePagaltzis |
5 |
[ML], [Haskell], [LISP], [Python] all allow full use of high-order functions. [C] allows you to pass functions as arguments, but their usefulness is rather limited. |
| 1 |
GlynWebster |
6 |
|
| |
|
7 |
!!!An Example |
| |
|
8 |
|
| 2 |
GlynWebster |
9 |
(This follows on from the the example in PolymorphicTypes.) |
| 1 |
GlynWebster |
10 |
|
| |
|
11 |
Glyn want make new trees from old ones by changing the leaves. So he writes a function to do this for him. One of its parameters will be a function that takes the value of a leaf and returns the changed value. |
| |
|
12 |
|
| |
|
13 |
# __let rec__ map change tree = |
| |
|
14 |
__match__ t __with__ |
| |
|
15 |
| Leaf value -> Leaf (change value) |
| |
|
16 |
| Node (left, right) -> Node (map change left, map change right) ;; |
| |
|
17 |
''val map : ('a -> 'b) -> 'a tree -> 'b tree = <fun>'' |
| |
|
18 |
|
| |
|
19 |
Once again Ocaml has worked out the types for itself. (__a -> b -> c__ is ML for "function that takes parameters of the types __a__ and __b__ and returns a value of type __c__.) It's also noted that if the __change__ function doesn't return the same type as its given then the __map__ function will return a tree of a different type. Good. That's what Glyn wanted. (If it wasn't he could add some type annotations to say so.) |
| |
|
20 |
|
| |
|
21 |
Here's a function that can be used as a __change__ parameter: |
| |
|
22 |
|
| |
|
23 |
# string_of_int ;; |
| |
|
24 |
''- : int -> string = <fun>'' |
| |
|
25 |
|
| |
|
26 |
You can guess what that does. __map__'s type is __('a -> 'b) -> 'a tree -> 'b tree__, so if I give it __string_of_int__ as its first parameter then __'a__ will be __string__ and __'b__ will be __int__, so __map__ should return a __string tree__... |
| |
|
27 |
|
| |
|
28 |
# __let__ numtree = Node (Node (Leaf 1, Leaf 2), Leaf 3) ;; |
| |
|
29 |
''val numtree : int tree = Node (Node (Leaf 1, Leaf 2), Leaf 3)'' |
| |
|
30 |
|
| |
|
31 |
# map string_of_int numtree ;; |
| |
|
32 |
''- : string tree = Node (Node (Leaf "1", Leaf "2"), Leaf "3")'' |
| |
|
33 |
|
| |
|
34 |
And it does! |
| |
|
35 |
|
| |
|
36 |
If he writes a few more functions like this he will have a reusable library of binary tree operations. ML makes writing reusable code and easy and ''reliable'' process. |
| |
|
37 |
|
| |
|
38 |
There's a lot more things you can do with higher-order functions, some of them very painful. What I've shown you there's at least ''one'' good thing you can do with them. |
