Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Porting extensible array indexing (Ix and family) to Java

Although I consider myself an lower-intermediate Haskeller (understand RankNTypes, but struggle with arrow "proc" notation), I am even more noobish at Java. Nevertheless, I decided that the one thing I couldn't do without in Java was something akin to the Ix type class and Haskell's flexibly indexed arrays. I set out to make my own, but I've come right smack up against my own lack of experience. Can anyone give me any advice or pointers on this task? Am I going about it all wrong, or do I have the right idea? Does the Java SE 7 Platform already have something like this that I somehow missed? Has someone else already done this?

I have the following interface simulating the Ix type class:

public interface Ix<T extends Ix<T>> {
    int indexIn(IxRange<T> range);
    boolean isIn(IxRange<T> range);
    boolean isFirstIn(IxRange<T> range);
    boolean isLastIn(IxRange<T> range);
    T nextIndexIn(IxRange<T> range);
    T prevIndexIn(IxRange<T> range);
    IxRange<T> maxRange();
}

I couldn't copy the original type class exactly due to lack of static methods in interfaces, as usual with Java, but I think this is a reasonable way around that (other than maxRange(), which just bugs me). If anyone has any better ideas, please tell me.

Since I didn't have tuples available (I don't want to depend on FunctionalJava), I made the following class (Ix<T> methods, among others, omitted).

public class IxRange<T extends Ix<T>> implements Ix<IxRange<T>> {
    public final T lowerBound;
    public final T upperBound;

    public IxRange(T lB,T uB) {
        lowerBound = lB;
        upperBound = uB;
    }

    public int rangeSize() {
        return upperBound.indexIn(this) - lowerBound.indexIn(this);
    }
}

I then have a class that begins like this:

public class FlexArray<I extends Ix<I>,E> extends AbstractList<E> implements Cloneable

This is where I am having the most trouble, primarily, but by no means exclusively, due to needing an instance first in order to call maxRange() (gah!). I also have several wrapper classes for common types that implement the Ix<T> interface, but that's an auxiliary concern.

To sum up, I am looking for advice on how to proceed, and, if possible, how to refactor Ix<I> to get rid of maxRange() and replace it with something better. General thoughts on the task are welcome as well, but are not the point of this question.

like image 707
Ptharien's Flame Avatar asked Dec 04 '25 13:12

Ptharien's Flame


1 Answers

My approach would be to use "first class typeclasses" also known as the "concept pattern" you dont get inference, and it isnt exactly as clean as using an oo interface directly, but makes more sense when you need to have things like binary methods. You can completely avoid the "curiously recurring generic pattern" (Ix<T extends Ix<T>>) which simplifies things, but at the expense of needing to pass the dictionaries by hand

public interface Ix<A>{
   public List<A> range(A start,A end);
   public int index(A start,A end,A el);
   public boolean inRange(A start,A end,A el);
   public int rangeSize(A start,A end);
}

To use this, you just create your "instances" like you would in Haskell

public class IxInteger extends Ix<Integer>{
    //use the singelton pattern 
    private static IxInteger instance = new IxInteger();
    public static IxInteger getInstance(){
       return instance;
    }
    private IxInteger(){
       //most likely doesn't need to do anything
    }
    //implement the typeclass
    public List<Integer> range(Integer start,Integer end){
       List<Integer> list = new ArrayList<Integer>(end-start);
       for(int i = start; i < end; i++){
           list.add(i);
       }
       return list;
    }
    ...
}

You then just pass the dictionary in whenever you need it.

public Foo ixFoo<A>(args..,Ix<A> ixDict){
   // do stuff
   ...
   // and when you need the dictionary
   myList = ixDict.range(start,end);
   ...
}

Edit: One problem is that when translating code sometimes you do stupid things. In Haskell [a] is used as a sort of universal interface to iterable collections. This doesn't really work in strict languages. So, one should probably replace the use of List<A> in my code with an iterator. It is best to retain the laziness in times like this.

like image 150
Philip JF Avatar answered Dec 07 '25 04:12

Philip JF



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!