八王子からの帰り,C++のテンプレートでコンパイル時にリストを使った計算をさせようとテンプレートでリストを表現する方法を考えていた.結論としては,値を直接使わずに,全てを型の上で処理してしまえばいい.ためしにリストを作って表示,foldr, map を書いてみた.まあ,int 限定にしているけど.一般化は容易でしょう.
#include <iostream> using namespace std; #define cons(x, y) Cons< Int< x >, y > #define nil Nil // nil or [] struct Nil {}; // cons h t or h:t template <typename H, typename T> struct Cons { typedef H head; typedef T tail; }; // element of lists template<int n> struct Int{ enum {val = n}; static void print() { cout << n; } }; // printer template <typename L> struct ListPrinter { static void print(){ cout << '['; L::head::print(); ListPrinter<typename L::tail>::print2(); cout << ']'; } static void print2(){ cout << ','; L::head::print(); ListPrinter<typename L::tail>::print2(); } }; template <> struct ListPrinter<Nil> { static void print(){ cout << '[' << ']'; } static void print2(){ } }; // foldr function // foldr f e [] = e // foldr f e (h:t) = f h (foldr f e t) // cons case: template<template<typename,typename> class F, typename E, typename L > struct Foldr{ typedef typename F<typename L::head, typename Foldr<F,E,typename L::tail>::val >::val val; }; // nil case: template<template<typename,typename> class F, typename E> struct Foldr<F,E,Nil>{ typedef E val; }; // map function // map f [] = [] // map f (h:t) = f h:(map f t) // cons case: template<template<typename> class F, typename L > struct Map{ typedef Cons< typename F<typename L::head>::val , typename Map<F, typename L::tail>::val> val; }; // nil case: template<template<typename> class F> struct Map<F,Nil>{ typedef Nil val; }; //addition operator template <typename X, typename Y> struct Add { typedef Int<X::val + Y::val> val; }; // zero typedef Int<0> Zero; //douoblring operator template <typename X> struct Double{ typedef Int<X::val + X::val> val; }; int main(int argc, char *argv[]) { typedef cons(4, cons(3, cons(2, cons(1, nil)))) l; typedef cons(5, l) l2; ListPrinter< l >::print(); cout << endl; ListPrinter< l2 >::print(); cout << endl; typedef Foldr<Add, Zero, l2>::val sum; sum::print(); cout << endl; typedef Map<Double, l2>::val l3; ListPrinter< l3 >::print(); cout << endl; }
とまあ,考えてみたわけだけど,あとに別の用件で google で検索かけたらThe Boost C++ Metaprogramming Libraryとかいうものを見つけてしまった.boost に含まれいてるらしいが,上で考えたのと同じで全てを型で扱ってコンパイル時計算をしているらしい.いやぁ,やっぱ同じことを考える人はいるもんだなぁ.でも,こいつにはサイズに制限があるらしい(上限を上げるようにすればいいんだけど).ということで,上の Cons/Nil は制限一切無いので捨てたもんじゃない(はず?).
- Newer: ことはじめ