Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

(OT) The Schwartzian Transform in Java

by djantzen (Priest)
on Jun 10, 2003 at 12:33 UTC ( #264648=perlmeditation: print w/ replies, xml ) Need Help??

Hi All. The following is a simple but demonstrative example of the Schwartzian Transform written in Java. It should compile and run with the latest version of Perl Idioms for Java. Enjoy!

import java.util.ArrayList; import java.util.Comparator; import java.util.List; import perlforjava.control.Looper; import perlforjava.functions.Arrays; import perlforjava.functions.Mapper; import perlforjava.lang.Block; public class TheSchwartz { public static void main(String[] args) { // Create a new List of values to sort ArrayList in = new ArrayList(); in.add("foobarbazquux"); in.add("foo"); in.add("foobarbaz"); in.add("foobar"); /* Sort based upon length of string by mapping each string to a List where the first element is the string and the second + is its length. Sort on the latter and return a new List of str +ings. */ List out = Mapper.map(new Block() { protected Object process(Object elem) { return ((List)elem).get(0); } // pull the first element from each List and return it }, Arrays.sort(new Comparator() { public int compare(Object a, Object b) { return ((Integer)((List)a).get(1)). compareTo(((Integer)((List)b).get(1))); } // run the comparison of Integer values to determin +e order }, Mapper.map(new Block() { protected Object process(Object elem) { ArrayList temp = new ArrayList(); temp.add(elem); temp.add(new Integer(((String)elem).length())); return temp; } // map each string into an ArrayList of string +=> length }, in) // end second map ) // end sort ); // end first map // Loop over the results to view them Looper.foreach(out, new Block() { protected Object process(Object elem) { System.out.println("ELEM " + elem.toString()); return null; } } ); // end foreach } }

The equivalent Perl code is rather more brief, demonstrating the claim all programs will eventually be reduced to Perl one-liners :^p Update: added parentheses, though not required, to better see the similarities between implementations1.

use strict; use warnings; my @in = qw/foobarbazquux foo foobarbaz foobar/; my @out = map( { $_->[0] } sort( { $a->[1] <=> $b->[1] } map( { [$_, length($_)] } @in ) ) ); foreach (@out) { print "$_\n"; }

To be fair however, the verbosity of the Java code is a requirement of (at least) its strong typing which necessitates all that casting, and the prohibition against method overloading on the basis of method return value. Sloppier import statements can also reduce the line count but I've opted for clarity. And of course the biggest reason is the lack of user defined blocks except through anonymous inner classes.

1. The original perl code was: my @out = map { $_->[0] } sort { $a->[1] <=> $b->[1] } map { [$_, length($_)] } @in;


"The dead do not recognize context" -- Kai, Lexx

Comment on (OT) The Schwartzian Transform in Java
Select or Download Code
Re: (OT) The Schwartzian Transform in Java
by hardburn (Abbot) on Jun 10, 2003 at 13:57 UTC

    Dear Lord

      Not 'Dear Lord' but 'My Dear Hands'. Java, the surest route to RSI that I know of.

      --tidiness is the memory loss of environmental mnemonics

        Java, the surest route to RSI that I know of.

        No, that would be COBOL.

        90% of every Perl application is already written.
        dragonchild
Re: (OT) The Schwartzian Transform in Java
by Mr. Muskrat (Abbot) on Jun 10, 2003 at 14:05 UTC

    use TheSchwartz;

Re: (OT) The Schwartzian Transform in Java
by teabag (Pilgrim) on Jun 10, 2003 at 14:13 UTC
    That will get you a place on the Altar of Unholy Blasphemy!
    That is, if he doesn't get to you first...

    Teabag
    Sure there's more than one way, but one just needs one anyway - Teabag

        Permit me a {grin} :^) My partner in crime, icmf3, suggested the exercise as a good test that we were on the right track with the project, and I was all too happy to find out.


        "The dead do not recognize context" -- Kai, Lexx

      Now that is a certificate I would hang on my wall! :^)


      "The dead do not recognize context" -- Kai, Lexx
Re: (OT) The Schwartzian Transform in Java
by Juerd (Abbot) on Jun 10, 2003 at 14:23 UTC

    With proper indenting it looks a lot better and doesn't need "end foreach"-like comments (if you ever feel you need comments that say what you're ending, fix your style instead!!).

    Rule of thumb: always let the thing that causes the indentation be the last on a line. Another rule of thumb: align closing parens/brackets with the indentation of the line that caused indentation.
    So don't use:

    somefunction( foo(bar, "Hello World", ) // end of foo ); // end of somefunction
    But instead use:
    somefunction( foo( bar, "Hello World", ) );
    You may or may not like it, but I find it much better readable.

    import java.util.ArrayList; import java.util.Comparator; import java.util.List; import perlforjava.control.Looper; import perlforjava.functions.Arrays; import perlforjava.functions.Mapper; import perlforjava.lang.Block; public class TheSchwartz { public static void main(String[] args) { // Create a new List of values to sort ArrayList in = new ArrayList(); in.add("foobarbazquux"); in.add("foo"); in.add("foobarbaz"); in.add("foobar"); /* Sort based upon length of string by mapping each string to a List where the first element is the string and the second + is its length. Sort on the latter and return a new List of str +ings. */ List out = Mapper.map( new Block() { // pull the first element from each List and return it protected Object process(Object elem) { return ((List)elem).get(0); } }, Arrays.sort( // run the comparison of Integer values to determine o +rder new Comparator() { public int compare(Object a, Object b) { return ((Integer)((List)a).get(1)). compareTo(((Integer)((List)b).get(1))); } }, // map each string into an ArrayList of string => leng +th Mapper.map( new Block() { protected Object process(Object elem) { ArrayList temp = new ArrayList(); temp.add(elem); temp.add(new Integer(((String)elem).length +())); return temp; } }, in ) ) ); // Loop over the results to view them Looper.foreach( out, new Block() { protected Object process(Object elem) { System.out.println("ELEM " + elem.toString()); return null; } } ); } }

    But indeed, Perl is much nicer towards programmers anyway.

    Juerd # { site => 'juerd.nl', plp_site => 'plp.juerd.nl', do_not_use => 'spamtrap' }

      Good points, the original indenting is the result of emacs' java-mode, which obviously is dictated by the syntactical structure of the code. I thought perhaps that it would help others see the implementation, but your version definitely reads better. Thanks juerd.


      "The dead do not recognize context" -- Kai, Lexx
      The problem isn't with the comments, it's with throwing everything into one big main() method. Why throw away code when with a little bit more work you can give it some real power?
      import java.util.ArrayList; import java.util.Comparator; import java.util.List; import perlforjava.control.Looper; import perlforjava.functions.Arrays; import perlforjava.functions.Mapper; import perlforjava.lang.Block; /** * The Schwartzian Transform written in Java. */ public class TheSchwartz { private ArrayList list; /** * Comparator to sort by length. */ public final static Comparator BY_LENGTH; /** * Comparator to sort alphabetically. */ public final static Comparator ALPHABETICALLY; /** * Static initializer */ static { BY_LENGTH = new Comparator() { public int compare(Object a, Object b) { return ((Integer) ((List) a).get(1)).compareTo( ((Integer) ((List) b).get(1))); } }; ALPHABETICALLY = new Comparator() { public int compare(Object a, Object b) { String s1 = a.toString().substring(1); String s2 = b.toString().substring(1); return s1.compareTo(s2); } }; } /** * Simple Constructor. * * @param list */ public TheSchwartz(ArrayList list) { this.list = list; } /** * Workhorse function. Sorting by passed in Comparator * * @return */ public ArrayList sort(Comparator sortBy) { List out = Mapper.map(new Block() { // pull the first element from each List and return it protected Object process(Object elem) { return ((List) elem).get(0); } }, Arrays.sort( // run the comparison of Integer values to determine o +rder sortBy, // map each string into an ArrayList of string => length Mapper.map(new Block() { protected Object process(Object elem) { ArrayList temp = new ArrayList(); temp.add(elem); temp.add(new Integer(((String) elem).length())); return temp; } }, list))); return (ArrayList)out; } public static void main(String[] args) { // Create a new List of values to sort ArrayList in = new ArrayList(); in.add("fu"); in.add("duhh"); in.add("birdy"); in.add("sea"); /* Sort based upon length of string by mapping each string to a List where the first element is the string and the second + is its length. Sort on the latter and return a new List of str +ings. */ TheSchwartz merlyn = new TheSchwartz(in); List outByLength = merlyn.sort(TheSchwartz.BY_LENGTH); System.out.println("By Length:"); // Loop over the results to view them Looper.foreach(outByLength, new Block() { protected Object process(Object elem) { System.out.println("ELEM " + elem.toString()); return null; } }); System.out.println("\nAlphabetically:"); List outAlphabetically = merlyn.sort(TheSchwartz.ALPHABETICALL +Y); // Loop over the results to view them Looper.foreach(outAlphabetically, new Block() { protected Object process(Object elem) { System.out.println("ELEM " + elem.toString()); return null; } }); } }
      Fun post.
      ()-()             
       \"/              
        `              
      

        The problem isn't with the comments

        The readability problem wasn't the comments. I rearranged those too, but the real problem was having screwed up indenting (closing paren lined up with opening paren). The comments "end of foreach" and "end of sort" were just signs of bad style, not the bad style itself.

        As for your code: I hate /* */ comments :)

        Juerd # { site => 'juerd.nl', plp_site => 'plp.juerd.nl', do_not_use => 'spamtrap' }

        Nice ignatz! I was merely shooting for a minimalist example in my OP, but this is a great demo of a more realistic application of the idea. I like the encapsulation of the core routine and the use of static Comparators to facilitate ease of use. And of course since public sort method can take any Comparator, using it in custom applications would be a breeze. The one part that concerns me is that the map that does the initial setup isn't always going to be the same (string => length), so there needs to be some way of conveying dynamic behavior for that aspect through the public sort method. Writing a general wrapper in Perl for the ST you'd probably pass a subroutine reference; in Java you'd probably have to pass an object or break the rules and pass a java.lang.reflect.Method. Hmmm, actually, that latter option probably would work:

        sort(Comparator c, Method prepare) .... .... // The second map would then look something like this map(new Block() { protected Object process(Object elem) { ArrayList temp = new ArrayList(); temp.add(elem); try { temp.add(prepare.invoke(elem, null)); // or possibly with ar +gs; } catch (Exception e) { // for real we'd catch finer grained exceptions and // do something smart } }, in);

        This does work, I just passed in the result of String.class.getMethod("length", null) and it ran as expected :^) Of course one limitation is the assumption that the transformation to be run on the element exists as an instance method. Probably this measure could be omitted for the first map as in basically all cases you just want to pull out the first element.


        "The dead do not recognize context" -- Kai, Lexx
Re: (OT) The Schwartzian Transform in Java
by hding (Chaplain) on Jun 10, 2003 at 18:03 UTC

    To be fair however, the verbosity of the Java code is a requirement of (at least) its strong typing which necessitates all that casting...

    To be fair to strongly typed languages, we should note that this is characteristic of only some of them, and that in others (e.g. an ML) type inferencing would take care of all the casting problems.

Re: (OT) The Schwartzian Transform in Java
by fletcher_the_dog (Friar) on Jun 10, 2003 at 21:14 UTC
    Please excuse my ignorance, but what is so cool about the Schwartzian Transform? All I can tell that it does is sort words by length. It seems that if that is all you wanted to do you could just do:
    my @in = qw/foobarbazquux boo foobarbaz foobar/; my @out=sort {length($a) <=> length($b)} @in; foreach (@out) { print "$_\n"; }
    What am I missing?

      This is only one very simple use of the Transform intended to demonstrate that it can be done in Java. You are correct that the problem as described is better solved in your code sample. The point of the Transform is to precompute expensive values to make the sort go faster. The general form is map, sort, map, but the bodies of those function calls may do whatever you want. A common example is sorting files based upon size:

      @sorted_by_size = map { $_->[0] } sort { $a->[1] <=> $b->[1] } map { [$_, -s] } @files;

      HTH, djantzen


      "The dead do not recognize context" -- Kai, Lexx

        I was originally going to comment that I hated the style that you had used for the ST in your original code. But here you have it more or less as I would write it. Cool. :-) I find that emphasizing the bottom to top, or right to left effect of the chain, with as minimal obscuring parenthesis to be much more readable. And this is the point that most people get confused with about ST's and chaining list operators, the information flows right to left at first this can seem odd, but to me it makes total sense, in that the information flow involves an explicit or implicit assignment. Assignments are left associative, and flow to the left. However from the method invocation POV the right to leftness confounds their usual expectation of left to rightness. For instance in an oo language we might expect an ST to be written like (and i believe Ruby does it close to this)

        @newfiles=@files.map([-s($_),$_]).sort($a->[0]<=>b->[0]).map(pop @$_);

        but since we arent doing method invocation, but rather using list operators in an assignment statement we end up with the at first weird looking bottom to top, right to left. (here i was going to say "it wouldnt be hard to write an OO implementation", but I ended up writing a proof of concept instead, and I can say it wasnt that hard, except for some unexpected nonsense with sort.) Here it is:

        package main; my @x=Array->new( qw( bb cccc ddd aaaaa fffff qqq xxx iiiii ) ) ->map('[length($_), $_ ]') ->sort('$b->[0] <=> $a->[0] || $a->[1] cmp $b->[1]') ->map('pop @$_'); print "@x";

        So theres a perl OO implementation of the list operators in perl. :-) I kinda got carried away, sorry. :-) (The rest of this mail is what I originally intended to post, somehow this has become a major digression. My apologies.)

        Also, I have a little personal rule with ST's. I always put the payload on the end. This way your code becomes

        @sorted_by_size = map { pop @$_ } sort { $a->[0] <=> $b->[0] } map { [-s $_ , $_ ] } @files;

        I do this because if you need to add sort criteria you can, but when you see the criteria in a list, like:

        @sorted_by_ext_name_size = map { pop @$_ } sort { $a->[0] cmp $b->[0] || $a->[1] cmp $b->[1] || $a->[2] <=> $b->[2] || 0 } map { [reverse(lc($_)=~/([^\\\/]+?)(\.[^.]+)?$/),-s($_),$_ ] } @files=glob ('c:/winnt/*.*'); print join(",\n",@files); print join(",\n",@sorted_by_ext_name_size);

        You see all the slots. I suppose you could do it the otherway round, but then you have to say { shift @$_} or { $_->[0] } but I find { pop @$_ } is easier to type and somehow more suggestive of the underlying idea. The stylized way I wrote this is meant to make changing the criteria easier. By putting the 0 at the end, lines can be rearranged without worrying, and it has no real performance effect afaict. (For instance to remove the need for the reverse statement, all you need is a single cut and paste to reorder the sort criteria. Its to make this point that I put it in. :-)

        Anyway, just thought Id throw my 2 cents in. I know other people have other preferences, and as long as they are readable I dont mind that much. :-)
        ---
        demerphq

        <Elian> And I do take a kind of perverse pleasure in having an OO assembly language...

      The Schwartzian Transform is a sorting technique (not just for sorting by length), that keeps you from having to keep from repeatedly calling a potentially slow expensive function in a sort. For more details be sure to check out this and the column on sorting merlyn has listed there.

      -enlil

Re: (OT) The Schwartzian Transform in Java
by Ovid (Cardinal) on Jun 10, 2003 at 23:00 UTC

    And just to make it clear that dynamically typed languages have it all over statically typed languages, here's an ST in python to guarantee a stable sort:

    def stable_sort(some_list, indices=xrange(sys.maxint)): decorated = zip(list,indices) decorated.sort return [item for item, index in decorated]

    In fact, in the Python Cookbook, this is even referred to as a Schwartzian Transform.

    Cheers,
    Ovid

    New address of my CGI Course.
    Silence is Evil (feel free to copy and distribute widely - note copyright text)

Re: (OT) The Schwartzian Transform in Java
by Anonymous Monk on Jun 11, 2003 at 05:38 UTC

    This isn't off-topic at all, it's the greatest single piece of Perl advocacy I've read! heh ;-)

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://264648]
Approved by cciulla
Front-paged by broquaint
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (7)
As of 2014-08-29 21:49 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (289 votes), past polls