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

/* function to concatenate one string onto another. equivalent to 
   a = a+b
*/
//#define NULL 0

char* cat(char *a, char *b)
{
  // char *a = "abc";
  // char *b = "def";
  int an = strlen(a);
  int bn = strlen(b);
  char *temp = (char *)malloc(an+bn+1);
  memcpy(temp,a,an);
  memcpy(temp+an,b,bn+1);
  // free(a);
  a = temp;
  return a;
}


///////////////// linked list abstraction in C /////////////////

//// Can we achieve the same level of abstraction over linked lists in C
// as we can in Scheme.  Scheme is untyped, so we'll confine ourselfs to
// lists of integers.  The question is, in what essential way is C different
// from scheme, aside from its syntax. 


typedef struct cell* list;   // defines list to be struct cell *

struct cell
{
  int head;
  struct cell * tail;
};

// constructor
list cons(int h, list t) 
{
  list newcell = (list)malloc(8);
  newcell->head = h;
  newcell->tail = t;
  return newcell;
}

// car returns first element of list, cdr returns rest of list
int  car(list m) { return m->head; }
list cdr(list m) { return m->tail; }

// destructor: recursively free (deallocate) each cell in list:
void freelist(list m)
{
  if (m!=NULL)
    {
      freelist(cdr(m));
      free(m);
    }
}

// length function
int length(list m)
{
  if (m==NULL) return 0; else return 1+length(cdr(m));
}
// (define (length m) (if (null? m) 0 (+ 1 (length (cdr m)))))

// member function - true if x is in m:
int member(int x, list m)
{
  return (m!=NULL) && (x==car(m) || member(x,cdr(m))); // look ma! no ifelse!
}
// (define (memb x m) (and (not (null? m)) (or (equal? x (car m)) 
//                                             (memb x (cdr m)))))


// last element of list
int last(list m)
{
  if (cdr(m)==NULL) return car(m);
  else return last(cdr(m));  
}
// (define (last m) (if (null? (cdr m)) (car m) (last (cdr m))))



// function to apply function to every element of list:
void foreach(list m, void (*f)(int))
{
  if (m!=NULL) 
    {
      f(car(m));
      foreach(cdr(m),f); 
    }
  else printf("\n");
}
// (define (foreach m f)
//   (if (null? m) (display "\n")
//         (begin
//             (f (car m))
//             (foreach (cdr m) f)))))


void print1(int x)   // (lambda (x) (display x))
{
  printf("%3d",x);
}

// map a function to a list, get new list

list map(int (*f)(int), list m)
{
  if (m==NULL) return NULL;
  else return cons(f(car(m)), map(f,cdr(m)));
}
// (define (map f m) (if (null? m) () (cons (f (car m)) (map f (cdr m)))))


// fold a binary operator op with identity id over a list:
int fold(int (*op)(int,int), int id, list m)
{
  if (m==NULL) return id;
  else return op(car(m), fold(op,id,cdr(m)));
}
// (define (fold op id m) 
//    (if (null? m) id 
//                  (op (car m) (fold op id (cdr m)))))

int square(int x) { return x*x; }

int times(int x, int y) {return x*y;}

int main()
{
  //  printf(cat("abc","def"));
  list A = cons(2,cons(4,cons(6,cons(8,NULL))));
  list B = cons(1,cdr(A));
  foreach(A,print1);
  foreach(B,print1);
  printf("fold is %d\n",fold(times,1,A));
  list temp = A;   // pointer to old list so it can be deallocated
  A = map(square,A);
  foreach(A,print1);
  freelist(temp);  // deallocate memory for old list A
  foreach(B,print1);   // !!!OOPS!!!  B is nolonger there!
} // main