// basic example  4 Oct 2011

#include <ailib.h>

int fac(int n){
	if(n == 0) return 1;
	else return n * fac(n-1);
}

// using "result" as an accumulator
int fac2(int n, int result){
	if(n == 0) return result;
	else return fac2(n-1, n*result);
}

int length(int ls){
	if(ls == NIL) return 0;
	else return 1 + length(tail(ls));
}

void test_length(void){
	int a,b,c;
	a = cons(name("A"),cons(name("B"),NIL));
	b = clone(a);
	c = cons(a,b);
	print_list(c); nl();
	printf("%d\n",length(c));
}

// do length2 similar to fac2
// do fib

int rev2(int ls1, int ls2){
	if( ls1 == NIL ) return ls2;
	else return rev2(tail(ls1), cons(head(ls1),ls2));
}

int reverse(int ls){
	return rev2(ls,NIL);
}

void test_rev(void){
	int a,b,c;
	a = cons(name("A"),cons(name("B"),cons(name("C"),NIL)));
	print_list(a); nl();
	b = reverse(a);
	print_list(b); nl();
}

// append( (A B D), (C E) ) = (A B D C E)
// append( A, (B C) ) = no
// append( (A B C), NIL ) = (A B C)

// append( (A), NIL ) = (A)
// append( x, y ) =  if singleton(x) then return cons(head(x),y)

int append(int ls1, int ls2){
	if( ls1 == NIL ) return ls2;
	else return cons(head(ls1), append(tail(ls1),ls2));
}

void test_append(void){
	int a,b,c;
	a = cons(name("A"),cons(name("B"),cons(name("D"),NIL)));
	b = cons(name("C"),cons(name("E"),NIL));
	print_list(a); nl();
	print_list(b); nl();
	c = append(a,b);
	print_list(c); nl();
}

// with append now we can define "direct" reverse
//    it is not "efficient" as "reserve"
int rev3(int ls){
	if( ls == NIL ) return NIL;
	else return append(rev3(tail(ls)), cons(head(ls), NIL));
}

void test_rev3(void){
	int a,b,c;
	a = cons(name("A"),cons(name("B"),cons(name("C"),NIL)));
	print_list(a); nl();
	b = rev3(a);
	print_list(b);
}

// now try to do "rev3" without "append"

// rev( A B C D ) =  (D C B A)
//             = cons( D, (C B A) )
//  D = head(rev(tail(x)))

//  to get (C B A)
//     (C B A) = rev( A B C)
//             = rev( cons( A, (B C)))
//             going after tail(x)
//             we can get A from x
//             = rev(cons(head(x),(B C)))
//             = rev(cons(head(x),rev(C B)))
//             = rev(cons(head(x),rev(tail(D C B)))
//             = rev(cons(head(x),rev(tail(rev(tail(x))))))

//  rev(x) = cons(head(rev(tail(x)),
//                rev(cons(head(x),rev(tail(rev(tail(x)))))

int rev4(int ls){
	if( ls == NIL ) return NIL;
	else if( tail(ls) == NIL ) return ls;
	else return cons(head(rev4(tail(ls))),
		             rev4(cons(head(ls), rev4(tail(rev4(tail(ls)))))));
}

void test_rev4(void){
	int a,b,c;
	a = cons(name("A"),cons(name("B"),cons(name("C"),NIL)));
	print_list(a); nl();
	b = rev4(a);
	print_list(b);
}

int main(void){
//	printf("%d\n",fac2(6,1));
//	test_length();
//	test_rev();
//	test_append();
//	test_rev3();
	test_rev4();
}