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

並びの演算と問題2.33

木の演算の本格的な抽象化が始まる。

うまく連鎖がつながると気持ちいい～。

でもつながらない時はたいていテンプレートマッチングのミスで、

デバッグがとても大変。C++11の静的表明とか使ったほうがいいのかな。

最高収入のプログラマの給料を探すコードは書いてない。

確か先でやってたような気がするので、その時にでも。

----

//accumulation

template <typename Accumulate, typename LeafType>

const Accumulate accumulate

(const function<Accumulate(LeafType,Accumulate)>& operation,

 const Accumulate& initialValue,

 const List& sequence)

{

    if(isNull(sequence)){return(initialValue);}

    return(operation

           (value<LeafType>(car(sequence)),

            accumulate(operation,initialValue,cdr(sequence))));

}

//filter

template <typename LeafType>

const List filter

(const function<bool(LeafType)>& predicate,

 const List& sequence)

{

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

    if(predicate(value<LeafType>(car(sequence)))){

        return(cons(car(sequence),

                    filter(predicate,cdr(sequence))));

    }

    return(filter(predicate,cdr(sequence)));

}

//enumerate-interval

const List enumerateInterval(const int low, const int high)

{

    if(low>high){return(makeList());}

    return(cons(low,enumerateInterval(low+1,high)));

}

// enumerate-tree

const List enumerateTree(const List& listTree)

{return(fringe(listTree));}

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

const function<bool(int)> isOdd=

    [](const int x){return(x%2==1);};

const function<bool(int)> isEven=

    [](const int x){return(x%2==0);};

const function<int(int,int)> add=

    [](const int x, const int y){return(x+y);};

const function<int(int,int)> mul=

    [](const int x, const int y){return(x*y);};

const function<int(int)> square=

    [](const int x){return(x*x);};

const function<int(int)> fibonacci=[](const int n){

    if(0==n || 1==n){return(n);}

    return(fibonacci(n-1)+fibonacci(n-2));

};

const function<List(List,List)> consAdd=cons<List>;

const int sumOddSquares(const List& tree)

{

    return(accumulate

           (add,0,(mapping

                   (square,filter

                    (isOdd, enumerateTree(tree))))));

}

const List evenFibonaccies(const int n)

{

    return(accumulate

           (consAdd,makeList(),

            filter(isEven,

                   mapping(fibonacci,enumerateInterval(0,n)))));

}

const List listFibonacciSquares(const int n)

{

    return(accumulate

           (consAdd,makeList(),

            mapping(square,

                    mapping(fibonacci,enumerateInterval(0,n)))));

}

const int productOfSquaresOfOddElements

(const List& sequence)

{

    return(accumulate

           (mul,1,mapping(square,filter(isOdd,sequence))));

}

// map (accumulate version)

template <typename ReturnType, typename ArgType>

const List mappingAcc

(const function<ReturnType(ArgType)>& procedure,

 const List& listTree)

{

    const auto nil(makeList());

    const function<List(List,List)>

        addProc=[procedure]

        (const List& x, const List& y)

        {return(cons(leafMap(procedure,x),y));};

    return(accumulate(addProc, nil,listTree));

}

//append (accumulate version)

const List appendAcc

(const List& sequence1,const List& sequence2)

{

    return(accumulate(consAdd,sequence2,sequence1));

}

//length (accumulate version)

const int lengthAcc(const List& sequence)

{

    function<int(List,int)> incrementAcc=

        [](const List& x,const int y){return(y+1);};

    return(accumulate(incrementAcc,0,sequence));

}

int main(int argc, char** argv)

{

    const auto list1(makeList(1,2,3,4,5));

    cout<<"(filter odd? (1 2 3 4 5)) = "

        <<listString(filter(isOdd,list1))<<endl;

   

    cout<<"(accumulate + 0 (1 2 3 4 5)) = "

        <<accumulate(add,0,list1)<<endl;;

    cout<<"(accumulate * 1 (1 2 3 4 5)) = "

        <<accumulate(mul,1,list1)<<endl;;

   

    cout<<"(accumulate cons nil (1 2 3 4 5)) = "

        <<listString(accumulate(consAdd,makeList(),

                                list1))<<endl;

    cout<<"(enumerate-interval 2 7) = "

        <<listString(enumerateInterval(2,7))<<endl;

   

    const auto list2(makeList(1,makeList(2,makeList(3,4),5)));

    const auto list3(enumerateTree(list2));

    cout<<"(enumerate-tree (1 (2 (3 4) 5))) = "

        <<listString(list3)<<endl;

   

    const auto list4(makeList(1,2,3,4,5));

    cout<<"(sum-odd-squares (1 (2 (3 4) 5))) = "

        <<sumOddSquares(list2)<<endl;

    const int nFibonacci(10);

    cout<<"(even-fibs "<<nFibonacci<<") = "

        <<listString(evenFibonaccies(nFibonacci))<<endl;

    cout<<"(list-fib-squares "<<nFibonacci<<") = "

        <<listString(listFibonacciSquares(nFibonacci))<<endl;

    cout<<"(product-of-squares-of-odd-elements (1 2 3 4 5)) = "

    <<productOfSquaresOfOddElements(list1)<<endl;

    cout<<endl<<"Excersize 2.33:"<<endl;

    cout<<"(map square (1 2 3 4 5)) = "

        <<listString(mappingAcc(square, list1))<<endl;

    cout<<"(append (enumerate-interval 1 5)) "

        <<"(enumerate-interval 6 10))"<<endl<<"= "

        <<listString(appendAcc

                     (enumerateInterval(1,5),

                      enumerateInterval(6,10)))

                      <<endl;

    cout<<"(length (1 2 3 4 5)) = "

        <<lengthAcc(list1)<<endl;

    cout<<"(length (enumerate-interval 2 7)) = "

        <<lengthAcc(enumerateInterval(2,7))<<endl;

   

    return(0);

}

----

出力

----

(filter odd? (1 2 3 4 5)) = (1 3 5)

(accumulate + 0 (1 2 3 4 5)) = 15

(accumulate * 1 (1 2 3 4 5)) = 120

(accumulate cons nil (1 2 3 4 5)) = (1 2 3 4 5)

(enumerate-interval 2 7) = (2 3 4 5 6 7)

(enumerate-tree (1 (2 (3 4) 5))) = (1 2 3 4 5)

(sum-odd-squares (1 (2 (3 4) 5))) = 35

(even-fibs 10) = (0 2 8 34)

(list-fib-squares 10) = (0 1 1 4 9 25 64 169 441 1156 3025)

(product-of-squares-of-odd-elements (1 2 3 4 5)) = 225

Excersize 2.33:

(map square (1 2 3 4 5)) = (1 4 9 16 25)

(append (enumerate-interval 1 5)) (enumerate-interval 6 10))

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

(length (1 2 3 4 5)) = 5

(length (enumerate-interval 2 7)) = 6