Blogged by Ujihisa. Standard methods of programming and thoughts including Clojure, Vim, LLVM, Haskell, Ruby and Mathematics written by a Japanese programmer. github/ujihisa

Tuesday, November 15, 2011

Lazy List in C

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

typedef struct list_ {
  int x;
  struct closure_int_int_list_ *tail;
} *list;

typedef struct closure_int_int_list_ {
  list (*call)(int, int);
  int x1;
  int x2;
} *closure_int_int_list;

closure_int_int_list newclosure(list call(int, int), int x1, int x2)
{
  closure_int_int_list c;
  c = (closure_int_int_list)malloc(sizeof(*c));
  c->call = call;
  c->x1 = x1;
  c->x2 = x2;
  return c;
}

list newlist(int x, closure_int_int_list tail)
{
  list xs = (list)malloc(sizeof(struct list_));
  xs->x = x;
  xs->tail = tail;
  return xs;
}

list listtail(list xs)
{
  if (xs->tail == NULL) return NULL;
  return xs->tail->call(xs->tail->x1, xs->tail->x2);
}

void deletelist(list xs)
{
  free(xs->tail);
  free(xs);
}

int *takelist(int num, list xs)
{
  int *array;
  int i;
  list p;
  array = (int *)malloc(sizeof(int) * num);
  p = xs;
  for (i = 0; i < num; ++i) {
    array[i] = p->x;
    p = listtail(p);
  }
  return array;
}

list fibnext(int a, int b)
{
  return newlist(b, newclosure(fibnext, b, a + b));
}

void printarray(int *xs, int size)
{
  int i;
  for (i = 0; i < size; ++i) {
    printf("%d ", xs[i]);
  }
}

int main(int argc, char const* argv[])
{
  list xs;
  int *array;
  xs = newlist(1, newclosure(fibnext, 1, 1));
  array = takelist(10, xs);
  printarray(array, 10);
  free(array);
  deletelist(xs);
  return 0;
}

result:

1 1 2 3 5 8 13 21 34 55 

No comments:

Post a Comment

Followers