SCIP in C++11 ― 2.2.2節 その1

階層構造と問題2.24～2.28

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

tupleやlistを使ってたときは、特に表示系を作るのに結構難儀したが、

Compositeパターンは強い。えらい楽だった。

----

// count-leaves

const int countLeaves(const List& listTree)

{

    if(isNull(listTree)){return(0);}

    if(!isPair(listTree)){return(1);}

    return(countLeaves(car(listTree))+countLeaves(cdr(listTree)));

}

// deep-reverse

const List deepReverse(const List& listTree)

{

    if(isNull(listTree)){return(makeList());}

    if(!isPair(listTree)){return(listTree);}

    return(append(deepReverse(cdr(listTree)),

                  makeList(deepReverse(car(listTree)))));

}

const List fringe(const List& listTree)

{

    if(isNull(listTree)){return(makeList());}

    if(!isPair(listTree)){return(makeList(listTree));}

    return(append(fringe(car(listTree)),fringe(cdr(listTree))));

}

//---------abstraction barrier---------

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;

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

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

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

    cout<<"(fringe x) = "<<listString(fringe(x227_3))<<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)