Cにおける、無限リストの実装

どうでもよいことなのですが、この間Cでcarとcdrが使える、いわゆるリストを実装しました。そのソースを以下に示します。

#include 
#include 
struct cell{
	int value;
	struct cell *next;
};

struct cell *new_cell(int value){
	struct cell *cell = malloc(sizeof(struct cell));
	cell->value = value;
	cell->next = NULL;
	return cell;
}

struct cell *cons(int first, struct cell *c){
	struct cell *f = new_cell(first);
	f->next = c;
	return f;
}

int car(struct cell *c){
	return c->value;
}

struct cell *cdr(struct cell *c){
	return c->next;
}

struct cell *append(struct cell *f, struct cell *n){
	if(f == NULL){
		return n;
	}else{
		return cons(car(f), append(cdr(f), n));
	}
}

struct cell *reverse(struct cell *c){
	if(c == NULL){
		return NULL;
	}else{
		return append(reverse(cdr(c)), new_cell(c->value));
	}
}

struct cell *add_last(struct cell *c, int value){
	if(c == NULL){
		return new_cell(value);
	}else{
		return append(c, add_last(cdr(c), value));
	}
}


int main(){
	struct cell *c = NULL;
	struct cell *d = NULL;
	c = cons(1, c);
	c = cons(2, c);
	c = cons(3, c);
	d = cons(4, d);
	d = cons(5, d);
	d = cons(6, d);
	d = append(d, c);
	printf("%d\n", car(c));
	printf("%d\n", car(cdr(c)));
	printf("%d\n", car(cdr(cdr(c))));
	printf("%d\n", car(d));
	printf("%d\n", car(cdr(d)));
	printf("%d\n", car(cdr(cdr(d))));
	c = reverse(c);
	printf("%d\n", car(c));
	
}

これでもちろん動作しますが、あんまり面白みが無いですよね。単にfreeされないという欠点だけを持っているリスト構造でしかありません。
なので、いわゆる無限リストというやつを実装してみることにしました。ソースとしてはほとんど変更していません。

#include 
#include 
struct cell{
	int value;
	struct cell *next;
	int delay;
	struct cell *(*next_func)(int);
	int arg;
};

struct cell *new_cell(int value){
	struct cell *cell = malloc(sizeof(struct cell));
	cell->value = value;
	cell->next = NULL;
	cell->delay = 0;
	cell->next_func = NULL;
	cell->arg = 0;
	return cell;
}

struct cell *cons(int first, struct cell *c){
	struct cell *f = new_cell(first);
	f->next = c;
	return f;
}

int car(struct cell *c){
	return c->value;
}

struct cell *cdr(struct cell *c){
	if(c->delay){
		c->next = c->next_func(c->arg);
		c->delay = 0;
	}
	return c->next;
}

struct cell *append(struct cell *f, struct cell *n){
	if(f == NULL){
		return n;
	}else{
		return cons(car(f), append(cdr(f), n));
	}
}

struct cell *reverse(struct cell *c){
	if(c == NULL){
		return NULL;
	}else{
		return append(reverse(cdr(c)), new_cell(c->value));
	}
}

struct cell *add_last(struct cell *c, int value){
	if(c == NULL){
		return new_cell(value);
	}else{
		return append(c, add_last(cdr(c), value));
	}
}

構造の中に、delayという項目があることに注目してください。このdelayというのはいわゆる遅延評価のためのフラグになっていて、これが1であれば後で評価してやらなくてはならないのです。評価の方法は単純で、next_funcにargを食わせるという方法になっています。
で、これをどうやって使うかという話になりますが、一番簡単な自然数の無限リストは以下のように実装可能です。

struct cell *start_n(int n){
	struct cell *c = new_cell(n);
	c->delay = 1;
	c->next_func = start_n;
	c->arg = n + 1;
	return c;
}

int main(){
	struct cell *c = start_n(0);
	//printf("%d\n", c->value);
	printf("%d\n", car(cdr(cdr(cdr(cdr(cdr(c)))))));
	
}

このようにアクセスすることで、どれだけ先の数でも得ることが出来ます。アクセスしなければ評価はされないので、最初から無限のリストが作られているわけではありません。あるいは素数の無限リストを作ってやることも簡単に出来ます。

struct cell *start_n_prime(int n){
	while(1){
		int flg2 = 0;
		int i;
		for(i = 2; i*i <= n; i++){
			if(n % i == 0){
				flg2 = 1;
				break;
			}
		}
		if(!flg2){
			break;
		}
		n++;
	}
	struct cell *c = new_cell(n);
	c->delay = 1;
	c->next_func = start_n_prime;
	c->arg = n+1;
	return c;
}

int main(){
	struct cell *c = start_n_prime(1);
	printf("%d\n", car(cdr(cdr(cdr(cdr(cdr(cdr(c))))))));
	
}

これで面白いのは、一度計算された値は一度しか評価されないということ、すなわちcall by needで実装されていることです。例えば、以下のソースにおいて、time1は9秒くらいかかりましたが、time2は0秒でした。一度目は計算していますが、二度目からはリストを辿るだけなので早いです。

#include 
int main(){
	struct cell *c = start_n_prime(1);
	struct cell *d = c;
	int i;
	
	int t1 = time(NULL);
	for(i = 0; i < 300000; i++){
		d = cdr(d);
	}
	printf("%d\n", car(d));
	int t2 = time(NULL);
	printf("time1:%d\n", t2 - t1);
	d = c;
	for(i = 0; i < 300000; i++){
		d = cdr(d);
	}
	printf("%d\n", car(d));
	printf("time2:%d\n", time(NULL) - t2);

}

問題は、次の関数への引数になる部分、すなわち構造体のarg要素がint型である点です。これでは何も出来ないじゃないか、と思うかもしれませんが、その場合にはポインタ型にキャストしてやれば良いのです。たとえば、引数を二つとるはずのフィボナッチ数列の無限リストも実装可能です。

struct cell *next_fib(int n){
	int *pair = (int *)n;
	int *next_pair = malloc(sizeof(int) * 2);
	struct cell *c = new_cell(pair[0] + pair[1]);
	c->delay = 1;
	c->next_func = next_fib;
	next_pair[0] = pair[1];
	next_pair[1] = pair[0] + pair[1];
	c->arg = (int)next_pair;
	return c;
}

int main(){
	int *pair = malloc(sizeof(int) * 2);
	pair[0] = 1;
	pair[1] = 1;
	struct cell *c = next_fib((int)pair);
	printf("%d\n", car(cdr(cdr(cdr(cdr(cdr(cdr(c))))))));
	
}

このソースが良いかどうかは別として、無限リストの良さと言うのは決して無限リスト自体が使いたいという要請というよりは、むしろ無限の長さを持っているものを有限の長さを持っているものと同様に扱うインターフェースがあるという点にあると思います。
C自体には無限を扱うという概念はおそらく無いために、確保した領域をfreeしないという形で不自然さが現れているわけです。関数型のパラダイムってのはこういうところに現れるんですね。
ちなみに、これはPerlだともっと簡単に書けるわけで、まあ当たり前だよね。
せっかくPerlでやるのであれば、僕としてはAUTOLOADと正規表現を使って、caddddddddddrみたいな関数を、任意のパターンで実装してやりたいなと思う。まあ、Acmeモジュールレベルの問題だとは思うけども。