source: liblaziness/binmemoise.h @ 24

#ifndef __BINMEMOISE_H__
#define __BINMEMOISE_H__
#include "delegate.h"
#include "bintree.h"

template<typename T>
BinTree<T> code(Fun1<T, Int> fun)
{
        return mkLazy(mkFun([] (Fun1<T, Int> fun) {
                auto val = mkLazy(mkFun([] (Fun1<T, Int> fun) { return fun.invoke (Ref::mk (0L)); }));
                auto lFun = mkFun1([] (Fun1<T, Int> fun, R<Int> n) { return fun.invoke (Ref::mk (*n * 2L + 1L)); });
                auto rFun = mkFun1([] (Fun1<T, Int> fun, R<Int> n) { return fun.invoke (Ref::mk (*n * 2L + 2L)); });
                return Ref::mk <BinTree<T>> (code(lFun), val, code(rFun));
        }, fun));
}

template<typename T>
Fun1<T, Int> decode(BinTree<T> tree)
{
        return mkFun1([] (BinTree<T> tree, R<Int> n)
        {
                if (*n == 0L)
                {
                        return tree->get();
                }
                else if (*n % 2L == 1L)
                {
                        return (decode (tree->getLeft())).invoke (Ref::mk ((*n - 1L) / 2L));
                }
                else
                {
                        return (decode (tree->getRight())).invoke (Ref::mk ((*n - 2L) / 2L));
                }
        });
}

#endif