Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.
share|improve this question
    
What should the behaviour be when calling zipWith on two lists of different lengths? –  balpha May 1 '11 at 18:01
    
@balpha: I choosed Haskells behavior: If either of the lists are nil, return nil. –  FUZxxl May 1 '11 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. –  Joey Adams May 1 '11 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. –  Joey Adams May 1 '11 at 22:56
    
What do you mean by "working incrementally" when you print a big list? –  Lowjacker May 2 '11 at 22:03
show 3 more comments

8 Answers 8

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--
share|improve this answer
    
Amazing. (How) does force memoize returned values? –  Joey Adams May 2 '11 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 May 2 '11 at 14:01
add comment

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 Dropbox. 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.
share|improve this answer
    
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. –  Casey May 1 '11 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? –  FUZxxl May 1 '11 at 17:51
    
C doesn't have templates, that is C++, but yes you could use C++ templates to make it generic. –  Casey May 1 '11 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. –  FUZxxl May 1 '11 at 18:02
1  
“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 * -> * -> *. –  Joey Adams May 2 '11 at 1:17
add comment

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

share|improve this answer
2  
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. –  Joey Adams May 2 '11 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. –  Joey Adams Dec 28 '11 at 3:37
    
@JoeyAdams: done. –  marinus Jan 1 '12 at 15:55
add comment

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.

share|improve this answer
    
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. –  Joey Adams May 1 '11 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) . –  Joey Adams May 1 '11 at 22:44
    
Cons(0, Cons(1, ZipWith(Plus, Thunk(Fibs), Tail(Thunk(Fibs))))), it goes out of memory –  SHiNKiROU May 1 '11 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 –  SHiNKiROU May 1 '11 at 23:00
1  
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. –  cthom06 May 2 '11 at 14:31
show 3 more comments

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()))
>>> 
share|improve this answer
1  
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())) –  Joey Adams May 2 '11 at 23:49
1  
Why can't you append unto empty or thunk? –  PyRulez Feb 24 at 23:44
add comment

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))
share|improve this answer
    
You can use [...] instead of Array[...]. –  Lowjacker May 3 '11 at 21:28
add comment

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.

share|improve this answer
    
"Unfortunately, C# has no multiple dispatch" - you can get the effect using events, albeit that's rather hacky. –  Peter Taylor May 31 '11 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. –  Joey Adams May 31 '11 at 21:19
    
@Peter Yes; you can also use the Visitor pattern to implement multiple dispatch but I wanted the solution to stay simple. –  Konrad Rudolph Jun 1 '11 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. –  Konrad Rudolph Jun 1 '11 at 10:13
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.