Implement lazy lists, preferably in a language you don't know well

Question

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.

Answer 1

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

  content_t* (*f)(content_t*,content_t*) = args->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->listA = tail(listA);
    args->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->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);
  list* core = zipWith(__add,one,two);
  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.

Answer 2

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
   /head someValue
   /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.

The comments before the procedures are to be read as

% 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 {
    /head /tail _twodict
    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

/head {
    force /head get
} def

/tail {
    force /tail get
} def

/print {
    dup empty not
    {
        dup
        head ==
        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
            dup head            % n-1 source head
            3 1 roll            % head n-1 source
            tail
            exch take           % head rest
            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)
Copyright (C) 2010 Artifex Software, Inc.  All rights reserved.
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>

Two additional interesting functions:

% creates an infinite list that starts with the given value, incrementing
% by one for each additional element
%
% startValue  <| count |>  lazyList
/count {
    {
        dup
        1 add count
        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
        {
            dup head                % func source head
            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
Error: /typecheck in --add--

Answer 3

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 head:     list.Head()
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.

Edit: changed the link (the old one was dead).

Answer 4

Python

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

class Node(object):
    def __init__(self, head, tail):
        self.__head__ = head
        self.__tail__ = tail

    def force(self):
        return self

    def empty(self):
        return False

    def head(self):
        return self.__head__

    def tail(self):
        return self.__tail__

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

    def __iter__(self):
        while not self.empty():
            yield self.head()
            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:
            return Node(self.__head__, self.__tail__.take(n - 1))

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

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

    def empty(self):
        return True

    def head(self):
        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.__head__ = node.head()
            self.__tail__ = node.tail()
        return self

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

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

    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()))
>>> 

Answer 5

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

def head(x)
  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
      return cons(f.call(head(a), head(b)), zipWith(f, tail(a), tail(b)))
    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

def add(x, y)
  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))

Answer 6

Google Go

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

package main
import "fmt"

type List struct {
  isNil, isCons, isThunk bool
  head *interface { }
  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.") }
  return *y.head
}

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()
    }
    return Cons(f(*x.head, *y.head), ZipWith(f, *x.tail, *y.tail))
  });
}

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 {
    fmt.Print(Head(y))
    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() = 
throw: runtime: address space conflict

panic during panic

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

Answer 7

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

    def head
        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

    def head
        @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

    def head
        self.force!.head
    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

    def head
        self.force!
        @value.head
    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?
            puts cur.head
            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 :
            cons f.call(a.head, b.head), zipwith a.tail, b.tail, &f }
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

Answer 8

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();
  
          return Cons(func(Head, other.Head), Tail.ZipWith(func, other.Tail));
      });
  }
  

  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.

Answer 9

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()]);
head(s):force(s)[1];
tail(s):force(s)[2];

zipWith(f,a,b):
  lazy(if(is_nil(a)|is_nil(b),
         nil,
         cons(f(head(a),head(b)), zipWith(f,tail(a),tail(b)))));

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

take(c,s):
  lazy(if((c=0)|(is_nil(s)),
         nil,
         cons(head(s),take(c-1,tail(s)))));

print(s):
  { comma(s):
      if(is_nil(s),
        void,
        { display(head(s));
          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.