Basic lazy stream in JS

ant.js

/* base functions */

function apply(f,args) {
	return f.apply(undefined, args);
}
var slice = Function.prototype.call.bind(Array.prototype.slice);

/* Stream */

function Stream(head, tail) {
	this.hd = head;
	this.tl = tail; 
}
Stream.prototype.isEmpty = function() {
	return this === EMPTY;
}
Stream.prototype.head = function() {
	if (typeof this.hd === 'function') {
		this.hd = this.hd();
	}
	return this.hd;
}
Stream.prototype.tail = function() {
	if (typeof this.tl === 'function') {
		this.tl = this.tl();
	}
	return this.tl;
}

/* Stream functions */

function length(self) {
	var l = 0;
	while (!self.isEmpty()) {
		l++;
		self = self.tail();
	}
	return l;
}
function toArray(self) {
	var a = [];
	while (!self.isEmpty()) {
		a.push(self.head());
		self = self.tail();
	}
	return a;
}
function take(n, self) {
	if (self.isEmpty() || n <= 0) return EMPTY;
	return cons(self.head(), function() {
		return take(n-1, self.tail());
	});
}
function drop(n, self) {
	while (!self.isEmpty() && n-- > 0) 
		self = self.tail();
	return self;
}
function map(f, self) {
	if (self.isEmpty()) return EMPTY;
	return cons(f(self.head()), function() {
		return map(f, self.tail());
	});
}
function flatMap(f, self) {
	if (self.isEmpty()) return EMPTY;
	return append(f(self.head()), function() {
		return flatMap(f, self.tail());
	});
}
function span(f, self) {
	const a = [];
	while (!self.isEmpty() && f(self.head())) {
		a.push(self.head());
		self = self.tail();
	}
	return [apply(stream, a), self];
}
function spanEq(v, self) {
	const a = [];
	while (!self.isEmpty() && v === self.head()) {
		a.push(self.head());
		self = self.tail();
	}
	return [apply(stream, a), self];
}
function append(self, g) {
	if (self.isEmpty()) return g();
	return cons(self.head(), function() {
		return append(self.tail(), g);
	});
}
function cons(head, tail) {
	return new Stream(head, tail);
}
var EMPTY = new Stream();
function stream() {
	var arg = arguments;
	if (arg.length === 0) return EMPTY;
	if (arg.length === 1) return cons(arg[0], EMPTY);
	if (arg.length === 2) return cons(arg[0], cons(arg[1], EMPTY));
	return cons(arg[0], function() {
		return apply(stream, slice(arg, 1));
	});
}
function iterate(f, s) {
	return cons(s, function() {
		return iterate(f, f(s));
	});
}
function group(self) {
	if (self.isEmpty()) return EMPTY;
	var hd = self.head();
	var s = spanEq(hd, self.tail());
	return cons(cons(hd, s[0]), function() {
		return group(s[1])
	});
}

/* ants */

function ants() {
	return iterate(next, stream(1));
}
function next(s) {
	return flatMap(headLength, group(s));
}
function headLength(s) {
	return stream(s.head(), length(s));
}

console.log(toArray(map(s => toArray(s).join(""), take(10, ants()))).join("\n"));
console.log(drop(1000000, drop(1000000, ants()).head()).head());

1
11
12
1121
122111
112213
12221131
1123123111
12213111213113
11221131132111311231
1

real    0m10.663s
user    0m10.083s
sys 0m0.679s

Prelude> :m +Data.List
Prelude Data.List> let ants = iterate(concatMap(sequence[head,length]).group)[1]
Prelude Data.List> :set +s
Prelude Data.List> putStrLn $ unlines $ map (concatMap show) $ take 10 ants
1
11
12
1121
122111
112213
12221131
1123123111
12213111213113
11221131132111311231

(0.01 secs, 1,032,024 bytes)
Prelude Data.List> ants !! 1000000 !! 1000000
1
(12.31 secs, 3,695,559,160 bytes)
Prelude Data.List> 

JooyungsMacBook:js jooyung.han$ more ants.hs
import Data.List

ants = iterate(concatMap(sequence[head,length]).group)[1]
main = do
  putStrLn $ unlines $ map (concatMap show) $ take 10 ants
  print $ ants !! 1000000 !! 1000000
JooyungsMacBook:js jooyung.han$ ghc ants.hs
[1 of 1] Compiling Main             ( ants.hs, ants.o )
Linking ants ...
JooyungsMacBook:js jooyung.han$ time ./ants
1
11
12
1121
122111
112213
12221131
1123123111
12213111213113
11221131132111311231

1

real    0m7.404s
user    0m6.660s
sys 0m0.637s
JooyungsMacBook:js jooyung.han$