source: liblaziness/list.h @ 29

#ifndef __LIST_H__
#define __LIST_H__
#include "lazy.h"
// #include "functional.h"
#include <exception>
#include <iostream>

class EmptyList : std::exception { };

template <typename T>
class List
{
        public:
                typedef T list_item_type;
                List() { }
                virtual ~List() { }
                virtual Lazy<T> getHead() = 0;
                virtual Lazy< List<T> > getTail() = 0;
                virtual bool isEmpty() = 0;
};

template <typename T>
using LazyList = R<LazyBase<List<T>>, true>;

template <typename T>
class Cons : public List<T>
{
        public:
                typedef T list_item_type;
                Cons(Lazy<T> head, LazyList<T> tail) : List<T>(), head(head), tail(tail) { }
                virtual ~Cons() { }
                virtual Lazy<T> getHead() { return head; }
                virtual LazyList<T> getTail() { return tail; }
                virtual bool isEmpty() { return false; }
        private:
                Lazy<T> head;
                LazyList<T> tail;
};

template <typename T>
class Nil : public List<T>
{
        public:
                typedef T list_item_type;
                Nil() : List<T>() { }
                virtual ~Nil() { }
                virtual Lazy<T> getHead() { throw EmptyList(); }
                virtual LazyList<T> getTail() { throw EmptyList(); }
                virtual bool isEmpty() { return true; }

                static LazyList<T> instance;
        private:
                static LazyList<T> initInstance();
};

template<typename T>
LazyList<T> Nil<T>::instance = Nil<T>::initInstance();

template<typename T>
LazyList<T> Nil<T>::initInstance()
{
        auto rNil = Ref::mk<Nil<T>>();
        return suspend(rNil);
}

template <typename T>
LazyList<T> cons(Lazy<T> head, LazyList<T> tail)
{
        return suspend<List<T>> (Ref::mk<Cons<T>> (head, tail));
}

template <typename T>
inline LazyList<T> operator<<=(Lazy<T> head, LazyList<T> tail)
{
        return cons(head, tail);
}

/*template <typename T>
class LLIterator
{
        public:
                LLIterator(LazyList<T> list) : list(list) { }
                T& operator *()
                {
                        return lazyVal(head(list)).deref();
                }
                LLIterator& operator++()
                {
                        list = tail(list);
                }
        private:
                LazyList<T> list;
};*/

template <typename T>
LazyList<T> drop(LazyList<T> list, Int i)
{
        if (i == 0L)
        {
                return list;
        }
        else
        {
                return drop(list.tail(), i - 1L);
        }
}

/**** iterate ****/

template <typename T>
LazyList<T> iterate(Delegate1<LazyBase<T>, LazyBase<T>> fun, Lazy<T> init)
{
        return mkLazy(mkLFun([] (decltype(fun) fun, decltype(init) init) {
                return Ref::mk<Cons<T>> (init, iterate (fun, fun(init)));
        }, fun, init));
}

/**** map ****/

template <typename TSource, typename TDest>
LazyList<TDest> map(Delegate1< LazyBase<TDest>, LazyBase<TSource> > fun, LazyList<TSource> l)
{
        return mkLazy(mkLFun([] (decltype(fun) fun, decltype(l) l) {
                return Ref::mk<Cons<TDest>> (fun(l.head()), map(fun, l.tail()));
        }, fun, l));
}

/**** filter ****/
template <typename T>
LazyList<T> filter(Delegate1<bool, LazyBase<T>> fun, LazyList<T> l)
{
        return mkLazy(mkLFun([] (decltype(fun) fun, decltype(l) l) {
                auto lx = l;
                while (*fun(lx.head()) == false)
                {
                        lx = lx.tail();
                }
                return Ref::mk<Cons<T>> (lx.head(), filter(fun, lx.tail()));
        }, fun, l));
}

/**** zipWith ****/

template <typename T> // TODO allow different lists
LazyList<T> zipWith(Delegate2<LazyBase<T>, LazyBase<T>, LazyBase<T>> fun, LazyList<T> l1, LazyList<T> l2)
{
        return mkLazy(mkLFun([] (decltype(fun) fun, decltype(l1) l1, decltype(l2) l2) {
                return Ref::mk<Cons<T>> (fun(l1.head(), l2.head()), zipWith(fun, l1.tail(), l2.tail()));
        }, fun, l1, l2));
}

/**** specialization ****/
template <typename T>
class R<LazyBase<List<T>>, true> : public R<LazyBase<List<T>>, false>
{
        protected:
                // passing protected constructor
                inline R(int i) : R<LazyBase<List<T>>, false>(i) { }
        public:
                inline R() : R<LazyBase<List<T>>, false>() { }
                template<typename U, bool od> inline R(R<LazyBase<U>, od>&  o) : R<LazyBase<List<T>>, false>(o, 0)
                {
                        _assert_subclass<U, List<typename U::list_item_type>> ERRORList;
                        _assert_subclass<typename U::list_item_type, T> ERRORItem;
                }
                template<typename U, bool od> inline R(R<LazyBase<U>, od>&& o) : R<LazyBase<List<T>>, false>(o, 0)
                {
                        _assert_subclass<U, List<typename U::list_item_type>> ERRORList;
                        _assert_subclass<typename U::list_item_type, T> ERRORItem;
                }
                // passing operator=
                template<typename U, bool od> inline R<LazyBase<List<T>>, true>& operator=(R<LazyBase<U>, od>&  o)
                {
                        _assert_subclass<U, List<typename U::list_item_type>> ERRORList;
                        _assert_subclass<typename U::list_item_type, T> ERRORItem;
                        R<LazyBase<List<T>>, false>::copy(o);
                        return *this;
                }
                template<typename U, bool od> inline R<LazyBase<List<T>>, true>& operator=(R<LazyBase<U>, od>&& o)
                {
                        _assert_subclass<U, List<typename U::list_item_type>> ERRORList;
                        _assert_subclass<typename U::list_item_type, T> ERRORItem;
                        R<LazyBase<List<T>>, false>::copy(o);
                        return *this;
                }
                // additional functionality
                inline Lazy<T>     head() { return this->deref().get().deref().getHead(); }
                inline LazyList<T> tail() { return this->deref().get().deref().getTail(); }
                inline static LazyList<T> iterate(Delegate1<LazyBase<T>, LazyBase<T>> fun, Lazy<T> init) { return ::iterate(fun, init); }
                inline static LazyList<T> iterate(Delegate1<LazyBase<T>, LazyBase<T>> fun, T init) { return ::iterate(fun, suspend(init)); }
                template<typename U> inline LazyList<U> map(Delegate1<LazyBase<U>, LazyBase<T>> fun) { return ::map(fun, *this); }
                inline LazyList<T> filter(Delegate1<bool, LazyBase<T>> fun) { return ::filter(fun, *this); }
                inline LazyList<T> drop(Int i) { return ::drop(*this, i); }
                // keep reference makeable with Ref::mk
                friend Ref;
};

#endif