Login | Register   
LinkedIn
Google+
Twitter
RSS Feed
Download our iPhone app
TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK
Browse DevX
Sign up for e-mail newsletters from DevX


advertisement
 

Build an Embedded Array Language in Java  : Page 2

This article describes a generalized system for dealing with multidimensional arrays of data. It lets you transform and extract slices of data along various axes with very little code, in the style of the programming language APL. And you're not limited to numerical data; you can generalize systems such as this to any kind of tabular data.


advertisement
Creating a Cube
First, let's start with some data. Here's a typical array of data:

Integer data[] = { 10, 20, 30 };

It's easy to turn this into a one-dimensional cube:

Cube cube = new Cube( data );

 
Figure 1. A One-dimensional cube: Here's how you might visualize the data in a one-dimensional cube.
Figure 1 shows how the data would look inside the cube:

It's just a coincidence that I put 10 in slot 0, 20 in slot 1, and 30 in slot 2. I'm going to do this to make the data nice and uniform so it's easy to see what's happening to it; in real life, it would be more like real data.

Modifying Data
One thing you can do with a cube is reverse it along the first axis, for example:



Cube r = cube.reverse();

 
Figure 2: Reversed Cube: If you reverse the data in Figure 1, you get this cube.
This returns a new Cube that looks like Figure 2:

Note that I said "returns a new Cube." This class was written in a functional style. In this context, that means that an object's method returns a new object, rather than modifying itself. This may seem a little strange, but in the context of array programming, it's very useful. It's an idea borrowed from other programming languages (and array languages like APL in particular), but it works just fine in Java.

The Map Operation
A map is an operation in which you apply a function to each element of a list. The result of a map is the list of the outputs of each function call. For example, you can map a function called 'doubler' across the Cube object, resulting in a cube that looks like Figure 3.

 
Figure 3. A Doubled Cube: The figure shows the results after doubling the cube values in Figure 1.

Cube d = cube.map( doubler );

But what is doubler? It isn't a function, exactly, since you can't pass those around in Java. Rather, it's a simple object that contains a single function:

Fun doubler = new Fun<Integer>() { public Integer apply( Integer n ) { return n 2; } };

The doubler class implements the Fun interface, which has a single method called apply(). Apply takes an object of some time, modifies it, and returns the modified version. A Fun is a value transformer; in this case, the transformation takes a number and doubles it. When you hand this Fun to the map() method, it applies the transformation to the whole cube, doubling each cell.

The Fold Operation
A fold is another useful operation you can apply to a multidimensional array. Whereas a map takes an N-dimensional array and returns another N-dimensional array, a fold takes an N-dimensional array and returns an (N-1)-dimensional array. That is to say, it collapses the cube along one dimension.

Here's an example. Going back to the original [10 20 30] array, you can fold it like this:

Integer data[] = { 10, 20, 30 } Cube cube = new Cube( data ); int sum = cube.fold( plus, 0 );

The result—10+20+30 = 60—gets stored in the integer variable sum. So, that adds up all the elements of the array. But how did it turn a fold (whatever that is) into a sum?

The method call was fold( plus, 0 ). One way to look at this is:

int sum = 0; // 0 sum = plus( sum, 30 ); // 30 = 0+30 sum = plus( sum, 20 ); // 50 = 20+30 sum = plus( sum, 10 ); // 60 = 10+50

In other words, the code contracts the array by repeatedly calling plus. You can also look at this in a more functional style:

int sum = plus( 10, plus( 20, plus( 30, 0 ) ) );

Or, using the '+' operator:

int sum = 10 + (20 + (30 + 0));

The cool thing about fold is that you can use different functions and get different, useful results. For example, if you wanted the product instead of the sum, you could just use 'times' and '1' instead of 'plus' and '0':

Integer data[] = { 10, 20, 30 } Cube cube = new Cube( data ); Integer product = cube.fold( times, 1 );

The preceding code returns 10 (20 (30 1)), or 6000. Of course, you need to define plus and times. You'd do that in much the same way as doubler, except that you use a function that takes two arguments, rather than one:

Fun2 plus = new Fun2<Integer>() { public Integer apply( Integer a, Integer b ) { return a + b; } }; Fun2 times = new Fun2<Integer>() { public Integer apply( Integer a, Integer b ) { return a b; } };

Admittedly, these definitions are a bit wordy, but the great thing is that they are reusable. It's easy to create a library of mappers and folders that you can refer to by name throughout your code.

Folding Left and Right
The folds shown in the previous section aren't the only way to fold; in fact, there are two different kinds of fold: left folds and right folds.

The folds in the last section were right folds (also known as foldr), which are the default type. In other words, fold() really means foldr(). When you do a right fold, you combine the elements from right to left, for example:

Integer data[] = { 10, 20, 30 } Cube cube = new Cube( data ); int sum = cube.foldr( plus, 0 );

Thus, a right fold as shown above is the same as:

int sum = 10 + (20 + (30 + 0)); // 60

But you could also do a left fold (also known as foldl), which adds the numbers from left to right:

Integer data[] = { 10, 20, 30 } Cube cube = new Cube( data ); int sum = cube.foldl( plus, 0 );

And that's the same as:

int sum = ((0 + 10) + 20) + 30; // 60

Obviously, if you're just adding, you'll get the same answer from the left fold as from the right fold, because addition is associative—that is, (a + b) + c is the same as a + (b + c). But division isn't associative; what do you get in that case?

Float data[] = { 10F, 20F, 30F, 40F }; Cube cube = new Cube( data ); float sum_right = (Float)cube.foldr( dividedby, 1F ); float sum_left = (Float)cube.foldl( dividedby, 1F );

The preceding code results in 0.375 for sum_right, and 2.6666667 for sum_left.



Comment and Contribute

 

 

 

 

 


(Maximum characters: 1200). You have 1200 characters left.

 

 

Sitemap