SCIP in C++11 ― 2.2.1節 その4

階層構造と問題2.24～2.28

いよいよ木―Schemeではリストのリスト―が登場。

C++11側で対応する、tupleを要素に持つtupleは、

データ構造としてはすでに表現できているが、表示系listStringが対応していない。

tupleの要素にtupleがあったら、listStringを再帰呼び出しする必要があるが、

そのためにはまずtupleをtupleと認識しないといけない。

これは新ヘッダtype_traitsのis_compoundとかで出来るかと思ったら、

実行時の分岐ではダメだということが判明。

tupleの場合とtupleでない場合の分岐処理を実行時分岐のifで書くと、

tupleに対しては出来ない処理への分岐もコンパイラが評価しに行って、

「tupleではそれはできましぇ～ん」ってコンパイラに泣かれちゃうのね。

ifが問題1.6でいう意味での特殊形式になってない。

C++02までは関数内の変数の型は一度決まれば変わらなかったから、

ifの両方の分岐が評価できたが、型による分岐ではそうはいかないってことだ。

コンパイル時の分岐が必要になる。

まあこれはたぶん、C++11がというより現段階のgccの実装上の問題なのだろう。

でなければis_compoundとかの実行時型識別の存在意義がないし。

それともis_compoundとかはテンプレートパラメターのために使うのかな。

とにかくコンパイルが通らないんじゃしょうがない。

他のSTLコンテナ、例えばunordered_multisetとかで木を表現すると、、

問題によってはばっちりマッチするだろうけど。

SICPで出てくるような、いろんな型が混ぜこぜの一般的な木を表現するには、

tupleでないとぐちゃぐちゃになる。

結局テンプレートマッチングでコンパイル時分岐をさせるしかないんだろう。

前問でせっかくfor-eachで実装し直した表示系listStringは、

木構造再帰になったのでまた書き直し。

ここを楽にするには、さらにもう一段、抽象の壁を必要とするみたいだな。

木構造の再帰を抽象化するのはこれからやるから、そのうち見えてくるだろう。

抽象を得るにはまず具体を知らねば。問題2.24～2.28はそんな問題。

pair?にあたるisPairは、コンパイル時分岐を多用しているために、

多分使う機会は殆ど無いが、一応実装。

また、fringeのように、tupleの木から全く別の構造の木を、

しかもその構造が事前に予測できない木をを作るようなのは、

tupleに向いてない。vectorとかに収めた方がいい。

まあテンプレートでゴリゴリ頑張ればfringeが返すtuple型の予測は、

一応できるが、それは単にコードの二重化なので意味ないし。

ただ、tupleを渡しただけでは葉の型がすぐ明らかではない

（tupleのtupleだったりする）から、leafの型を別に渡すようにした。

以前との共通部分を含めると、ソースがだいぶ長くなってきた・・・。

そろそろライブラリにしたほうがいいか。

----

// pair?

template<typename TupleArg1,typename... TupleArgs>

constexpr bool isPair(const tuple<TupleArg1, TupleArgs...>& tupleList)

{

    return(true);

}

template<typename DataType>

constexpr bool isPair(const DataType& tupleList){

    return(false);

}

//print list and vector to string

template <typename Tuple1stArg, typename... TupleArgs>

void listStringElement

(const tuple<Tuple1stArg, TupleArgs...>& tupleList,

 stringstream& listSStream);//prototype

template <typename LeafType> void listStringElement

(const LeafType& leaf, stringstream& listSStream);

void listStringElement

(const NullTupleType& tupleList,stringstream& listSStream){}

template  <typename ...TupleArgs,typename... TupleTupleArgs>

void listStringElement

(const tuple<tuple<TupleTupleArgs...>,TupleArgs...>& tupleList,

 stringstream& listSStream)

{

    listSStream<<"(";

    listStringElement(car(tupleList),listSStream);

    listSStream<<")";

    if(!isNull(cdr(tupleList))){listSStream<<" ";}

    listStringElement(cdr(tupleList),listSStream);

}

template <typename Tuple1stArg, typename... TupleArgs>

void listStringElement

(const tuple<Tuple1stArg,TupleArgs...>& tupleList,

 stringstream& listSStream)

{

    listStringElement(car(tupleList),listSStream);

    if(!isNull(cdr(tupleList))){listSStream<<" ";}

    listStringElement(cdr(tupleList),listSStream);

}

template <typename LeafType> void listStringElement

(const LeafType& leaf, stringstream& listSStream)

{listSStream<<leaf;}

template <typename Tuple1stArg, typename... TupleArgs>

const string listString

(const tuple<Tuple1stArg,TupleArgs...>& tupleList)

{

    stringstream listSStream;

    listSStream<<"(";

    listStringElement(tupleList,listSStream);

    listSStream<<")";

    return(listSStream.str());

}

template <typename Argument>

const string listString(const vector<Argument> vectorList)

{

    stringstream listSStream("");

    listSStream<<"(";

    if(vectorList.size()>0){

        for_each(vectorList.begin(),vectorList.end(),

                 [&listSStream](const Argument& arg)

                 {listSStream<<arg<<" ";});

    }

    string tmpString(listSStream.str());

    tmpString[tmpString.size()-1]=')';

    return(tmpString);

}

template <typename LeafType>

const string listString(const LeafType& leaf)

{

    stringstream listSStream;

    listSStream<<leaf;

    return(listSStream.str());

}

// count-leaves

const int countLeaves(const NullTupleType& x){return(0);}

template<typename LeafType>

const int countLeaves(const LeafType& leaf){return(1);}

template<typename TupleArg1, typename... TupleArgs>

const int countLeaves(const tuple<TupleArg1,TupleArgs...>& x)

{return(countLeaves(car(x))+countLeaves(cdr(x)));}

// deep-reverse

const NullTupleType deepReverse(const NullTupleType& null)

{return(null);}

template<typename LeafType>

const LeafType deepReverse(const LeafType& leaf){return(leaf);}

template<typename TupleArg1,typename... TupleArgs>

const tuple<TupleArg1,TupleArgs...>

deepReverse(const tuple<TupleArg1,TupleArgs...>& tupleList)

{

    return(append(deepReverse(cdr(tupleList)),

                  makeList(deepReverse(car(tupleList)))));

}

//fringe

template<typename LeafType>

void fringeVectorize(const NullTupleType& null,

                     vector<LeafType>& leafList){}

template<typename LeafType>

void fringeVectorize (const LeafType& leaf,

                      vector<LeafType>& leafList)

{leafList.push_back(leaf);}

template<typename TupleArg1,typename... TupleArgs,typename LeafType>

void fringeVectorize(const tuple<TupleArg1,TupleArgs...>& tupleList,

                     vector<LeafType>& leafList)

{

    fringeVectorize(car(tupleList),leafList);

    fringeVectorize(cdr(tupleList),leafList);

}

template<typename TupleArg1,typename... TupleArgs,typename LeafType>

const vector<LeafType>

fringe(const tuple<TupleArg1,TupleArgs...>& tupleList, const LeafType leaf)

{

    vector<LeafType> leafList(0);

    fringeVectorize(tupleList,leafList);

    return(leafList);

}

int main(int argc, char** argv)

{

    auto tree1(cons(makeList(1,2),makeList(3,4)));

    cout<<"x="<<listString(tree1)<<endl;

    cout<<"(length x) = "<<length(tree1)<<endl;

    cout<<"(count-leaves x) = "<<countLeaves(tree1)<<endl;

    cout<<endl<<"(list x x)="

        <<listString(makeList(tree1,tree1))<<endl;

    cout<<"(length (list x x)) = "

        <<length(makeList(tree1,tree1))<<endl;

     cout<<"(count-leaves (list x x)) = "

         <<countLeaves(makeList(tree1,tree1))<<endl;

    

    cout<<endl<<"Excersize 2.24:"<<endl;

    auto tree2(makeList(1,makeList(2,makeList(3,4))));

    cout<<"(list 1 (list 2 (list 3 4))) = "<<listString(tree2)<<endl;

    cout<<endl<<"Excersize 2.25:"<<endl;

    auto tree3(makeList(1,3,makeList(5,7),9));

    cout<<"x2.25-1 = "<<listString(tree3)<<endl;

    cout<<"(car (cdr (car (cdr (cdr x25))))) = "

        <<listString(car(cdr(car(cdr(cdr(tree3))))))<<endl;

    cout<<endl;

    auto tree4(makeList(makeList(7)));

    cout<<"x2.25-2 = "<<listString(tree4)<<endl;

    cout<<"(car (car x2.25-2))) = "

        <<listString(car(car(tree4)))<<endl;

    cout<<endl;

    auto tree5(makeList

               (1,makeList

                (2,makeList

                 (3,makeList

                  (4,makeList

                   (5,makeList(6,7)))))));

    cout<<"x2.25-3 = "<<listString(tree5)<<endl;

    cout<<"(car (cdr (car (cdr (car (cdr (car "

        <<"(cdr (car (cdr (car (cdr(x2.25-3))))))))))))) = "

        <<listString(car(cdr

                         (car(cdr

                              (car(cdr

                                   (car(cdr

                                        (car(cdr

                                             (car(cdr(tree5)

                                                  ))))))))))))<<endl;

   

    cout<<endl<<"Excersize 2.26:"<<endl;

    auto x226(makeList(1,2,3));

    auto y226(makeList(4,5,6));

    cout<<"(append x y) = "<<listString(append(x226,y226))<<endl;

    cout<<"(cons x y) = "<<listString(cons(x226,y226))<<endl;

    cout<<"(list x y) = "<<listString(makeList(x226,y226))<<endl;

   

    cout<<endl<<"Excersize 2.27:"<<endl;

    auto x227(makeList(makeList(1,2),makeList(3,4)));

    cout<<"x = "<<listString(x227)<<endl;

    cout<<"(reverse x) = "<<listString(reverse(x227))<<endl;

    cout<<"(deep-reverse x) = "<<listString(deepReverse(x227))<<endl;

    auto x227_2(makeList(makeList(1,2),makeList(3,4),makeList(5,6)));

    cout<<endl<<"x = "<<listString(x227_2)<<endl;

    cout<<"(deep-reverse x) = "<<listString(deepReverse(x227_2))<<endl;

    auto x227_3(makeList(makeList(1,2,3),makeList(4,5,6),makeList(7,8,9)));

    cout<<endl<<"x = "<<listString(x227_3)<<endl;

    cout<<"(deep-reverse x) = "<<listString(deepReverse(x227_3))<<endl;

    cout<<endl<<"Excersize 2.28:"<<endl;

    const int leafDummy(0);

    cout<<"x = "<<listString(x227)<<endl;

    cout<<"(fringe x) = "<<listString(fringe(x227,leafDummy))<<endl;

    cout<<endl<<"x = "<<listString(x227_3)<<endl;

    cout<<"(fringe x) = "<<listString(fringe(x227_3,leafDummy))<<endl;

    return(0);

}

----

出力

----

x=((1 2) 3 4)

(length x) = 3

(count-leaves x) = 4

(list x x)=(((1 2) 3 4) ((1 2) 3 4))

(length (list x x)) = 2

(count-leaves (list x x)) = 8

Excersize 2.24:

(list 1 (list 2 (list 3 4))) = (1 (2 (3 4)))

Excersize 2.25:

x2.25-1 = (1 3 (5 7) 9)

(car (cdr (car (cdr (cdr x25))))) = 7

x2.25-2 = ((7))

(car (car x2.25-2))) = 7

x2.25-3 = (1 (2 (3 (4 (5 (6 7))))))

(car (cdr (car (cdr (car (cdr (car (cdr (car (cdr (car (cdr(x2.25-3))))))))))))) = 7

Excersize 2.26:

(append x y) = (1 2 3 4 5 6)

(cons x y) = ((1 2 3) 4 5 6)

(list x y) = ((1 2 3) (4 5 6))

Excersize 2.27:

x = ((1 2) (3 4))

(reverse x) = ((3 4) (1 2))

(deep-reverse x) = ((4 3) (2 1))

x = ((1 2) (3 4) (5 6))

(deep-reverse x) = ((6 5) (4 3) (2 1))

x = ((1 2 3) (4 5 6) (7 8 9))

(deep-reverse x) = ((9 8 7) (6 5 4) (3 2 1))

Excersize 2.28:

x = ((1 2) (3 4))

(fringe x) = (1 2 3 4)

x = ((1 2 3) (4 5 6) (7 8 9))

(fringe x) = (1 2 3 4 5 6 7 8 9)