Monday, 10 November 2014

Iteration: functional style

for(int i = 0; i < a.length; i++){
a[i] = f(a[i], constant_info); // where f is a pure function
for(int i = 0; i < a.length; i++) {
accum = g(a[i], accum); // where g is a pure function
while(x >= 0 && s < a.length) {
ans *= h(a[x], accum);
x = a[x];

In the first example, we have a function purely in terms of the i'th element of a. It cannot affect anything else about a and it doesn't have any other information about a.

In the second example, we ease up and give ourselves access to an accumulated value that could possibly summarize the previous part of the array.

In the final one we let all hell loose and allow the value to determine where we go next. We're no longer accumulating in a fixed direction from left to right. We're allowing the value at our location to determine where we jump to next.

The above are three general ways of iteration. Now imagine if we had specific loop constructs that tackled each of the above cases. Aside from the clutter, this would actually make stuff more clear. Using these constructs would guarantee that any effect on our array was localized, or that an update to our accumulator is restricted to the correct values. I mean if all we wanted to do was simply modify the individual characters of a string (say by applying a shift cipher) having access to the entire array seems a bit overkill right. It's easy to imagine messing up and referencing some other part of the array in the update. So we could implement something like,

forIndividual (new Function <Dest_Type, Source_Type> ( Source_Type valueAtInd) {
public Dest_Type apply(Source_Type valueAtInd){
return some_jiggery_pokery(valueAtInd);
forAccumulate (new Function <Dest_Type, Tuple<Dest_Type, Source_Type>> (){
public Dest_Type apply(Source_Type valueAtInd, Dest_Type accum){
return accumulate_stuff(valueAtInd, accum);
forJumpAround (new Function <Tuple <Source_Type, Dest_Type>, Source_Type> (){
public Tuple<Dest_Type, Source_Type> apply(Source_Type stream){
return new Tuple(process_element_in_stream(stream), next_in_stream(stream));

That looks particularly ugly. It's because the idea of an update is not first class in Java, reifying it results in the above. However the idea behind these elaborate schemes is to protect the programmer from himself. 
Restrict the user by giving him the minimal amount of information necessary to perform the task
Separate the update from the manner of iteration.

Moving to a functional language where an update can be reified to a function, transcribing the above to Haskell we get:

map ~ forIndividual
map :: (a -> b) -> [a] -> [b]
foldl ~ forAccumulate
foldl :: (a -> b -> a) -> [a] -> b -> [b]
unfoldr ~ forJumpAround
unfoldr :: (a -> Maybe(b, a)) -> a -> [b]
We can abstract these even further, where we generalize the container we iterate over.

No comments:

Post a Comment