List2

List2.hx

enum List<T> {
    Cons(h : T, t : List<T>, n : Int) : List<T>;
	Nil : List<T>;
}

enum StreamCell<T> {
    Cons(h : T, t : Stream<T>, n : Int) : StreamCell<T>;
    Nil : StreamCell<T>;
}
typedef Stream<T> = Void -> StreamCell<T>

enum Enumerable<X> {
	Strict<T>(x : List<T>) : Enumerable<List<T>>;
	Lazy<T>(x : Stream<T>) : Enumerable<Stream<T>>;
}

abstract AbsEnumerable<X>(Enumerable<X>) {
	public function new(x) {
		this = x;
	}

	@:from public static inline function fromStrict<T>(x : List<T>) : AbsEnumerable<List<T>> {
		return new AbsEnumerable(Strict(x));
	}

	@:from public static inline function fromLazy<T>(x : Stream<T>) : AbsEnumerable<Stream<T>> {
		return new AbsEnumerable(Lazy(x));
	}

	@:from public static inline function fromList<T>(x : Enumerable<T>) : AbsEnumerable<T> {
		return new AbsEnumerable(x);
	}

	@:to public inline function toX() : X {
		return switch (this) {
			case Strict(x) : x;
			case Lazy(x)   : x;
		}
	}

	@:to public inline function toAbsEnumerable() : AbsEnumerable<X> {
		return this;
	}
}

interface ListInterface<X, Y> {
	public function nil() : AbsEnumerable<Y>;
	public function cons(x : X, l : AbsEnumerable<Y>) : AbsEnumerable<Y>;
	public function hd(l : AbsEnumerable<Y>) : X;
	public function tl(l : AbsEnumerable<Y>) : AbsEnumerable<Y>;
	public function append(a : AbsEnumerable<Y>, b : AbsEnumerable<Y>) : AbsEnumerable<Y>;
	public function reverse(l : AbsEnumerable<Y>) : AbsEnumerable<Y>;
	public function take(l : AbsEnumerable<Y>, n : Int) : AbsEnumerable<Y>;
	public function drop(l : AbsEnumerable<Y>, n : Int) : AbsEnumerable<Y>;
	public function length(l : AbsEnumerable<Y>) : Int;
	public function toArray(l : AbsEnumerable<Y>) : Array<X>;
}

class StrictList<T> implements ListInterface<T, List<T>> {
    public function new() {}
    
	public inline function nil() : List<T> {
		return List.Nil;
	}

    public inline function cons(x : T, l : List<T>) : List<T> {
		return List.Cons(x, l, (length(l) + 1));
    }
    
    public inline function hd(l : List<T>) : T {
        return switch(l) {
            case List.Cons(h, _, _): h;
            case List.Nil: throw "error!";
        };
    }
    
    public inline function tl(l : List<T>) : List<T> {
        return switch(l) {
            case List.Cons(_, t, _): t;
            case List.Nil: List.Nil;
        };
    }
    
    public inline function append(a : List<T>, b : List<T>) : List<T> {
		return switch(a) {
			case List.Cons(h, t, _): cons(h, append(t, b));
			case List.Nil: b;
		}
    }
    
	public inline function length(l : List<T>) : Int {
		return switch (l) {
			case List.Cons(_, _, n): n;
			case List.Nil: 0;
		}
	}

	public inline function take(l : List<T>, n : Int) : List<T> {
		return switch(n) {
			case i if (i <= 0): l;
			case i: cons(hd(l), take(tl(l), i - 1));
		}
	}

	public inline function drop(l : List<T>, n : Int) : List<T> {
		return switch(n) {
			case i if (i <= 0): l;
			case i: drop(tl(l), i - 1);
		}
	}

    public inline function reverse(l : List<T>) : List<T> {
		function loop(l : List<T>, a : List<T>) {
			return return switch(l) {
				case List.Cons(h, t, n): loop(t, List.Cons(h, a, n));
				case List.Nil: a;
			}
		}

		return loop(l, List.Nil);
    }

    public inline function toArray(l : List<T>) : Array<T> {
        function loop(l : List<T>, a : Array<T>) : Array<T> {
            return switch(l) {
                case List.Cons(h, t, _): a.push(h); loop(t, a);
                case List.Nil: a;
            };
        }
        
        return loop(l, []);
    }
}

class LazyList<T> implements ListInterface<T, Stream<T>> {
	public function new () { }

	public inline function nil() : Stream<T> {
		return function () { return StreamCell.Nil; };
	}

    public inline function cons(x : T, s : Stream<T>) : Stream<T> {
        return function() : StreamCell<T> {
            return StreamCell.Cons(x, s, length(s) + 1);
        };
    }

	public inline function length(s : Stream<T>) : Int {
		return switch(s()) {
			case StreamCell.Cons(h, t, n) : n;
			case StreamCell.Nil: 0;
		}
	}
    
    public inline function hd(s : Stream<T>) : T  {
        return switch(s()) {
            case StreamCell.Cons(h, _, _): h;
            case StreamCell.Nil: throw "stream headd error!";
        }
    }
    
    public inline function tl(s : Stream<T>) : Stream<T> {
        return switch(s()) {
            case StreamCell.Cons(_, t, _): t;
            case StreamCell.Nil: nil();
        }
    }

    public inline function append(a : Stream<T>, b : Stream<T>) : Stream<T> {
		function loop (s : Stream<T>) : StreamCell<T> {
			return switch(s()) {
				case StreamCell.Cons(h, t, n): StreamCell.Cons(h, function () { return loop(t); }, n + length(b));
				case StreamCell.Nil: b();
			}
		}
        
        return function () { return loop(a); }
    }
    
    public inline function reverse(s : Stream<T>) : Stream<T> {
		var n = switch (s()) {
			case StreamCell.Cons(_, _, n): n;
			case StreamCell.Nil: 0;
		}

        function loop(s : Stream<T>, a : StreamCell<T>) : StreamCell<T> {
            return switch(s()) {
				case StreamCell.Cons(h, t, i):
					loop(t, StreamCell.Cons(h, function () { return a; }, n - i));
                case StreamCell.Nil : a;
			}
		}
        
		return function () { return loop(s, StreamCell.Nil); };
    }

	public inline function toArray(s : Stream<T>) : Array<T> {
		return switch (s()) {
			case StreamCell.Cons(h, t, _): [h].concat( toArray(t) );
			case StreamCell.Nil: [];
		}
	}
    
    public inline function take(s : Stream<T>, n : Int) : Stream<T> {
		return switch(n) {
			case i if (i <= 0): s;
			case i: cons(hd(s), take(tl(s), i - 1));
		}
    }

	public inline function drop(s : Stream<T>, n : Int) : Stream<T> {
		return switch(n) {
			case i if (i <= 0): s;
			case i : drop(tl(s), i - 1);
		}
	}
}



class Test {
	static function listBenchmark<T> (maker : ListInterface<Int, T>, n : Int, ?str : String) {
		var a : Float = 0.0;

		for (i in 0 ... 10) {
            var timer = Date.now().getTime();
            
			{
				var x = maker.nil();
				for (j in 0 ... n)
					x = maker.cons(j, x);

				var y = maker.nil();
				for (j in 0 ... n)
					y = maker.cons(j, y);

				var z = maker.nil();
				for (j in 0 ... n)
					z = maker.cons(j, z);

				maker.append(maker.append(x, y), z);
				//maker.append(x, maker.append(z, y));
			}

            a += Date.now().getTime() - timer;
        }
        trace("---- " + str + " ----");
        trace(a / 10);
        trace("---- end ----");
	}

	static function miniTest<T>(maker : ListInterface<Int, T>) {
		var x = maker.cons(3, maker.cons(2, maker.cons(1, maker.nil())));
		var y = maker.cons(6, maker.cons(5, maker.cons(4, maker.nil())));

		trace(maker.toArray(maker.append(maker.append(x, y), y)));
		trace(maker.toArray(maker.append(y, maker.append(x, y))));
	}

	static function main() {
		miniTest(new StrictList<Int>());
		miniTest(new LazyList<Int>());

		listBenchmark(new StrictList<Int>(), 1000, "StrictList 1000");
		listBenchmark(new StrictList<Int>(), 2000, "StrictList 2000");
		listBenchmark(new StrictList<Int>(), 3000, "StrictList 3000");
		listBenchmark(new StrictList<Int>(), 4000, "StrictList 4000");
        
		listBenchmark(new LazyList<Int>(), 1000, "LazyList 1000");
		listBenchmark(new LazyList<Int>(), 2000, "LazyList 2000");
		listBenchmark(new LazyList<Int>(), 3000, "LazyList 3000");
		listBenchmark(new LazyList<Int>(), 4000, "LazyList 4000");
	}
}