On 05/09/2011 07:17 PM, Orchid XP v8 wrote:

> While the identifier names are strongly suggestive, I doubt anybody not
> mildly fuent in Haskell is going to figure out what's actually going on
> here. I'll post a Java translation in a minute. Then we can see whether
> the program becomes clearer (i.e., Haskell is the problem) or remains
> opaque (i.e., the algorithm is the problem).

OK, so attempting to compare like for like, here's the most "natural" 
way I could think of to implement this in Java:

   public abstract class MinHeap
   {
     public abstract bool is_empty();
     public abstract int top();
     public abstract MinHeap insert(int x);
     public abstract MinHeap delete_top();
     public abstract MinHeap union(MinHeap h);
     public abstract int size();
   }

   public class MinHeap_Emtpy extends MinHeap
   {
     private MinHeap_Empty() {}
     public static MinHeap_Empty empty = new MinHeap_Empty();

     public bool is_empty() {return true;}

     public int top() // Throw exception

     public MinHeap insert(int x)
     {return new MinHeap_Node(x, null, null);}

     public MinHeap delete_top() // Throw exception

     public MinHeap union(MinHeap h) {return h;}

     public int size() {return 0;}
   }

   public class MinHeap_Node extends MinHeap
   {
     public int datum;
     public MinHeap child0, child1;

     public bool is_empty() {return false;}
     public int top() {return this.datum;}

     public MinHeap insert(int x)
     {
       let h = this.datum;
       let l = x;
       if (h < l) {h = x; l = this.datum;}
       return new MinHeap_Node(l, this.child1.insert(h), this.child0);
     }

     public MinHeap delete_top() {return this.child0.union(this.child1);}

     public MinHeap union(MinHeap h)
     {
       if (h.is_empty()) return this;

       MinHeap_Node that = (MinHeap_Node)h;

       if (this.datum < that.datum)
       return new MinHeap_Node(this.datum, that, this.delete_top());
       return new MinHeap_Node(that.datum, this, that.delete_top());
     }

     public int size()
     {return 1 + this.child0.size() + this.child1.size();}
   }

Differences:
- I don't know how Java does generics, so this min-heap handles int only.
- I left out the list conversion stuff, because I'm not sure about 
Java's container types off the top of my head. The "idiomatic" way is 
probably to define an interator or something anyway...
- It's a while since I did Java. This might not actually compile for one 
reason or other. (In particular, I'm fuzzy on how auto-constructors work...)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message