# Implement lazy lists, preferably in a language you don't know well [closed]

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:

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.
• What should the behaviour be when calling zipWith on two lists of different lengths?
– balpha
Commented May 1, 2011 at 18:01
• @balpha: I choosed Haskells behavior: If either of the lists are nil, return nil. Commented May 1, 2011 at 20:02
• @balpha: In Haskell, zipWith stops when either list runs out of items. Hence, zipWith (+) [1,2,3,4,5] [0,0,0] == [1,2,3]. However, this doesn't matter for the Fibonacci algorithm above, as both arguments to zipWith are infinite lists. Commented May 1, 2011 at 21:52
• This challenge had a hidden surprise in it: you need to do something special to implement fibs correctly, as it depends on itself. I updated the question to elaborate on lazy recursion. FUZxxl figured it out by him/her/itself. Commented May 1, 2011 at 22:56
• What do you mean by "working incrementally" when you print a big list? Commented May 2, 2011 at 22:03

## PostScript

I've played with PostScript before, but I wouldn't say I know it particularly well (in fact, my guess is that you can count the number of people in the world that really know PostScript using one hand).

I deviated from your spec in that the function that's used to create a thunk is allowed to return another thunk; force will keep evaluating until the result is a nil or a cons.

The lists are implemented as dictionaries:

<< /type /nil >>

<< /type /cons
/tail someList >>

<< /type /thunk
/func evaluationFunction >>

<< /type /dataThunk
/func evaluationFunction
/data someValueToBePassedToTheFunction >>


The code follows. Note that we're overwriting some builtin operators (in particular print; I haven't checked if there are more); in real world use, this would have to be watched out for. Of course there will be no real world use, so that's fine.

% before2 before1 before0  <| procedure |>  after1 after0


i.e. showing the expected stack contents before the call and the resulting stack contents after the call. The comments within the procedures show the content of the stack after the particular line has been executed.

% Helper procedure that creates a dictionary with the top two elements as keys
% and the next two elements as values.
%
% value1 value2 key1 key2  <| _twodict |>  << /key1 /value1 /key2 /value2 >>
/_twodict {
<< 5 1 roll    % << value1 value2 key1 key2
4 2 roll       % << key1 key2 value1 value2
3 2 roll       % << key1 value1 value2 key2
exch >>
} def

/nil {
<< /type /nil >>
} def

% item list  <| cons |>  consCell
/cons {
dup /type /cons put
} def

% constructs a thunk from the function, which will be called with no
% arguments to produce the actual list node. It is legal for the function
% to return another thunk.
%
% func  <| thunk |>  lazyList
/thunk {
/thunk /func /type _twodict
} def

% A dataThunk is like a regular thunk, except that there's an additional
% data object that will be passed to the evaluation function
%
% dataObject func  <| dataThunk |>  lazyList
/dataThunk {
/data /func _twodict
dup /type /dataThunk put
} def

% lazyList  <| force |>  consOrNil
/force {
dup /type get dup
/thunk eq
{
pop
dup /func get exec exch copy
force
dup /func undef
}
{
/dataThunk eq
{
dup dup /data get exch
/func get exec exch copy
force
dup dup /func undef /data undef
} if
} ifelse
} def

/empty {
force
/type get
/nil eq
} def

} def

/tail {
force /tail get
} def

/print {
dup empty not
{
dup
tail
print
}
{
pop
} ifelse
} def

% sourceList n  <| take |>  resultingList
/take {
/source /n _twodict
{
dup /source get exch    % source data
/n get 1 sub dup        % source n-1 n-1
-1 eq
{
pop pop nil
}
{                       % source n-1
exch                % n-1 source
3 1 roll            % head n-1 source
tail
cons
} ifelse
}
dataThunk
} def

% sourceList1 sourceList2 func  <| zipWith |>  resultList
/zipWith {
3 1 roll
2 array astore                  % func [L1 L2]
/func /sources _twodict
{
dup /sources get aload pop  % data L1 L2
2 copy empty exch empty or
{
pop pop pop nil
}
{
dup head exch tail      % data L1 H2 T2
3 2 roll
dup head exch tail      % data H2 T2 H1 T1
exch                    % data H2 T2 T1 H1
4 3 roll                % data T2 T1 H1 H2
5 4 roll /func get      % T2 T1 H1 H2 func
dup 4 1 roll            % T2 T1 func H1 H2 func
exec                    % T2 T1 func NEWHEAD
4 2 roll                % func NEWHEAD T2 T1
exch 4 3 roll           % NEWHEAD T1 T2 func
zipWith cons
} ifelse
}
dataThunk
} def


Load this into Ghostscript, ignoring the displayed page -- we're only working with the interpreter. Here's the Fibonacci algorithm:

[balpha@localhost lazylist]\$ gs lazylist.ps
GPL Ghostscript 8.71 (2010-02-10)
This software comes with NO WARRANTY: see the file PUBLIC for details.
GS> /fibs 0 1 { fibs fibs tail { add } zipWith } thunk cons cons def
GS> fibs 40 take print
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
GS>


% creates an infinite list that starts with the given value, incrementing
% by one for each additional element
%
% startValue  <| count |>  lazyList
/count {
{
dup
cons
}
dataThunk
} def

% apply the given function to each element of the source list, creating
% a (lazy) list that contains the corresponding results
%
% sourceList function  <| map |> resultList
/map {
/source /func _twodict
{
dup /func get exch
/source get                 % func source
dup empty not
{
2 index                 % func source head func
exec 3 1 roll           % newHead func source
tail exch map cons
}
{
pop pop nil
} ifelse
}
dataThunk
} def


Start counting at 5, multiply each element of the resulting list with 3, and display the first ten values:

GS> 5 count { 3 mul } map 10 take print
15
18
21
24
27
30
33
36
39
42


Regarding polymorphism: Even though PostScript is strongly typed, it allows arbitrary types as dictionary values, so you can throw in anything you like:

GS> 1337 [ 42 3.14 ] << /key /value >> (Hello world) 3 count
GS<5> cons cons cons cons 10 take print
1337
[42 3.14]
-dict-
(Hello world)
3
4
5
6
7
8
GS>


Note that type errors, e.g. from trying to add strings to numbers, will only happen at evaluation time:

GS> (some string) (another string) nil cons cons
GS<1> 13 27 nil cons cons
GS<2> { add } zipWith      % no error yet
GS<1> print

• Amazing. (How) does force memoize returned values? Commented May 2, 2011 at 13:40
• @JoeyAdams: It does indeed. After evaluating a thunk, the copy operator copies the contents of the evaluated version into the original, overwriting /type and possibly setting other values. After recursively evaluating until we have a nil or cons, it also (via undef) removes /func and, where applicable, /data. The last step isn't strictly necessary (/func and /data would just be ignored), but leaving this step out would leak even more memory :)
– balpha
Commented May 2, 2011 at 14:01

## 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 {
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->listA;
list* listB = args->listB;
list* listC;

content_t* (*f)(content_t*,content_t*) = args->f;

free(args);
return nil();
} else {
args->listA = tail(listA);
args->listB = tail(listB);
listC = thunk(__zipWith,args);
}
}

list* zipWith(content_t* (*f)(content_t*,content_t*),list* listA, list* listB) {
struct __zipArgs* args = malloc(sizeof(struct __zipArgs));
args->f = f;
args->listA = listA;
args->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(&one_,NULL);
list* two  = cons(&zero_,one);
one->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.
• Nice submission, especially for being a C first-timer. Regarding polymorphism, if you're willing to allocate all your content on the heap, you could use void* as the type of content_t. Commented May 1, 2011 at 17:25
• @Casey: Thank you very much. I thought of using void* too, but I thought that would sidestep the type system too far. Isn't that possible using templates? Commented May 1, 2011 at 17:51
• C doesn't have templates, that is C++, but yes you could use C++ templates to make it generic. Commented May 1, 2011 at 17:56
• I don't know how to use them. But I guess, it's just that C is kind of limited in terms of it's typesystem. - I wasn't even able to code this program without using void* and friends. Commented May 1, 2011 at 18:02
• “The member kind is kind of a tag.” You could just call it tag, as that's a pretty accepted term for the concept (e.g. tagged union, Spineless Tagless G-machine. On the other hand, "kind" has a different meaning in a Haskell context: the type of a type. Int has kind *, [] has kind * -> *, and (,) has kind * -> * -> *. Commented May 2, 2011 at 1:17

## C++

This is the largest thing I've ever written in C++. I normally use Objective-C.

It's polymorphic but it doesn't free anything ever.

My main function (and the add function to ZipWith)ended up looking like this:

int add(int a, int b) {return a + b;}

int main(int argc, char **argv) {
int numFib = 15; // amount of fibonacci numbers we'll print
if (argc == 2) {
numFib = atoi(argv[1]);
}

// list that starts off 1, 1...
LazyList<int> fibo = LazyList<int>(new Cons<int>(1,
new LazyList<int>(new Cons<int>(1))));
// zip the list with its own tail
LazyList<int> *fiboZip = LazyList<int>::ZipWith(add, &fibo, fibo.Tail());
// connect the begin list to the zipped list
fibo.Tail() -> ConnectToList(fiboZip);

// print fibonacci numbers
int *fibonums = fibo.Take(numFib);
for (int i=0; i<numFib; i++) cout << fibonums[i] << " ";

cout<<endl;

return 0;
}


This gives

 ./lazylist-fibo 20
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765


The classes work like this:

make a thunk:    LazyList<T>(new Thunk<T>( function, *args ))
make empty list: LazyList<T>(new Nil<T>())
make cons:       LazyList<T>(new Cons<T>( car, *cdr ))

list empty:      list.Empty()
list's tail:     list.Tail()
zipWith:         LazyList<T>::ZipWith(function, a, b)
take:            list.Take(n)
print:           list.Print()


Full source: here. It's a mess, mainly because it's in one big file.

• Excellent work, and thanks for taking "throw a fit" literally :-) I am by no means a C++ expert, but a more C++-y way to implement Thunk might be to use a function object (a.k.a. "functor") (that is, overload the () operator), and to use inheritance to avoid having to use void* . See here for a trivial example of doing that. Commented May 2, 2011 at 21:21
• The full source link is dead now. Could you re-upload it? gist.github.com is a good place to put it. Commented Dec 28, 2011 at 3:37
• @JoeyAdams: done. Commented Jan 1, 2012 at 15:55

## Python

Doesn't use generators to implement the list, just to implement the __iter__ method for use with for.

class Node(object):
self.__tail__ = tail

def force(self):
return self

def empty(self):
return False

def tail(self):
return self.__tail__

def zip_with(self, func, other):
def gen_func():
if other.empty():
return other
return Thunk(gen_func)

def __iter__(self):
while not self.empty():
self = self.tail()

def append(self, other):
while not self.tail().empty():
self = self.tail()
self.__tail__ = other

def take(self, n):
if n == 0:
return NullNode()
else:

def _print(self):
for item in self:
print item

class NullNode(Node):
def __init__(self):
pass

def empty(self):
return True

raise TypeError("cannot get head of nil")

def tail(self):
raise TypeError("cannot get tail of nil")

def zip_with(self, func, other):
return self

def append(self, other):
raise TypeError("cannot append to nil")

def take(self, n):
return self

class Thunk(Node):
def __init__(self, func):
self.func = func

def force(self):
node = self.func()
self.__class__ = node.__class__
if not node.empty():
self.__tail__ = node.tail()
return self

def empty(self):
return self.force().empty()

def tail(self):
return self.force().tail()

def take(self, n):
return self.force().take(n)


The Fibonacci list is created like this:

>>> from lazylist import *
>>> fib = Node(0, Node(1, NullNode()))
>>> fib.append(fib.zip_with(lambda a, b: a + b, fib.tail()))
>>>

• This is beautiful. My favorite line is self.__class__ = node.__class__. Note that this hits a NotImplemented exception when it gets up to 2971215073 (long), which is apparently an invalid argument to int.__add__. To support big integers, do fib.append(fib.zip_with(lambda a,b: a+b, fib.tail())) Commented May 2, 2011 at 23:49
• Why can't you append unto empty or thunk? Commented Feb 24, 2014 at 23:44

## Ruby

My first Ruby program. We represent all nodes as arrays, where the array length determines the type:

0: empty list
1: thunk (call the single element to get the cons cell)
2: cons cell (1st is head, 2nd is tail)


The code is then pretty straightforward, with a hack to reset the thunk function to set up the recursive fib.

def nil_()
return Array[]
end

def cons(a, b)
return Array[a, b]
end

def thunk(f)
return Array[f]
end

def force(x)
if x.size == 1
r = x[0].call
if r.size == 2
x[0] = r[0]
x.push(r[1])
else
x.pop()
end
end
end

def empty(x)
force(x)
return x.size == 0
end

force(x)
return x[0]
end

def tail(x)
force(x)
return x[1]
end

def zipWith(f, a, b)
return thunk(lambda {
if empty(a) or empty(b)
return nil_()
else
end
})
end

def take(n, x)
if n == 0
return nil_()
else
return cons(head(x), take(n - 1, tail(x)))
end
end

def print(x)
while not empty(x)
puts x[0]
x = x[1]
end
end

return x + y
end

T=thunk(nil)  # dummy thunk function
fibs=cons(0, cons(1, T))
T[0]=zipWith(method(:add), fibs, tail(fibs))[0]  # overwrite thunk function

print(take(40, fibs))

• You can use [...] instead of Array[...]. Commented May 3, 2011 at 21:28

A relatively new language, and I learned it by CTRL+Fing the Spec.

package main
import "fmt"

type List struct {
isNil, isCons, isThunk bool
tail *List
thunk (func() List)
}

func Nil() List {
return List { true, false, false, nil, nil, Nil }
}

func Cons(a interface { }, b List) List {
return List { false, true, false, &a, &b, Nil }
}

func Thunk(f(func() List)) List {
return List { false, false, true, nil, nil, f }
}

func Force(x List) List {
if x.isNil { return Nil()
} else if x.isCons { return Cons(*x.head, *x.tail) }
return Force(x.thunk())
}

func Empty(x List) bool {
return Force(x).isNil;
}

func Head(x List) interface { } {
y := Force(x)
if y.isNil { panic("No head for empty lists.") }
}

func Tail(x List) List {
y := Force(x)
if y.isNil { panic("No tail for empty lists.") }
return *y.tail
}

func Take(n int, x List) List {
if (n == 0) { return Nil() }
return Thunk(func() List {
y := Force(x)
return Cons(*y.head, Take(n - 1, *y.tail))
})
}

func Wrap(x List) List {
return Thunk(func() List {
return x
})
}

func ZipWith(f(func(interface { }, interface { }) interface { }), a List, b List) List {
return Thunk(func() List {
x, y := Force(a), Force(b)
if x.isNil || y.isNil {
return Nil()
}
});
}

func FromArray(a []interface { }) List {
l := Nil()
for i := len(a) - 1; i > -1; i -- {
l = Cons(a[i], l)
}
return l
}

func Print(x List) {
fmt.Print("[")
Print1(x)
fmt.Print("]")
}

func Print1(x List) {
y := Force(x)
if y.isCons {
z := Force(Tail(y))
if z.isCons { fmt.Print(", ") }
Print1(z)
}
}

func Plus(a interface { }, b interface { }) interface { } {
return a.(int) + b.(int)
}

func Fibs() List {

return Thunk(func() List {
return Cons(0, Cons(1, Thunk(func() List {
return ZipWith(Plus, Thunk(Fibs), Tail(Thunk(Fibs)))
})))
})
}

func Fibs0() List {
// alternative method, working
return Cons(0, Cons(1, Fibs1(0, 1)))
}

func Fibs1(a int, b int) List {
c := a + b
return Cons(c, Thunk(func() List { return Fibs1(b, c) }))
}

func CountUp(x int, k int) List {
return Cons(x, Thunk(func() List {
return CountUp(x + k, k)
}))
}

func main() {
//a := []interface{} { 0, 1, 2, 3 }
//l, s := FromArray(a), FromArray(a)
Print(Take(40, Fibs()))
}


The problem was fixed, by dealing with thunk-within-a-thunks. However, it seems the online compiler cannot take 40 elements, maybe because of memory. I will test it on my Linux later.

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368runtime: address space conflict: map() =

panic during panic


I tested the code with the online compiler, because I can't install Go on Windows easily.

• This is pretty nice and simple. However, instead of 3 bools, you could use a single tag whose possible values are constants generated by the iota constant generator. See an example in the Go Programming Language Specification, and an answer on StackOverflow. Commented May 1, 2011 at 21:51
• Your Fibs function doesn't work because Go uses strict evaluation, and Fibs recurses on itself without a terminating condition. Fibs0/Fibs1 uses a simple generator approach rather than the algorithm described in my post, so it doesn't meet the "requirements". I updated my post to elaborate on lazy recursion, which is needed to implement fibs = 0 : 1 : zipWith (+) fibs (tail fibs) . Commented May 1, 2011 at 22:44
• Cons(0, Cons(1, ZipWith(Plus, Thunk(Fibs), Tail(Thunk(Fibs))))), it goes out of memory Commented May 1, 2011 at 22:55
• I tried Cons(0, Cons(1, Thunk(func() List { return ZipWith(Plus, Thunk(Fibs), Thunk(func() List { return Tail(Fibs()) })) }))) and I get invalid memory address error Commented May 1, 2011 at 23:00
• Since you're still learning Go: You can make some much more elegant code than this using interfaces for the Lists and separate types for Thunks, etc. Commented May 2, 2011 at 14:31

# Crystal

Despite following the GitHub repository, I've never actually used Crystal until now. Crystal is a statically-typed Ruby variant with full type inference. Even though there's already a Ruby answer, Crystal's static typing led me to using polymorphism, rather than an array, to represent the nodes. Because Crystal does not allow modification of self, I created a wrapper class, named Node, that would wrap everything else and manage the thunks.

Along with the classes, I created the constructor functions lnil, cons, and thunk. I've never quite used Ruby for more than a 20-line script before, either, so the block stuff threw me off quite a bit.

I based the fib function off the Go answer.

class InvalidNodeException < Exception
end

abstract class LazyValue
end

class LNil < LazyValue
def empty?
true
end

def force!
self
end

raise InvalidNodeException.new "cannot get head of LNil"
end

def tail
raise InvalidNodeException.new "cannot get tail of Nil"
end

def take(n)
Node.new self
end
end

class Cons < LazyValue
def initialize(@car, @cdr)
end

def empty?
false
end

def force!
@cdr.force!
self
end

@car
end

def tail
@cdr
end

def take(n)
Node.new n > 0 ? Cons.new @car, @cdr.take n-1 : LNil.new
end
end

class Thunk < LazyValue
def initialize(&@func : (-> Node))
end

def empty?
raise Exception.new "should not be here!"
end

def force!
@func.call()
end

end

def tail
self.force!.tail
end

def take(n)
self.force!.take n
end
end

class Node
def initialize(@value = LNil.new)
end

def empty?
self.force!
@value.empty?
end

def force!
@value = @value.force!
self
end

self.force!
end

def tail
self.force!
@value.tail
end

def take(n)
self.force!
return @value.take n
end

def print
cur = self
while !cur.empty?
cur = cur.tail
end
end
end

def lnil
Node.new LNil.new
end

def cons(x, r)
Node.new Cons.new x, r
end

def thunk(&f : (-> Node))
Node.new Thunk.new &f
end

def inf(st=0)
# a helper to make an infinite list
f = ->() { lnil }
f = ->() { st += 1; cons st, thunk &f }
thunk { cons st, thunk &f }
end

def zipwith(a, b, &f : Int32, Int32 -> Int32)
thunk { a.empty? || b.empty? ? lnil :
end

def fibs
# based on the Go answer
fibs2 = ->(a : Int32, b : Int32) { lnil }
fibs2 = ->(a : Int32, b : Int32) { cons a+b, thunk { fibs2.call b, a+b } }
cons 0, cons 1, thunk { fibs2.call 0, 1 }
end

fibs.take(40).print
zipwith(inf, (cons 1, cons 2, cons 3, lnil), &->(a : Int32, b : Int32){ a+b }).print


I bent the rules a little because there isn’t yet a .NET solution here – or more generally an OOP solution except for the one in Python which uses inheritance, but it’s different enough from my solution to make both interesting (in particular since Python allows to modify the self instance, making the thunk implementation straightforward).

So this is C#. Full disclosure: I’m nowhere near a beginner in C# but I haven’t touched the language in a while since I currently have no use for it at the job.

The salient points:

• All classes (Nil, Cons, Thunk) derive from a common abstract base class, List.

• The Thunk class uses the Envelope-Letter pattern. This essentially emulates the self.__class__ = node.__class__ assignment in the Python source, since the this reference cannot be modified in C#.

• IsEmpty, Head and Tail are properties.

• All appropriate functions are implemented recursively and lazily (except for Print, which can’t be lazy) by returning thunks. For example, this is Nil<T>.ZipWith:

public override List<T> ZipWith(Func<T, T, T> func, List<T> other) {
return Nil();
}


… and this is Cons<T>.ZipWith:

public override List<T> ZipWith(Func<T, T, T> func, List<T> other) {
return Thunk(() => {
if (other.IsEmpty)
return Nil();

});
}


Unfortunately, C# has no multiple dispatch, otherwise I could also get rid of the if statement. Alas, no dice.

Now, I’m not really happy with my implementation. I’m happy so far because all of the above is totally straightforward. But. I feel that the definition of Fib is needlessly complicated since I need to wrap the arguments into thunks to make it work:

List<int> fib = null;
fib = List.Cons(0, List.Cons(1,
List.ZipWith(
(a, b) => a + b,
List.Thunk(() => fib),
List.Thunk(() => fib.Tail))));


(Here, List.Cons, List.Thunk and List.ZipWith are convenience wrappers.)

I would like to understand why the following much easier definition isn’t working:

List<int> fib = List.Cons(0, List.Cons(1, List.Nil<int>()));
fib = fib.Concat(fib.ZipWith((a, b) => a + b, fib.Tail));


given an appropriate definition of Concat, of course. This is essentially what the Python code does – but it’s not working (= throwing a fit).

/EDIT: Joey has pointed out the obvious flaw in this solution. However, replacing the second line with a thunk also yields an error (Mono segfaults; I’m suspecting a stack overflow which Mono doesn’t handle well):

fib = List.Thunk(() => fib.Concat(fib.ZipWith((a, b) => a + b, fib.Tail)));


The full source code can be found as a gist on GitHub.

• "Unfortunately, C# has no multiple dispatch" - you can get the effect using events, albeit that's rather hacky. Commented May 31, 2011 at 21:06
• The ironic thing about lazy evaluation is that it requires state to implement. fib.ZipWith and fib.Tail use the old fib, which remains [0,1] and does not change. Thus, you get [0,1,1] (I think), and your Take function doesn't let you take from null (Haskell's take does, though). Try wrapping the second line's rvalue in a thunk, so it will refer to the new fib rather than the old. Commented May 31, 2011 at 21:19
• @Peter Yes; you can also use the Visitor pattern to implement multiple dispatch but I wanted the solution to stay simple. Commented Jun 1, 2011 at 10:10
• @Joey Duh. It’s blindingly obvious now. However, the thunk solution still doesn’t work (see updated answer) but I’m too busy now to investigate. Commented Jun 1, 2011 at 10:13

## Pico

for the record, this solution uses a translation of scheme's delay force as defined in srfi-45. and builds lazy lists on top of that.

{
 scheme's srfi-45 begins here

_lazy_::"lazy";
_eager_::"eager";

lazy(exp())::[[_lazy_, exp]];
eager(exp)::[[_eager_, exp]];
delay(exp())::lazy(eager(exp()));

force(promise)::
{ content:promise[1];
if(content[1]~_eager_,
content[2],
if(content[1]~_lazy_,
{ promise_:content[2]();
content:promise[1];
if(content[1]~_lazy_,
{ content_:promise_[1];
content[1]:=content_[1];
content[2]:=content_[2];
promise_[1]:=content });
force(promise) })) };

 scheme's srfi-45 ends here

nil:delay([]);
is_nil(s):size(force(s))=0;
cons(a(),b()):delay([a(),b()]);
tail(s):force(s)[2];

zipWith(f,a,b):
lazy(if(is_nil(a)|is_nil(b),
nil,

fibs:void;
fibs:=cons(0, cons(1, zipWith(+,fibs,tail(fibs))));

take(c,s):
lazy(if((c=0)|(is_nil(s)),
nil,

print(s):
{ comma(s):
if(is_nil(s),
void,
if(!(is_nil(tail(s))), display(","));
comma(tail(s)) });
display("[");
comma(s);
display("]");
void };

print(take(40,fibs))

}


the output looks like this: (but depending on how tpico is patched it might have more double quotes in it. display normally prints strings with quotes. i.e. all appearances of [,,,] would have quotes around them like "[".)

[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]<void>


due to the limits of the integer datatype in tpico this fails at computing the 45th (or 46th offset) Fibonacci number.

note that tpico 2.0pl11 is broken in that begin(a,b) (which is commonly written as {a;b}) and the if function are not tail recursive. not to mention that it took me 5 years to figure out why begin wasn't tail recursive. also at that time i wrote the translation of srfi-45 in Pico. it turned out to be that begin was waiting for the value of b before returning when it didn't need to wait. and once i got that i was also able to fix if as it had the same problem. and there was this other error that made the meta level constructor make inoperative.

Pico lets a function control if its arguments are evaluated before the function is called or just packaged as thunks. for this code, i can ellipsis over the oddities of call by function.

Pico has no type inference. i thought about this for a while but i ran to a problem due to the oddities of call by function. i came up with the statement that types must encode the existence of bound variable names. but i was mainly thinking of how to adapt Hindley-Milner type inference to a subset of Pico without mutation. the main idea was that the type checker returns multiple possible schemes if there are more than one possible binding and the type check succeeds if there is at least one possible type scheme. a possible scheme is one that no type assignment conflicts.