Implement lazy lists, preferably in a language you don't know well This is a nice exercise for becoming more fluent in that programming language you've been meaning to learn, but have only tinkered with lightly.  This involves working with objects, using or simulating closures, and stretching the type system.

Your task is to write code to manage lazy lists, then use it to implement this algorithm for generating Fibonacci numbers:

Code samples are in Haskell

let fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
 in take 40 fibs


Result:

[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986]


Your lazy list implementation should meet these guidelines:


A List node is one of three things:

Nil - Empty list.
   []
Cons - A single item, paired with a List of the remaining items:
    1 : [2,3,4,5]
    (: is the cons operator in Haskell)
Thunk - A deferred computation that produces a List node when needed.

It supports the following operations:

nil - Construct an empty list.
cons - Construct a cons cell.
thunk - Construct a Thunk, given a function that takes no arguments and returns a Nil or Cons.
force - Given a List node:

If it's a Nil or Cons, simply return it.
If it's a Thunk, call its function to get a Nil or Cons.  Replace the thunk with that Nil or Cons, and return it.
Note: Replacing the thunk with its forced value is an important part of the definition of "lazy".  If this step is skipped, the Fibonacci algorithm above will be too slow.

empty - See if a List node is Nil (after forcing it).
head (a.k.a. "car") - Get the first item of a list (or throw a fit if it's Nil).
tail (a.k.a. "cdr") - Get the elements after the head of a list (or throw a fit if it's Nil).
zipWith - Given a binary function (e.g. (+)) and two (possibly infinite) lists, apply the function to corresponding items of the lists.  Example:
zipWith (+) [1,2,3] [1,1,10] == [2,3,13]
take - Given a number N and a (possibly infinite) list, grab the first N items of the list.
print - Print all the items in a list.  This should work incrementally when given a long or infinite list.

fibs uses itself in its own definition.  Setting up lazy recursion is a tad tricky; you'll need to do something like this:


Allocate a thunk for fibs.  Leave it in a dummy state for now.
Define the thunk function, which depends on a reference to fibs.
Update the thunk with its function.


You may want to hide this plumbing by defining a function fix which calls a List-returning function with its own return value.  Consider taking a short nap so this idea can set in.
Polymorphism (the ability to work with lists of any type of item) is not required, but see if you can find a way to do it that's idiomatic in your language.
Don't worry about memory management.  Even languages with garbage collection have a tendency to carry around objects you'll never use again (e.g. on the call stack), so don't be surprised if your program leaks memory while traversing an infinite list.


Feel free to deviate slightly from these guidelines to accommodate the particulars of your language, or to explore alternative approaches to lazy lists.

Rules:


Pick a language you don't know well.  I can't "require" this, hence the "honor-system" tag.  However, voters can check your history to see what languages you've been posting in.
Don't use your language's built-in lazy list support to do everything.  Post something substantial or at least interesting.


Haskell is pretty much out.  That is, unless you do something like this:

data List a = IORef (ListNode a)
data ListNode a = Nil | Cons !a !(List a) | Thunk !(IO (ListNode a))


Note: Haskell's non-strict evaluation isn't off-limits, but your lazy list implementation shouldn't derive its capability directly from there.  In fact, it'd be interesting to see an efficient, purely functional solution that doesn't require laziness.
Python:


Don't use itertools.
Generators are fine, but you use them, you'll have to find some way to memoize forced values.
C

I am a total beginner in C, this code is actually the first real thing I coded in C. It compiles without any warnings and runs fine on my system.

How to build

First, get the tarball from my server. It includes a makefile, so just run make to build it and then make run to run it. The program then prints a list of the first 93 fibonacci numbers. (After number 94, an unsigned 64 bit integer overflows)

Explanation

The programs core is the file lazy-list.c. In the corresponding header file, I define a struct list, that is our lazy list. It looks like this:

enum cell_kind {
  NIL,
  CONS,
  THUNK
};

typedef enum cell_kind cell_kind;

typedef long int content_t;

struct list {
  cell_kind kind;
  union {
    struct {
      content_t* head;
      struct list* tail;
    } cons;
    struct {
      struct list* (*thunk)(void*);
      /* If you want to give arguments to the thunk, put them in here */
      void* args;
    } thunk;
  } content;
};


The member kind is kind of a tag. It marks, whether we reched the lists end (NIL), a cell that is already evaluated (CONS) or a thunk (THUNK). Then, there follows a union. It is


either an already evaluated cell with a value and a tail
or a thunk, featuring a function-pointer and a struct, that may contain some arguments to the function, if needed.


The content of the union is asserted by the tag. If the tag is NIL, the content of the union is undefined.

By defining the helper functions mentioned in the specification above, one can usually abstract the lists definition from it's usage, eg. you can simply call nil() to get an empty list instead of creating one by yourself.

The three most interesting functions are zipWith, take and fibonaccis. But I don't want to explain take, since it is very similar to zipWith. All functions, that operate lazily, have three components:


A wrapper, that creates a thunk
A worker, that performs the calculations for one cell
A struct, that keeps the arguments


In case of zipWith, these are zipWith, __zipWith and __zipArgs. I just show them here without any further explanation, there function should be quite clear:

struct __zipArgs {
  content_t* (*f)(content_t*,content_t*);
  list* listA;
  list* listB;
};

static list* __zipWith(void* args_) {
  struct __zipArgs* args = args_;
  list* listA = args-&gt;listA;
  list* listB = args-&gt;listB;
  list* listC;

  content_t* (*f)(content_t*,content_t*) = args-&gt;f;
  content_t* headA = head(listA);
  content_t* headB = head(listB);
  content_t* headC;

  if (NULL == headA || NULL == headB) {
    free(args);
    return nil();
  } else {
    headC = f(headA, headB);
    args-&gt;listA = tail(listA);
    args-&gt;listB = tail(listB);
    listC = thunk(__zipWith,args);
    return cons(headC,listC);
  }
}

list* zipWith(content_t* (*f)(content_t*,content_t*),list* listA, list* listB) {
  struct __zipArgs* args = malloc(sizeof(struct __zipArgs));
  args-&gt;f = f;
  args-&gt;listA = listA;
  args-&gt;listB = listB;
  return thunk(__zipWith,args);
}


The other interesting function is fibonaccis(). The problem is, that we need to pass a pointer of the first and second cell to the thunk of the third, but in order to create those cells we also need a pointer to the thunk. To solve that problem, I filled the pointer to the thunk with a NULL first and changed it into the thunk, after it was created. Here is the listening:

static content_t* __add(content_t* a,content_t* b) {
  content_t* result = malloc(sizeof(content_t));
  *result = *a + *b;
  return result;
}

list* fibonaccis() {
  static content_t one_ = 1;
  static content_t zero_ = 0;
  list* one  = cons(&amp;one_,NULL);
  list* two  = cons(&amp;zero_,one);
  list* core = zipWith(__add,one,two);
  one-&gt;content.cons.tail = core;
  return two;


Possible improvements


My solution does not use polymorphism. Although possibly possible, my C skills are not sufficient to know how to use it. Instead, I used a type content_t, that one can change to whatever fits.
One could extract the thunk out of the list's defintion and using it only abstractly, but doing so would make the code more complicated.
One could improve the parts of my code that aren't good C.