ML/(Strict) Haskell in Java
This is from an actual real project. It makes use of persistent immutable data structures and uses recursion even when not necessary. Actually, it's more like Kore (the language the project implements) in Java, but the style is basically the same as ML. But the philosophy of Kore is that the author shouldn't format his code, so none of the Java code is formatted either (it's autoformatted by eclipse).
drop n elements from a list:
public static <T> List<T> drop(List<T> l, Integer n) {
return n == 0 ? l : drop(l.cons().tail, n - 1);
}
In ML/Haskell, where you'd pattern match to extract the head and tail, here you say list.cons().x and list.cons().tail.
insert an element in a list:
public static <T> List<T> insert(List<T> l, Integer i, T x) {
if (i == 0)
return cons(x, l);
return cons(l.cons().x, insert(l.cons().tail, i - 1, x));
}
List is defined literally how the algebraic datatype would be defined. Here is a version with the eclipse-generated boilerplate removed:
public final class List<T> {
public static final class Nil<T> {
}
public static final class Cons<T> {
public final T x;
public final List<T> tail;
public Cons(T x, List<T> tail) {
if (x == null)
throw new RuntimeException("null head");
if (tail == null)
throw new RuntimeException("null tail");
this.x = x;
this.tail = tail;
}
}
private final Nil<T> nil;
private final Cons<T> cons;
private List(Nil<T> nil, Cons<T> cons) {
this.nil = nil;
this.cons = cons;
}
public boolean isEmpty() {
return nil != null;
}
public Nil<T> nil() {
if (nil == null)
throw new RuntimeException("not nil");
return nil;
}
public Cons<T> cons() {
if (cons == null)
throw new RuntimeException("not cons");
return cons;
}
public static <T> List<T> cons(Cons<T> cons) {
if (cons == null)
throw new RuntimeException("constructor received null");
return new List<T>(null, cons);
}
public static <T> List<T> nil(Nil<T> nil) {
if (nil == null)
throw new RuntimeException("constructor received null");
return new List<T>(nil, null);
}
}
Here is a map data structure implemented in terms of a trie:
public final class Map<K, V> {
private final Tree<Character, Optional<Pair<K, V>>> tree;
// keys are sorted in reverse order so entrySet can use cons instead of append
private final Comparer<Pair<Character, Tree<Character, Optional<Pair<K, V>>>>> comparer =
new PairLeftComparer<Character, Tree<Character, Optional<Pair<K, V>>>>(
new ReverseComparer<Character>(new CharacterComparer()));
private Map(Tree<Character, Optional<Pair<K, V>>> tree) {
this.tree = tree;
}
public static <K, V> Map<K, V> empty() {
return new Map<K, V>(new Tree<Character, Optional<Pair<K, V>>>(
OptionalUtils.<Pair<K, V>> nothing(),
ListUtils
.<Pair<Character, Tree<Character, Optional<Pair<K, V>>>>> nil()));
}
public Optional<V> get(K k) {
Tree<Character, Optional<Pair<K, V>>> t = tree;
for (char c : k.toString().toCharArray()) {
Tree<Character, Optional<Pair<K, V>>> t2 = getEdge(t, c);
if (t2 == null)
return nothing();
t = t2;
}
if (t.v.isNothing())
return nothing();
return some(t.v.some().x.y);
}
public Map<K, V> put(K k, V v) {
return new Map<K, V>(put(tree, k.toString(), v, k));
}
private Tree<Character, Optional<Pair<K, V>>> put(
Tree<Character, Optional<Pair<K, V>>> t, String s, V v, K k) {
if (s.equals(""))
return new Tree<Character, Optional<Pair<K, V>>>(some(Pair.pair(k, v)),
t.edges);
char c = s.charAt(0);
Tree<Character, Optional<Pair<K, V>>> t2 = getEdge(t, c);
if (t2 == null)
return new Tree<Character, Optional<Pair<K, V>>>(
t.v,
sort(
cons(
pair(
c,
put(new Tree<Character, Optional<Pair<K, V>>>(
OptionalUtils.<Pair<K, V>> nothing(),
ListUtils
.<Pair<Character, Tree<Character, Optional<Pair<K, V>>>>> nil()),
s.substring(1), v, k)), t.edges), comparer));
return new Tree<Character, Optional<Pair<K, V>>>(t.v, sort(
replace(pair(c, put(t2, s.substring(1), v, k)), t.edges), comparer));
}
private List<Pair<Character, Tree<Character, Optional<Pair<K, V>>>>> replace(
Pair<Character, Tree<Character, Optional<Pair<K, V>>>> edge,
List<Pair<Character, Tree<Character, Optional<Pair<K, V>>>>> edges) {
if (edges.cons().x.x.equals(edge.x))
return cons(edge, edges.cons().tail);
return cons(edges.cons().x, replace(edge, edges.cons().tail));
}
// I consider this O(1). There are a constant of 2^16 values of
// char. Either way it's unusual to have a large amount of
// edges since only ASCII chars are typically used.
private Tree<Character, Optional<Pair<K, V>>> getEdge(
Tree<Character, Optional<Pair<K, V>>> t, char c) {
for (Pair<Character, Tree<Character, Optional<Pair<K, V>>>> p : iter(t.edges))
if (p.x.equals(c))
return p.y;
return null;
}
public Map<K, V> delete(K k) {
return new Map<K, V>(delete(tree, k.toString()).x);
}
private Pair<Tree<Character, Optional<Pair<K, V>>>, Boolean> delete(
Tree<Character, Optional<Pair<K, V>>> t, String k) {
if (k.equals(""))
return pair(
new Tree<Character, Optional<Pair<K, V>>>(
OptionalUtils.<Pair<K, V>> nothing(), t.edges), t.edges.isEmpty());
char c = k.charAt(0);
Tree<Character, Optional<Pair<K, V>>> t2 = getEdge(t, c);
if (t2 == null)
return pair(t, false);
Pair<Tree<Character, Optional<Pair<K, V>>>, Boolean> p =
delete(t2, k.substring(1));
List<Pair<Character, Tree<Character, Optional<Pair<K, V>>>>> edges = nil();
for (Pair<Character, Tree<Character, Optional<Pair<K, V>>>> e : iter(t.edges))
if (!e.x.equals(c))
edges = cons(e, edges);
if (!p.y)
return pair(
new Tree<Character, Optional<Pair<K, V>>>(t.v, cons(pair(c, p.x),
edges)), false);
boolean oneEdge = t.edges.cons().tail.isEmpty();
return pair(new Tree<Character, Optional<Pair<K, V>>>(t.v, edges), oneEdge
&& t.v.isNothing());
}
public static class Entry<K, V> {
public Entry(K k, V v) {
this.k = k;
this.v = v;
}
public final K k;
public final V v;
}
public List<Entry<K, V>> entrySet() {
return entrySet(ListUtils.<Entry<K, V>> nil(), tree);
}
private List<Entry<K, V>> entrySet(List<Entry<K, V>> l,
Tree<Character, Optional<Pair<K, V>>> t) {
if (!t.v.isNothing()) {
Pair<K, V> p = t.v.some().x;
l = cons(new Entry<K, V>(p.x, p.y), l);
}
for (Pair<Character, Tree<Character, Optional<Pair<K, V>>>> e : iter(t.edges))
l = entrySet(l, e.y);
return l;
}
}
The types start to take up as much space as the code. For example, in put, the method has 302 characters of types and 343 characters of code (not counting space/newlines).
but never could quite figure it out. I need to analyze this when I have time...
there are languages which easily allow to express any way of thinking. (LISP family, for example) – Display Name – 2015-07-20T08:07:25.203
1@m.buettner create your file with the extension
.litcoffee. It might help. – Ismael Miguel – 2014-03-20T22:53:44.903A little long (and previously-written; and not self-contained) for an answer, but: Postscript scanner in Postscript in C.
– luser droog – 2014-03-21T04:36:52.550I'd like to clarify that program needs to be correct only in language it't written in (in case of my examples, Java and C), not in language it pretends to be written in. However if it's correct in both, the better! – el.pescado – 2014-03-21T07:13:55.967
@el.pescado Indeed, your Pascal program would compile with the unnecessary brackets in the if statement, but not with the the double == (and obviously not without declaring the variable i.) You might want to edit your question instead of posting as comment. Up to you. Nice question, by the way. – Level River St – 2014-03-21T10:49:15.567
51I don't think you (or the majority of the answers) understand the point of the quote. It's not that a Real Programmer writes code that looks lexically like Fortran even though he's writing in Pascal or LISP: it's that he applies a Fortran way of thinking even when writing in Pascal or LISP; e.g. "As all Real Programmers know, the only useful data structure is the Array.". Great answers would be procedural code in Prolog, functional code in C, object-oriented code in Pascal. – Peter Taylor – 2014-03-21T11:10:57.283
1I hope someone's gonna do a Lisp dialect in, well, anything but another Lisp dialect... – itsjeyd – 2014-03-21T21:23:36.177
I thought real programmers only coded in assembly and machine language (binary) ... – Agi Hammerthief – 2014-03-21T23:22:55.777
I had an assistant prof at Univ (around '87) who was totally into Pascal, and created exactly these #defines in C. – Henk Langeveld – 2014-03-22T20:30:40.327
6
@itsjeyd Greenspun's Tenth Rule Of Programming: "Any sufficiently complicated C or Fortran program contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of CommonLisp."
– Joshua Taylor – 2014-03-25T17:38:42.987@JoshuaTaylor Funny you should mention that - I literally just discovered that quote via http://paulgraham.com/avg.html ... :)
– itsjeyd – 2014-03-25T22:55:16.240@itsjeyd Of course, what's interesting about this problem, is that writing making code in another language work in (Common) Lisp actually isn't too difficult, because it's easy enough to customize the reader, the syntax for symbols is already quite inclusie, and it's easy to wrap things in macros. For instance, in this answer that I wrote, some C/Java style psuedo-code integrates seamlessly in Lisp.
– Joshua Taylor – 2014-03-25T22:58:08.160@PeterTaylor yeah, I tried to do this now... – Display Name – 2014-03-26T00:30:59.947
Somebody do Nimrod/PHP... – cjfaure – 2014-03-26T09:15:20.070
@PeterTaylor, I think mine matches the quote, if not the intent of the question... – Bill Woodger – 2014-03-26T13:16:38.593
How about Objective-C and... oh, wait.. – Max Chuquimia – 2014-03-27T10:14:25.277
@PeterTaylor You are 100% right - the quote is not about the look of the program, it's about the thinking that goes into it. It goes both ways, too - my FORTRAN teacher scolded me once for using nested loops to print 2D arrays. She said, literally, that I shouldn't expect to pass her class if I continue writing Pascal programs in FORTRAN :-) – dasblinkenlight – 2014-03-27T13:04:34.950