Skip to content

Instantly share code, notes, and snippets.

@yelouafi yelouafi/List.js
Created Apr 24, 2015

Embed
What would you like to do?
function eachKey(obj, f) {
for(var key in obj) {
if( obj.hasOwnProperty(key) )
f(key, obj[key]);
}
}
function adtcase (base, proto, key) {
return (...args) => {
var inst = new base();
eachKey(proto(...args), (key, val) => { inst[key] = val })
inst['is'+key] = true;
return inst;
}
}
function adt(base, variants) {
eachKey(variants, (key, v) => {
if(typeof v === 'function')
base[key] = adtcase(base, v, key);
else {
base[key] = v;
v['is'+key] = true;
}
})
}
function List() {}
adt( List, {
Empty : new List(),
Cons : (head, tail) => ({head, tail}),
Lazy : thunk => ({thunk})
})
List.one = x => List.Cons(x, List.Empty);
List.array = function(arr) {
return from(0);
function from(i){
return i < arr.length ? List.Cons( arr[i], from(i+1) ) : List.Empty;
}
}
// map : (List a, a -> b ) -> List b
List.prototype.map = function(f) {
return this.isEmpty ? List.Empty :
this.isCons ? List.Cons( f(this.head), this.tail.map(f) ) :
/*isLazy */ List.Lazy( () => this.thunk().map(f) );
}
// concat : (List a, List a ) -> List a
List.prototype.concat = function(list) {
return this.isEmpty ? list :
this.isCons ? List.Cons( this.head, this.tail.concat(list) ) :
/*isLazy */ List.Lazy( () => this.thunk().concat(list) );
}
// filter : (List a, a -> Boolean ) -> List a
List.prototype.filter = function(f) {
return this.isEmpty ? List.Empty :
this.isCons ?
(f(this.head) ?
List.Cons( this.head, this.tail.filter(f) ) :
this.tail.filter(f)) :
/* isLazy */ List.Lazy( () => this.thunk().filter(f) );
}
// sort : List a -> List a
List.prototype.sort = function() {
return this.isEmpty ? List.Empty :
this.isCons ?
List.Lazy( () => this.tail.filter( x => x < this.head ).sort() )
.concat( List.one(this.head) )
.concat( List.Lazy(() => this.tail.filter(x => x >= this.head)).sort() ) :
/*isLazy */ List.Lazy( () => this.thunk().sort() );
}
// take : (List a, Integer ) -> List a
List.prototype.take = function(n) {
return this.isEmpty || n <= 0 ?
List.Empty :
this.isCons ?
List.Cons( this.head, this.tail.take(n-1) ) :
/* isLazy */
this.thunk().take(n);
}
// do : (List a, a -> b ) -> List b
List.prototype.do = function(action) {
return this.isEmpty ? List.Empty :
this.isCons ? List.Cons( action(this.head), this.tail.do(action) ) :
/*isLazy */ this.thunk().do(action);
}
let nat = start => List.Cons( start, List.Lazy( () => nat(start+1) ) )
let repeat = val => List.Cons( val, List.Lazy(repeat.bind(null, val)) )
let infRands = (min, max) => List.Cons(
parseInt((Math.random() * (max - min + 1)), 10) + min,
List.Lazy( () => infRands(min, max) )
)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.