fork download
copy 
  1. /***********************************************************
  2. data VList T where
  3.   | Empty :: VList T
  4.   | Node {value::T, next::VList T} :: VList T
  5. (for int type only)
  6. ***********************************************************/
  7. #include <stdio.h>
  8. #include <stdlib.h>
  9. #include <time.h>
  10.  
  11. /*#define DEBUG*/
  12.  
  13. #ifdef DEBUG
  14. int mallocCounter = 0;
  15. int freeCounter = 0;
  16. #endif
  17.  
  18. enum TAG_VList {
  19.   EMPTY,
  20.   NODE
  21. };
  22. union VList {
  23.   enum TAG_VList tag;
  24.   struct {
  25.     enum TAG_VList tag;
  26.   } Empty;
  27.   struct {
  28.     enum TAG_VList tag;
  29.     int value;
  30.     union VList *next;
  31.   } Node;
  32. };
  33.  
  34. void *dmalloc(size_t size) {
  35.   if (size >= 0) {
  36.     void *ptr = malloc(size);
  37. #ifdef DEBUG
  38.     if (ptr) {
  39.       mallocCounter++;
  40.       fprintf(stderr, "[DEBUG] MALLOC: %p\n", ptr);
  41.     }
  42. #endif
  43.     return ptr;
  44.   } else {
  45.     return NULL;
  46.   }
  47. }
  48.  
  49. void dfree(void * ptr) {
  50.   if (ptr) {
  51.     free(ptr);
  52. #ifdef DEBUG
  53.     freeCounter++;
  54.     fprintf(stderr, "[DEBUG]   FREE: %p\n", ptr);
  55. #endif
  56.   }
  57. }
  58.  
  59. void VList_dispose(union VList **pList) {
  60.   if (pList && *pList) {
  61.     if ((*pList)->tag == NODE) {
  62.       VList_dispose(&((*pList)->Node.next));
  63.     }
  64.     dfree(*pList);
  65.     *pList = NULL;
  66.   }
  67. }
  68.  
  69. union VList *VList_Empty() {
  70.   union VList *result = (union VList*)dmalloc(sizeof(union VList));
  71.   if (result) {
  72.     result->Empty.tag = EMPTY;
  73.   }
  74.   return result;
  75. }
  76.  
  77. union VList *VList_Node(int value, union VList *next) {
  78.   union VList *result = (union VList*)dmalloc(sizeof(union VList));
  79.   if (result) {
  80.     result->Node.tag   = NODE;
  81.     result->Node.value = value;
  82.     result->Node.next  = next;
  83.   }
  84.   return result;
  85. }
  86.  
  87. int VList_match_Empty(union VList *list) {
  88.   return list && list->tag == EMPTY;
  89. }
  90.  
  91. int VList_match_Node(union VList *list, int *pValue, union VList **pNext) {
  92.   if (list && list->tag == NODE) {
  93.     if (pValue) {
  94.       *pValue = list->Node.value;
  95.     }
  96.     if (pNext) {
  97.       *pNext  = list->Node.next;
  98.     }
  99.     return 1;
  100.   }
  101.   return 0;
  102. }
  103.  
  104. union VList *VList_clone(union VList *list) {
  105.   int value;
  106.   union VList *next;
  107.   if (VList_match_Empty(list)) {
  108.     return VList_Empty();
  109.   } else if (VList_match_Node(list, &value, &next)) {
  110.     return VList_Node(value, VList_clone(next));
  111.   } else {
  112.     return 0;
  113.   }
  114. }
  115.  
  116. union VList *VList_map(union VList *list, int (*fn)(int)) {
  117.   int value;
  118.   union VList *next;
  119.   if (VList_match_Empty(list)) {
  120.     return VList_Empty();
  121.   } else if (VList_match_Node(list, &value, &next)) {
  122.     return VList_Node(fn ? fn(value) : value, VList_map(next, fn)); 
  123.   } else {
  124.     return NULL;
  125.   }
  126. }
  127.  
  128. union VList *VList_filter(union VList *list, int (*fn)(int)) {
  129.   int value;
  130.   union VList *next;
  131.   if (VList_match_Empty(list)) {
  132.     return VList_Empty();
  133.   } else if (VList_match_Node(list, &value, &next)) {
  134.     return (fn && fn(value)) ?
  135.       VList_Node(value, VList_filter(next, fn)) :
  136.       VList_filter(next, fn);
  137.   } else {
  138.     return NULL;
  139.   }
  140. }
  141.  
  142. int VList_fold(union VList *list, int start, int (*fn)(int, int)) {
  143.   int value;
  144.   union VList *next;
  145.   if (VList_match_Empty(list)) {
  146.     return start;
  147.   } else if (VList_match_Node(list, &value, &next)) {
  148.     return fn ? fn(value, VList_fold(next, start, fn)) : start;
  149.   } else {
  150.     return start;
  151.   }
  152. }
  153.  
  154. union VList *VList_appendValue(union VList *list, int newValue) {
  155.   int value;
  156.   union VList *next;
  157.   if (VList_match_Empty(list)) {
  158.     return VList_Node(newValue, VList_Empty());
  159.   } else if (VList_match_Node(list, &value, &next)) {
  160.     return VList_Node(value, VList_appendValue(next, newValue));
  161.   } else {
  162.     return NULL;
  163.   }
  164. }
  165.  
  166. union VList *VList_appendValues(union VList *list, union VList *newValues) {
  167.   int value;
  168.   union VList *next;
  169.   if (VList_match_Empty(list)) {
  170.     return VList_clone(newValues);
  171.   } else if (VList_match_Node(list, &value, &next)) {
  172.     return VList_Node(value, VList_appendValues(next, newValues));
  173.   } else {
  174.     return NULL;
  175.   }
  176. }
  177.  
  178. union VList *VList_reverse(union VList *list) {
  179.   int value;
  180.   union VList *next;
  181.   if (VList_match_Empty(list)) {
  182.     return VList_Empty();
  183.   } else if (VList_match_Node(list, &value, &next)) {
  184.     return VList_appendValue(VList_reverse(next), value);
  185.   } else {
  186.     return NULL;
  187.   }
  188. }
  189.  
  190. int VList_count(union VList *list) {
  191.   int value;
  192.   union VList *next;
  193.   if (VList_match_Empty(list)) {
  194.     return 0;
  195.   } else if (VList_match_Node(list, &value, &next)) {
  196.     return 1 + VList_count(next);
  197.   } else {
  198.     return 0;
  199.   }
  200. }
  201.  
  202. void *closure = NULL;
  203.  
  204. int lt(int x) {
  205.   int y = closure ? *((int*)closure) : 0;
  206.   return x < y;
  207. }
  208.  
  209. int ge(int x) {
  210.   int y = closure ? *((int*)closure) : 0;
  211.   return x >= y;
  212. }
  213.  
  214. union VList *VList_sort(union VList *list) {
  215.   int value;
  216.   union VList *next;
  217.   if (VList_match_Empty(list)) {
  218.     return VList_Empty();
  219.   } else if (VList_match_Node(list, &value, &next)) {
  220.     void *oldClosure = closure;
  221.     closure = &value;
  222.     union VList *leftFilter = VList_filter(next, lt);
  223.     union VList *leftSide = VList_sort(leftFilter);
  224.     VList_dispose(&leftFilter);
  225.     union VList *rightFilter = VList_filter(next, ge);
  226.     union VList *rightSide = VList_sort(rightFilter);
  227.     VList_dispose(&rightFilter);
  228.     closure = oldClosure;
  229.     union VList *temp = VList_appendValue(leftSide, value);
  230.     VList_dispose(&leftSide);
  231.     union VList *result = VList_appendValues(temp, rightSide);
  232.     VList_dispose(&rightSide);
  233.     VList_dispose(&temp);
  234.     return result;
  235.   } else {
  236.     return NULL;
  237.   }
  238. }
  239.  
  240. union VList *randomNumbers(int count, int min, int max) {
  241.   if (count >= 1) {
  242.     int number = min + rand() % (max - min + 1);
  243.     return VList_Node(number, randomNumbers(count - 1, min, max));
  244.   } else {
  245.     return VList_Empty();
  246.   }
  247. }
  248.  
  249. void printNumbers(union VList *numbers) {
  250.   int flagFirst = 1;
  251.   union VList *current = numbers;
  252.   while (current) {
  253.     int value;
  254.     union VList *next;
  255.     if (VList_match_Node(current, &value, &next)) {
  256.       if (flagFirst) {
  257.         flagFirst = 0;
  258.       } else {
  259.         putchar(',');
  260.         putchar(' ');
  261.       }
  262.       printf("%d", value);
  263.       current = next;
  264.     } else {
  265.       current = NULL;
  266.     }
  267.   }
  268.   putchar('\n');
  269. }
  270.  
  271. int main(int argc, char *argv[]) {
  272.   srand((unsigned)time(NULL));
  273.   union VList *numbers = randomNumbers(12, 1, 6);
  274.   printf("Before sort: ");
  275.   printNumbers(numbers);
  276.   union VList *sortedNumbers = VList_sort(numbers);
  277.   printf("After sort:  ");
  278.   printNumbers(sortedNumbers);
  279.   VList_dispose(&sortedNumbers);
  280.   VList_dispose(&numbers);
  281. #ifdef DEBUG
  282.   fprintf(stderr, "[DEBUG] MALLOC: %d, FREE: %d\n", mallocCounter, freeCounter);
  283. #endif
  284.   return 0;
  285. }
Success #stdin #stdout 0s 4368KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Before sort: 6, 4, 3, 3, 1, 1, 2, 6, 6, 1, 4, 1
After sort:  1, 1, 1, 1, 2, 3, 3, 4, 4, 6, 6, 6
https://ideone.com/y3LQKb
Pattern matching and algebraic data types for pure C.
language:
C (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!