#include<stdio.h>
#include<stdlib.h>

#define Nil 0
typedef struct pair* list;

struct pair
{
  int item;   // car
  list next;  // cdr
};

list cons(int head, list tail)
{
  list A = (list)malloc(sizeof(struct pair)); // allocate 8 bytes
  A->item = head;
  A->next = tail;
  return A;
}

int car(list A)  { return A->item; }
list cdr(list A) { return A->next; }
int null(list A) { return A==Nil; }

int cadr(list A) { return car(cdr(A)); }
list cddr(list A) { return cdr(cdr(A)); }

int length(list A)
{ if (null(A)) return 0; else return 1 + length(cdr(A)); }
// (define (length A) (if (null? A) 0 (+ 1 (length (cdr A)))))

// product of all numbers in A, tail recursively
int product(list A)
{
  int iter(list A,int ax)
  { if (null(A)) return ax; else return iter(cdr(A),ax*car(A)); }
  return iter(A,1);
}
/*
(define (product A)
   (define (iter A ax) (if (null? A) ax (iter (cdr A) (* ax (car A)))))
   (iter A 1))
*/

// print all elements of list
void print(list A)
{
  for(;!null(A);A=cdr(A)) // does same thing as tail-recursive program
    printf("%d ", car(A));
  printf("\n");
}

// higher-order function "map"
list map(int (*f)(int), list A)
{
  if (null(A)) return A;
  else return cons(f(car(A)),map(f,cdr(A)));
}

// reduce - apply binary operator to successive elements (left-assoc)
int reduce(int (*op)(int,int), int id, list A)
{ 
  if (null(A)) return id;  // return identity
  else if (null(cdr(A))) return car(A);
  else return reduce(op,id,cons(op(car(A),cadr(A)), cddr(A))); 
}

// returns true predicate p holds for all elements
int forall(int (*p)(int), list A)
{
  if (null(A)) return 1; else return p(car(A)) && forall(p,cdr(A));
} // note that this is tail-recursive

int exists(int (*p)(int), list A)
{
  int notp(int n) { return !p(n); }
  return !forall(notp,A);
}

list reverse(list M)
{ 
  list rev(list M, list stack)
  { if (null(M)) return stack; else return rev(cdr(M),cons(car(M),stack)); }
  return rev(M,Nil);
}

void deallocate(list M)
{
  if (!null(M)) deallocate(cdr(M));
  free(M);
}


int main()
{
  list M = cons(2,cons(3,cons(5,cons(7,Nil))));
  list N = cons(1,cdr(M)); // what is N?
  print(N);
  printf("%d\n", product(M));
  int odd(int n) { return n%2==1; }
  print(map(&odd, M)); 
  printf("exists odd: %d\n", exists(&odd,M));
  list temp = M;
  M = reverse(M);
  deallocate(temp);
  print(M);
  print(N);
  return 0;
}