Folding typelist

From: brianchon_pascal (brianchon_pascal_at_[hidden])
Date: 2002-01-05 16:18:34

I learned from Andrei Alexandrescu's Modern C++ Design for the idea 
of typelist. I missed any reference to the "fold" functional. I'm 
posting my thoughts here, since it's the first time for me to post 
things like this, if someone else had posted something similar, then 
please forgive me for my ignorance.

// [code typelist_fold]
struct nil {};

template<typename H, typename T>
struct cons {
    typedef H head_type;
    typedef T tail_types;
};

template<typename L, template<class, class> class F, typename E>
struct fold {
    typedef typename fold<typename L::tail_types, 
                          F, 
                          F<typename L::head_type, E> 
                     >::traits traits;
};

template<template<class, class> class F, typename E>
struct fold<nil, F, E> {
    typedef typename E::traits traits;
};
// [end of typelist_fold]

typedefs, enums and static member functions (which are intended to 
wrap global functions) can be put into member struct "traits", 
therefore they may be carried around without knowning their exact 
signatures.

Example: calculating length of typelist

// [code list_count]
template<typename X, typename E>
struct iter_count {
    struct traits {
        typedef typename E::traits base_traits;
        enum {Count = base_traits::Count+1};
    };
};

struct nil_count {
    struct traits {
        enum {Count = 0};
    };
};

template<typename L>
struct list_count {
    enum {Count = fold<L, iter_count, nil_count>::traits::Count};
};

// then given

typedef cons<int, cons<bool, cons<char, nil> > > my_type_list;

list_count<my_type_list>::Count; // returns 3
// [end of list_count]

Example: find position of element type

// [code list_pos]
template<typename T, typename X> 
struct eq_types {enum {Result = false};};

template<typename T> 
struct eq_types<T, T> {enum {Result = true};};

template<typename X, typename E>
struct iter_pos {
    struct traits {
        typedef typename E::traits base_traits;
        typedef typename base_traits::arg_type arg_type;
        enum {Found = base_traits::Found 
                   || eq_types<arg_type, X>::Result};
        enum {Pos = Found? base_traits::Pos : base_traits::Pos+1};
    };
};  

template<typename T>
struct nil_pos {
    struct traits {
        typedef T arg_type;
        enum {Found = false};
        enum {Pos = 0};
    };
};

template<typename L, typename T>
struct list_pos {
    enum {Pos = fold<L, iter_pos, nil_pos<T> >::traits::Pos};
};

list_pos<my_type_list, char>::Pos // returns 2
list_pos<my_type_list, float>::Pos // returns 3 (not found)
// [end of list_pos]

Example: rev and cat typelist

// [code list_rev list_cat]
template<typename X, typename E>
struct iter_cat {
    struct traits {
        typedef typename E::traits base_traits;
        typedef cons<X, typename base_traits::types> types;
    };
};  

template<typename L>
struct nil_cat {
    struct traits {
        typedef L types;
    };
};

template<typename L>
struct list_rev {
    typedef 
    typename fold<L, iter_cat, nil_cat<nil> >::traits::types types;
};

template<typename L1, typename L2>
struct list_cat {
    typedef typename fold<list_rev<L1>::types, 
                          iter_cat, 
                          nil_cat<L2> 
                     >::traits::types types;
};

list_cat<my_type_list, my_type_list>::types // returns concat of 2 
my_type_lists
// [end of list_rev list_cat]

Finally wrapping functions:

// [code list_print_pos_in_list]
template<typename X, typename E>
struct iter_print_pos_in_list {
    struct traits {
        typedef typename E::traits base_traits;
        typedef typename base_traits::types types;
        static ostream& Print(ostream& os) {
            return base_traits::Print(os) << list_pos<types, X>::Pos
                                          << ' ';
        }
    };
};  

template<typename L>
struct nil_print_pos_in_list {
    struct traits {
        typedef L types;
        static ostream& Print(ostream& os) {
            return os;
        }
    };
};

template<typename L1, typename L2>
struct list_print_pos_in_list {
    static ostream& Print(ostream& os) {
        return fold<L1, 
                    iter_print_pos_in_list, 
                    nil_print_pos_in_list<L2> 
               >::traits::Print(os);
    }
};

list_print_pos_in_list<
    list_cat<my_type_list, my_type_list>::types, 
    my_type_list>::Print(std::cout) << endl; // prints 0 1 2 0 1 2
// [end of list_print_pos_in_list]

"fold" can be used to abstract the iteration of a chain of functions, 
such as filters statically, for example:

void* SmallBlockAlloc::Alloc(size_t Min) {
    return Alloc32Bytes::Alloc(Min) 
        || Alloc64Bytes::Alloc(Min)
        || Alloc128Bytes::Alloc(Min);
}

SmallBlockAlloc can also be an element filter later.

Comments are welcome, thank you.

brianchon
brianchon_pascal_at_[hidden]