Trying to implement Array.min

1

Hi there,

I am trying to extend the standard library with Array.min which would return the smallest value in an Array of ordered values. Like this:

var value = [5, 2, -3, 4].min(); // -3

Ideally it would behave like the Iterator.min method in Rust which operates on iterators of values that satisfy the Ord trait.

I tried using static extensions:

class ArrayExtensions {
	static public function min<T>(arr:Array<T>):T {
		var minValue = arr[0];

		for (i in 1...arr.length) {
			if (arr[i] < minValue) { // Cannot compare min.T and min.T
				minValue = arr[i];
			}
		}

		return minValue;
	}
}

Is it possible to specify to the compiler that a type that can be compared?

I can also constraint the generic type parameter to the common types I will be using:

class ArrayExtensions {
    static public function min<T:Int & Float>(arr:Array<T>):T { // ... }
}

but I can’t seem to make it work:

using ArrayExtensions;

var value = [0.0, 1.0].min(); // Array<Float> has no field min

Is there another way to do this?

Thanks!

2

Hi

min<T:Int & Float> means that the type has to be compatible with both Int AND Float, which is not what you want in this case as Int and Float are not fully compatible with each other.

Probably there are more elegant and robust ways to achieve what you want, but this solution works as expected.

First I created an Abstract of which the underlying type’s values can be compared (Int, Float, and I threw in String as well just to make the example more understandable) by exposing the required type operations.

abstract Comparable(Dynamic) from Int to Int from Float to Float from String to String {
    @:op( A < B )
    static public function lt<T>( a:Comparable, b:Comparable ):Bool;

    @:op( A > B )
    static public function gt<T>( a:Comparable, b:Comparable ):Bool;
}

Then I used this Comparable abstract type as the type parameter in the static extension’s min() function:

class ArrayExtensions {

    static public function min<T:Comparable>( arr:Array<Comparable> ):Comparable {
        var minValue = arr[0];

        // Notice the zero-indexing!
        for (i in 0...arr.length) {
            if (arr[i] < minValue) {
				minValue = arr[i];
			}
		}
        return minValue;
    }
}

Fully working example code:

package;

import haxe.Json;
using Main.ArrayExtensions;

class Main {

    static public function main() {

        var intA:Comparable = 123;
        var intB:Comparable = 456;
        trace( '$intA is smaller than $intB: ${intA < intB}' );
        trace( '$intA is larger than $intB: ${intA > intB}' );

        var floatA:Comparable = 123.456;
        var floatB:Comparable = 789.012;
        trace( '$floatA is smaller than $floatB: ${floatA < floatB}' );
        trace( '$floatA is larger than $floatB: ${floatA > floatB}' );

        var stringA:Comparable = 'Hello';
        var stringB:Comparable = 'World';
        trace( '$stringA is smaller than $stringB: ${stringA < stringB}' );
        trace( '$stringA is larger than $stringB: ${stringA > stringB}' );

        // These won't compile as they are of unsupported types
        // var arrayA:Comparable = [];
        // var boolA:Comparable = false;

        var comparableArrayA:Array<Comparable> = [ 5, 2, -3, 4 ];
        trace( 'ArrayExtensions.min() of comparableArrayA is: ${comparableArrayA.min()}' );
        trace( 'comparableArrayA as JSON: ${Json.stringify( comparableArrayA )}' );

        var comparableArrayB:Array<Comparable> = [ 5.5, 2.2, -33.3, -44.004 ];
        trace( 'ArrayExtensions.min() of comparableArrayB is: ${comparableArrayB.min()}' );
        trace( 'comparableArrayB as JSON: ${Json.stringify( comparableArrayB )}' );

        var comparableArrayC:Array<Comparable> = [ 1, 9.99, 'hello' ];
        trace( 'ArrayExtensions.min() of comparableArrayC is: ${comparableArrayC.min()}' );
        trace( 'comparableArrayC as JSON: ${Json.stringify( comparableArrayC )}' );

        // Using ArrayExtensions.min() as static extension
        var value = [5, 2, -3, 4].min();
        trace( 'Smallest value is: ${value}' );
        
        var value = [5.1, 2.2, -3.3, 4.5].min();
        trace( 'Smallest value is: ${value}' );

        var value = [ "quick", "brown", "fox" ].min();
        trace( 'Smallest value is: ${value}' );

        // Won't compile
        // var value = [ true, false ].min();
        // trace( 'Smallest value is: ${value}' );

    }

}

abstract Comparable(Dynamic) from Int to Int from Float to Float from String to String {

    @:op( A < B )
    static public function lt<T>( a:Comparable, b:Comparable ):Bool;

    @:op( A > B )
    static public function gt<T>( a:Comparable, b:Comparable ):Bool;

}

class ArrayExtensions {

    static public function min<T:Comparable>( arr:Array<Comparable> ):Comparable {

        var minValue = arr[0];

        // Notice the zero-indexing!
        for (i in 0...arr.length) {

            if (arr[i] < minValue) {

				minValue = arr[i];

			}

		}

        return minValue;

    }

}

Output:

Main.hx:12: 123 is smaller than 456: true
Main.hx:13: 123 is larger than 456: false
Main.hx:17: 123.456 is smaller than 789.012: true
Main.hx:18: 123.456 is larger than 789.012: false
Main.hx:22: Hello is smaller than World: true
Main.hx:23: Hello is larger than World: false
Main.hx:31: ArrayExtensions.min() of comparableArrayA is: -3
Main.hx:32: comparableArrayA as JSON: [5,2,-3,4]
Main.hx:35: ArrayExtensions.min() of comparableArrayB is: -44.004
Main.hx:36: comparableArrayB as JSON: [5.5,2.2,-33.3,-44.004]
Main.hx:39: ArrayExtensions.min() of comparableArrayC is: 1
Main.hx:40: comparableArrayC as JSON: [1,9.99,"hello"]
Main.hx:44: Smallest value is: -3
Main.hx:47: Smallest value is: -3.3
Main.hx:50: Smallest value is: brown
1 Like
3

If you need to deal with Int and Float only then you can use <T:Float> constraint (beceause Int is compatible with Float):

static function min<T:Float>(a:Array<T>):T {
    var result = a[0];
    for(i in 1...a.length)
      if(a[i] < result)
        result = a[i];
    return result;
  }

Another approach is to define a module containing separate classes for each array type you want to handle.
For example ArrayUtils.hx with the following content:

class ArrayFloatUtils {
  public static function min(a:Array<Float>):Float {
    var result = a[0];
    for(i in 1...a.length)
      if(a[i] < result)
        result = a[i];
    return result;
  }
}

class ArrayIntUtils {
  public static function min(a:Array<Int>):Int {
    var result = a[0];
    for(i in 1...a.length)
      if(a[i] < result)
        result = a[i];
    return result;
  }
}

And then use it like this:

using ArrayUtils; //See "Source 2" tab

class Test {
  static function main() {
    var minInt = [1, 2, -1, 3].min();
    trace(minInt);  //-1
    $type(minInt); //Int
    
    var minFloat = [1.5, 2.1, -1.04, 3.6].min();
    trace(minFloat);  //-1.04
    $type(minFloat); //Float
  }
}
1 Like
4

@Igazine
Thanks a lot, this is what I was looking for! I had some doubt about Int & Float but you cleared that out. :wink:

The only downfall of this approach is that I need to explicitly declare each type that needs to be supported by Comparable but this shouldn’t be an issue since I mostly use Int or Float…

@RealyUniqueName
Actually constraining the type to Int or Float is working so your first solution works perfectly

5

Update: if the array is empty, it will return null because it will access the a[0] element which is undefined in JS (undefined == null is true), this is not correct and the return type should be Null<T>

I can add an explicit check for that and return null:

class ArrayExtensions {
	public static function min<T:Float>(a:Array<T>):Null<T> {
        if (a.length == 0) return null;
    
		var result = a[0];
    
		for (i in 1...a.length)
			if (a[i] < result)
				result = a[i];
    
		return result;
	}
}

Now another wanted behavior is to return positive infinity if the array is empty so it’s useful when comparing multiple minimum values together:

class ArrayExtensions {
	public static function min<T:Float>(a:Array<T>):T {
        if (a.length == 0) return Math.POSITIVE_INFINITY;
    
		var result = a[0];
    
		for (i in 1...a.length)
			if (a[i] < result)
				result = a[i];
    
		return result;
	}
}

[ERROR] Test.hx:5: characters 24-53

 5 |     if (a.length == 0) return Math.POSITIVE_INFINITY;
   |                        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   | Float should be min.T

But it doesn’t work, why can’t the compiler accept that we return a Float for min.T which is constrained to Float?

6

I am unsure maybe it is because a Float constraint means that it must be based on Float but does not have to equate to all Floats, but if you constrain it to a wrapper abstract either with @ to and from or other approaches then you can side step.

@:forward
abstract Tf( Float ) from Float to Float {
  public inline function new( f: Float ){
		this = f;
  }
}
function main() {
    trace("Haxe is great!");
}
class ArrayExtensions {
	public static function mini<T:Tf>(a:Array<Tf>):Tf {
    var f: Tf = Math.POSITIVE_INFINITY;
    if (a.length == 0) return f; 
		var result: Tf = a[0];
		for (i in 1...a.length)
			if( (a[i]: Float ) < ( result: Float ))
				result = a[i];
		return result;
	}
}

I tried to forward the Float methods… but you may need to implement eq operators on the Tf yourself, to make the if statement cleaner. Probably my answer is not useful in it’s form but may give you ideas?

7

I thought I should mention if you want to inline your method you may want to return the ‘if’.

return if( a.length == 0 ){
  f;
} else {
//
}
8

Because the compiler thinks T might extend Float. (Not true AFAIK, but for other types it could happen.) So it knows that T can always be converted to Float, but it doesn’t realize that Float can always be converted to T.

Consider returning Float instead of T.

2 Likes
9

It works, thanks for the explanation!