map which had the effect of
applying a function to every item in an array. Note the contents
of the array itself were changed so this was a destructive map.
Functional languages have no such destructive operations - in Miranda
the higher order function map is provided as part of the
system, but it works constructively by producing a new structure which
is the result of applying a function to every element in the old structure.
Miranda's map works on lists rather than arrays, lists being
a data structure fundamental to functional programming as arrays are
fundamental to imperative programming.
The code for map is one of the methods in the file
Higher.java, which can be found in the shared
directory /import/teaching/BSc/1st/ItP/numbers. You
will also find there the code for the interface IntToInt used
by this Java map, and code for two classes, Square and
Add which implement IntToInt.
In the same file Higher.java you will find code for another
higher order function in Java, zip, which there wasn't time
to cover in class. The zip method uses an object
representing a function which takes two integers and returns an integer.
This type of object is represented by the type IntIntToInt,
defined by the interface in the file IntIntToInt.java in
the same directory. Files for two classes that implement
IntIntToInt.java are also given, Product.java
and Diff2Squares.java.
The idea of zip is that it takes a function and two arrays,
a and b and produces (constructively, unlike our
Java map) a third array c such that
c[0] is f(a[0],b[0]), c[1] is
f(a[1],b[1]), and so on.
As an exercise, you should try defining the equivalent of further higher
order functions in Java. This may involve defining new types representing
functions like IntToInt and IntIntToInt,
although in some cases you may use those existing types. One example
of a method you could define is filter which takes an
array and an object representing a function which returns a boolean,
and returns an array consisting only of those elements of the original
array on which the function when applied gives true.
For example if a representation of the function "less than 40" were
passed into filter as an argument, it would take an
array of numbers and return an array consisting of all those numbers
from the original wich are less than 40.
Another higher order function is foldr which takes an array a and
an object representing a function f on elements of that array,
and returns f(a[0],f(a[1],f(a[2],...,f(a[n-2],a[n-1])...)))
where there are n elements in the array. Then if
f(x,y) gives the sum of x and y
you will get the sum of all the elements in the array, if it gives the
minimum x and y you will get the minimum of all
the elements in a and so on.
You could also work out how you could do function composition in Java.
Function composition is represented by the function o in
Java, which works such that if o(f,g) gives h then
h(x) is the same as f(g(x)).
Obviously, this exercise is going to be a lot easier for those who have done functional programming and thus are familiar with the idea of these higher order functions than those who haven't. But the others should still try to understand this important idea and give it a try.
I have also made available (copies were distributed in the lectures) the second semester tests for Introduction to Programming used last year. You can find the test here, and you will also need a copy of the code which the first part of the test refers to, available here. You ought to be able to do most of this test, though there are a few aspects of the first part of the test (particularly regarding the issue of inheritance) which we have't covered yet. It would be a good exercise to try and do as much of this test as you can, looking up for yourself (learning by doing) any aspects you are not yet familiar with. We did a little bit on inheritance in week 10, and I intend to cover it in more detail later.
Matthew Huntbach 22nd January 2001