Skip to content

Instantly share code, notes, and snippets.

@dobrokot
Last active November 4, 2015 12:34
Show Gist options
  • Save dobrokot/0ebc9c9fbd55050dcee7 to your computer and use it in GitHub Desktop.
Save dobrokot/0ebc9c9fbd55050dcee7 to your computer and use it in GitHub Desktop.
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;}) );
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment