haskell_like_lazy_lists.cpp

haskell_like_lazy_lists.cpp

#include <memory>
#include <functional>
#include <iostream>
#include <assert.h>

struct ListNode {
private:
    typedef std::function<std::shared_ptr<ListNode>()> NextGetterFunc;
    NextGetterFunc next_getter;
    std::shared_ptr<ListNode> cached_next;

public:
    std::shared_ptr<ListNode> GetNext() {
        if (next_getter) {
            cached_next = next_getter();
            next_getter = NextGetterFunc(); // make empty
        }
        return cached_next;
    }

    ListNode(int value, std::function<std::shared_ptr<ListNode>()> next_getter)
        : next_getter(next_getter)
        , value(value)
    {
    }

    const int value = 0;
};

typedef std::shared_ptr<ListNode> List;


void Print(List l) {
    if (!l) {
        std::cout << '\n';
    } else {
        std::cout << l->value << ';';
        Print(l->GetNext());
    }
}

List MakeRange(int start, int count) {
    if (count == 0) {
        return List(nullptr);
    }
    return List(new ListNode(start, [=](){ return MakeRange(start + 1, count-1); }));
}

int GetLast(List l) {
    assert(l);
    List next = l->GetNext();
    if (next) {
        return GetLast(next);
    } else {
        return l->value;
    }
}

List Change(int val, List l) {
    if (!l)
        return l;

    if (l->value == val) {
        return List(new ListNode( GetLast(l), [=]() { return l->GetNext(); } ));
    } else {
        return List(new ListNode( l->value, [=]() { return Change(val, l->GetNext()); } ));
    }
}

template <class Func>
List ZipWith(List xs, List ys, Func f) {
    if (!xs || !ys) {
        return List();
    }
    return List(new ListNode(
        f(xs->value, ys->value),
        [=]() { return ZipWith(xs->GetNext(), ys->GetNext(), f); }
    ));
}

int main() {
    List l = MakeRange(1, 10);
    Print(l);
    List l2 = Change(5, l);
    Print(l2);
    Print(ZipWith(l, l2, [](int i, int j) { return i - j; }));

    //cause memory leak
    List fib(new ListNode(0,
        [&]() { return List(new ListNode(1, [&]() {
            return ZipWith(fib, fib->GetNext(), [](int i, int j) { return i + j; });
        }));}
    ));

    Print( ZipWith(fib, l, [](int i, int){return i;}) );
}