%{
#include <stdio.h>
#include <malloc.h>

struct sortedIntList {
  int i;
  struct sortedIntList *next;
};

struct sortedIntList *allocCons(int i, struct sortedIntList *ll) {
	struct sortedIntList *res;
	res = malloc(sizeof(struct sortedIntList));
	res->i = i;
	res->next = ll;
	return(res);
}
%}

%GET_FUN_SYM<struct sortedIntList *>(xx) ((xx==NULL)?0:1)
%GET_SUBTERM<struct sortedIntList *>(xx,n) ((n==0)?xx->i:(int)xx->next)

%sym struct sortedIntList *nil()                              % 0
%sym struct sortedIntList *cons(int, struct sortedIntList *)  % 1
%var int x,y;
%var struct sortedIntList *z;

%rule cons(x, cons(y, z)) %--> if (x==y) return(cons(y,z));
%rule cons(x, cons(y, z)) %--> if (x>y) return(cons(y,cons(x,z)));
%rule cons(x, z)          %--> return(allocCons(x,z));

%%

void printIntList(struct sortedIntList *ll) {
  printf("[ "); fflush(stdout);
  for(; ll!=NULL; ll=ll->next) {
	printf("%d", ll->i);
	if (ll->next!=NULL) printf(", ");
  }
  printf("]\n");
}

main() {
	printIntList(cons(1, cons(4, cons(2, NULL))));
	printIntList(cons(1, cons(4, cons(2, cons(0, cons(9,NULL))))));
}