なんか、こじらせた。
これだけではLispになりませんが、もだった材料はそろうみたいなので、できそうな気がします。たぶん。
#include <iostream> // 等値 template<typename T, typename U> struct Eq { static const bool condition = false; }; template<typename T> struct Eq<T, T> { static const bool condition = true; }; // 論理和 template<typename T, typename U, bool cond = T::condition> struct Or; template<typename T, typename U> struct Or<T, U, true> { static const bool condition = true; }; template<typename T, typename U> struct Or<T, U, false> { static const bool condition = U::condition; }; // 論理積 template<typename T, typename U, bool cond = T::condition> struct And; template<typename T, typename U> struct And<T, U, true> { static const bool condition = U::condtion; }; template<typename T, typename U> struct And<T, U, false> { static const bool condition = false; }; // 分岐 template<bool Condition, typename T, typename U> struct If { typedef T type; }; template<typename T, typename U> struct If<false, T, U> { typedef U type; }; // 終端 struct Nil {}; // リスト template<typename T, typename U> struct List { typedef T head; typedef U tail; static std::ostream& value(std::ostream& out) { return out << head::value << tail::value; } }; template<typename T> struct List<T, Nil> { typedef T head; typedef Nil tail; static std::ostream& value(std::ostream& out) { return out << head::value; } }; // 構築 template<typename Head, typename List> struct Cons; template<typename Head, template<typename, typename> class List, typename H, typename T> struct Cons<Head, List<H, T>> { typedef List<Head, List<H, T>> type; }; // CAR template<typename List> struct Car; template<template<typename, typename> class List, typename H, typename T> struct Car<List<H, T>> { typedef H type; }; // CDR template<typename List> struct Cdr; template<template<typename, typename> class List, typename H, typename T> struct Cdr<List<H, T>> { typedef T type; }; // 包含検査 template<typename X, typename List> struct Member { static const bool condition = Or<Eq<X, typename List::head>, Member<X, typename List::tail>>::condition; }; template<typename _> struct Member<_, Nil> { static const bool condition = false; }; // 挿入 template<typename X, typename List> struct Insert; template<typename X, template<typename, typename> class List, typename H, typename T> struct Insert<X, List<H, T>> { typedef typename If< Member<X, List<H, T>>::condition, List<H, T>, typename Cons<X, List<H, T>>::type >::type type; }; // 利用例 template<char C> struct Char { static const char value = C; }; typedef List<Char<'A'>, List<Char<'B'>, List<Char<'C'>, Nil>>> ABC; typedef Insert<Char<'A'>, ABC>::type ABC_; typedef Insert<Char<'D'>, ABC>::type DABC; int main(int, char* []) { std::cout << ABC::value << std::endl; std::cout << ABC_::value << std::endl; std::cout << DABC::value << std::endl; return 0; }
実行結果。
ABC ABC DABC