Loops Considered Harmful
Yesterday someone from work told me that he was trying to take all the characters in a java.lang.String, and return a string containing a single instance of each of those characters, in sorted order.
He had some straightforward code to do the work, but he had used a boolean array of ASCII bytes, and couldn't handle UniCode chars. In my cleverness, I wanted to show him how to do the work in 2 lines of code, only I immediately started running into limitations within Java.
Why two lines? Well it should be possible to put the contents of a string into an object that can sort them and remove duplicates, and then pull this data back out and put it into a new string. Learning Lisp I've learnt to expect the sort of functionality needed to do this simply and easily. There shouldn't be a need to iterate over the characters, recording the ones in use, and manually sorting. The data being manipulated should be a single "entity", rather than arrays of elements that require iterative techniques to manipulate. This functionality should all be available, making the final function a trivial call to just a few methods. As Abelson and Sussman said, "Programs must be written for people to read, and only incidentally for machines to execute." Iteration, sorting, and other mechanical operations should all be services found in lower levels of the code, and abstracted away.
Incidentally, this is exactly the sort of thing that is done all the time with the STL in C++. Because all of the collection classes (and arrays) meet the required interfaces, then almost any data type can be used in any position. All you need here are algorithms for sorting and removing duplicates, feeding in a string and getting one out the other side. Admittedly, C++ contains language features which allow significant abuse (and I've seen it abused quite badly), but it also allows for some very elegant code. Since C++/STL is an "unsafe" language offering some of the functionality you expect to see in Lisp, then this brings to mind the quote from Philip Greenspun: Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified bug-ridden slow implementation of half of Common Lisp.
Back to Java, the obvious way to handle a problem like this is with a java.util.SortedSet (the only implementation of this in java.util.* is TreeSet). I just had to get the characters out of the string, insert them into the SortedSet and get them back out again, in String form. You'd think this would be easy, but I encountered several problems, showing up problems in the Java libraries, and even the Java language.
The String, the characters retrieved from it, and the sorted set of characters should all form "entities", which are simply different representations of exactly the same data. Since Java and its libraries expect each of these representations at different times, it should be easy and trivial to go from one representation to another. However, this isn't the case.Strings can provide their contents as an array of char. However, these SortedSets need to take objects as their basic elements. (I understand why the language is built this way, but it still frustrates me that I can't declare a SortedSet<char>.) The object that wraps a char is java.lang.Character, so the array of chars will need to be converted to Characters before they could be put into a SortedSet. Also, since we want to treat the data as a single entity, we want to avoid iterating through the data, and instead insert the entire entity into the SortedSet. This means converting a char[] into a Character[].
Autoboxing
While Java 5 now supports autoboxing between native types and their associated objects, there is no way to convert an array of a native type into an array of associated objects. Since arrays are a part of the language, and not an accessible class, there is no way to extend arrays into doing this either. Instead, a loop must be written to iterate through one array, converting the elements to the types in the other array. This is an easy thing to do, but it's the kind of fundamental operation that should be found in a library, rather than being re-implemented by every developer.
So the first thing I had to do was write a method to autobox a char[] into a Character[] and another method to unbox it back again. These are quite trivial:
private static final Character[] toCharacters(char[] chars) {
Character[] characters = new Character[chars.length];
for (int i = 0; i < chars.length; i++) characters[i] = chars[i];
return characters;
}
private static final char[] toChars(Character[] characters) {
char[] chars = new char[characters.length];
for (int i = 0; i < characters.length; i++) chars[i] = characters[i];
return chars;
}java.lang.Character objects, rather than the char values that come from a String. Unfortunately, Java arrays are not compatible with the collections classes (unlike other languages, like Python, or C++ when using the STL), so the array needs further conversion still. This time there is a utility to convert an array into a collection-compatible object, called java.util.Arrays.asList(). So now I can finally put the string into a SortedSet:SortedSet charSet = new TreeSet<Character>(
Arrays.asList(toCharacters(inputString.toCharArray()))); java.util.Collection interface also specifies the toArray() method for converting the collection into an array, so it is possible to move back this way as well. However, the String class still needs to work with char rather than java.lang.Character, so the array unboxing method above is needed to convert this way:public static String sortedWithoutDuplicates(String inputString) {
SortedSet<Character> charSet =
new TreeSet<Character>(
Arrays.asList(toCharacters(inputString.toCharArray())));
return new String(
toChars(charSet.toArray(new Character[charSet.size()])));
}toCharacters()to convert thechar[]frominputString.toCharArray()to aCharacter[].Arrays.asList()to convert theCharacter[]to aList<Character>
String.toCharacterArray(). With just those two changes the first line would instead be: SortedSet<Character> charSet =
new TreeSet<Character>(inputString.toCharacterArray());java.util.Collection<E>defines the methods:<T> T[] toArray(T[] a)Object toArray()
Character[], but this means we need to create the array manually before calling the method.toChars()to convert theCharacter[]into achar[]for theStringconstructor.
Object toArray() method had be redefined into: E[] toArray(). I can't see why this change wasn't made with the release of generics, since E[] is still a valid Object[], and the other method got redefined this way when generics came out. I'd also like to see String accept a Character[] in a constructor, in the same way I'm looking for a String.toCharacterArray() method. These changes would make the second line look like: return new String(charSet.toArray());toCharacters(), toChars() and the mess in sortedWithoutDuplicates()) into the following single method:public static String sortedWithoutDuplicates(String inputString) {
SortedSet<Character> charSet =
new TreeSet<Character>(inputString.toCharacterArray());
return new String(charSet.toArray());
}TreeSet<Character> should take a String, nor should a String constructor accept a SortedSet<Character>. These operations are too specific to the described task, and do not merit inclusion in a standard library. In particular, they would only apply if the wrapped type of the SortedSet is Character, and would break down on other types.Why would I make suggestions about modifications to the standard libraries? While we have to work with them, we shouldn't just lie down and accept the shortcomings of Java. It doesn't happen all the time, but Sun do listen to suggestions on the language and libraries, particularly when suggestions extend the standard libraries without breaking them. Also, if they ever release Java as open source software, then we will have an opportunity to make contributions which may even get accepted.
