implement Lists; include "lists.m"; # these will be more useful when p is a closureallsat[T](p: ref fn(x: T): int, l: list of T): int{	for(; l != nil; l = tl l)		if(!p(hd l))			return 0;	return 1;} anysat[T](p: ref fn(x: T): int, l: list of T): int{	for(; l != nil; l = tl l)		if(p(hd l))			return 1;	return 0;} map[T](f: ref fn(x: T): T, l: list of T): list of T{	if(l == nil)		return nil;	return f(hd l) :: map(f, tl l);} filter[T](p: ref fn(x: T): int, l: list of T): list of T{	if(l == nil)		return nil;	if(p(hd l))		return hd l :: filter(p, tl l);	return filter(p, tl l);} partition[T](p: ref fn(x: T): int, l: list of T): (list of T, list of T){	l1: list of T;	l2: list of T;	for(; l != nil; l = tl l)		if(p(hd l))			l1 = hd l :: l1;		else			l2 = hd l :: l2;	return (reverse(l1), reverse(l2));} append[T](l: list of T, x: T): list of T{	# could use the reversing loops instead if this is ever a bottleneck	if(l == nil)		return x :: nil;	return hd l :: append(tl l, x);} concat[T](l: list of T, l2: list of T): list of T{	if(l2 == nil)		return l;	for(rl1 := reverse(l); rl1 != nil; rl1 = tl rl1)		l2 = hd rl1 :: l2;	return l2;} combine[T](l: list of T, l2: list of T): list of T{	for(; l != nil; l = tl l)		l2 = hd l :: l2;	return l2;} reverse[T](l: list of T): list of T{	rl: list of T;	for(; l != nil; l = tl l)		rl = hd l :: rl;	return rl;} last[T](l: list of T): T{	# l must not be nil	while(tl l != nil)		l = tl l;	return hd l;} # find instance of x in l, return tail of l from xfind[T](x: T, l: list of T): list of T	for { T =>	eq:	fn(a, b: T): int; }{	for(; l != nil; l = tl l)		if(T.eq(x, hd l))			return l;	return nil;} # delete the first instance of x in ldelete[T](x: T, l: list of T): list of T	for { T =>	eq:	fn(a, b: T): int; }{	loc := find(x, l);	if(loc == nil)		return l;	o: list of T;	for(; l != loc; l = tl l)		o = hd l :: o;	l = tl loc;	for(; o != nil; o = tl o)		l = hd o :: l;	return l;} pair[T1, T2](l1: list of T1, l2: list of T2): list of (T1, T2){	if(l1 == nil && l2 == nil)		return nil;	return (hd l1, hd l2) :: pair(tl l1, tl l2);} unpair[T1, T2](l: list of (T1, T2)): (list of T1, list of T2){	l1: list of T1;	l2: list of T2;	for(; l != nil; l = tl l){		(v1, v2) := hd l;		l1 = v1 :: l1;		l2 = v2 :: l2;	}	return (reverse(l1), reverse(l2));} ismember[T](x: T, l: list of T): int	for { T =>	eq:	fn(a, b: T): int; }{	for(; l != nil; l = tl l)		if(T.eq(x, hd l))			return 1;	return 0;}