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

ベクトルと行列：問題2.36～2.37

algorithmにはinner_productやadjacent_differenceといった、

多少の線形代数チックな計算ができるものがあるが、

これはもっと一般的な話だな。使えるかもしれない。

mapを使った再帰の隠蔽が、mapをリストに対するfor_eachのように使って、

本格的に行われ始めたようだ。map強いなあ。

関数型言語って、計算理論からの数学的帰結を利用して矛盾なく計算を実行する言語、

というイメージが自分的に芽生えつつある

（ホントはそういうのは論理型言語なのかな）が、

mapで写像を意識してるときは特に、数学してる感じがする。

問題2.37では、2つのリストから1つのリストを得るmapが必要。

この実装はそんなに難しくないが、さらに一般化して、

任意個のリストから1つのリストを作るような

mapを作ろうとしてみたがこれは挫折。

写像の関数を、C++11のbindを使って再帰的に計算出来るかと思ったら、

任意個のplaceholderをどうすれば設定できるのかがわからない。

----

//map for 2 input lists

template <typename ArgType1, typename ArgType2, typename ReturnType>

const List mapping

(const function<ReturnType(ArgType1,ArgType2)>& procedure,

 const List& listTree1,const List& listTree2)

{  

    if(isNull(listTree1) || isNull(listTree2)){return(makeList());}

    return(cons(procedure(value<ArgType1>(car(listTree1)),

                          value<ArgType2>(car(listTree2))),

                mapping(procedure,cdr(listTree1),cdr(listTree2))));

}

// accumulate-n

template <typename Accumulate, typename LeafType>

const List accumulateN

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

 const Accumulate& initialValue,

 const List& sequences)

{

    if(isNull(car(sequences))){return(makeList());}

    const function<List(List)> carMap=car;

    const function<List(List)> cdrMap=cdr;

    return(cons

           (accumulate

            (operation,initialValue,

             mapping(carMap,sequences)),

            accumulateN

            (operation,initialValue,

             mapping(cdrMap,sequences))));

}

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

typedef int Field;

typedef List Vector;

typedef List Matrix;

const Vector nullVector(makeList());

const function<bool(Field)> isOdd=

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

const function<bool(Field)> isEven=

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

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

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

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

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

const function<Field(Field)> square=

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

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

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

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

};

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

const Field dotProduct(const Vector& v,

                       const Vector& w)

{

    return(accumulate(add,0,mapping(mul,v,w)));

}

const List matrixVectorProduct

(const Matrix& m, const Vector& v)

{

    const function<Field(Vector)> rowProduct

        =[v](const Vector& mRow)

        {

            return(dotProduct(v,mRow));

        };

    return(mapping(rowProduct,m));

}

const Matrix transposeMatrix(const Matrix& mat)

{

    function<Vector(Field,Vector)>

        consVec=cons<Field>;

    return(accumulateN(consVec,nullVector,mat));

}

const Matrix matrixProduct(const Matrix& m, const Matrix& n)

{

    function<Vector(Vector)>

        mRowProduct=[n](const Vector& mRow)

        {

            return(matrixVectorProduct(transposeMatrix(n),mRow));

        };

    return(mapping(mRowProduct,m));

}

int main(int argc, char** argv)

{

    const auto vector0(makeList(1,2,3));

    const auto vector1(makeList(4,5,6));

    const auto vector2(makeList(7,8,9));

    const auto vector3(makeList(10,11,12));

    const auto vectors(makeList

                       (vector0,vector1,vector2,vector3));

    cout<<"Excersize 2.36:"<<endl;

    cout<<"s = "<<listString(vectors)<<endl;

    const auto sumVector(accumulateN(add,0,vectors));

    cout<<"(accumulate-n + 0 s) = "<<listString(sumVector)<<endl;

    cout<<endl<<"Excersize 2.37:"<<endl;

    const auto matrix1stRow(makeList(1,2,3,4));

    const auto matrix2ndRow(makeList(4,5,6,6));

    const auto matrix3rdRow(makeList(6,7,8,9));

    const auto matrix(makeList

                      (matrix1stRow,matrix2ndRow,matrix3rdRow));

    const auto vector4_1(makeList(10,10,10,10));

    const auto vector4_2(makeList(1,-1,1,-2));

    cout<<"v = "<<listString(vector4_1)<<endl;

    cout<<"w = "<<listString(vector4_2)<<endl;

    cout<<"(dot-product v w) = "

        <<dotProduct(vector4_1,vector4_2)<<endl;

    cout<<endl;

    cout<<"m = "<<listString(matrix)<<endl;

    cout<<"(matrix-*-vector m v) = "

        <<listString(matrixVectorProduct(matrix,vector4_1))<<endl;

    cout<<"(transpose-mat m) = "

        <<listString(transposeMatrix(matrix))<<endl;

    cout<<endl;

    const auto m_1stRow(makeList(1,2));

    const auto m_2ndRow(makeList(3,4));

    const auto n_1stRow(makeList(1,-1));

    const auto n_2ndRow(makeList(1,-1));

    const auto m(makeList(m_1stRow,m_2ndRow));

    const auto n(makeList(n_1stRow,n_2ndRow));

    cout<<"m = "<<listString(m)<<endl;

    cout<<"n = "<<listString(n)<<endl;

    cout<<"(matrix-*-matrix m n) = "

        <<listString(matrixProduct(m,n))<<endl;

   

    return(0);

}

----

出力

----

Excersize 2.36:

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

(accumulate-n + 0 s) = (22 26 30)

Excersize 2.37:

v = (10 10 10 10)

w = (1 -1 1 -2)

(dot-product v w) = -10

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

(matrix-*-vector m v) = (100 210 300)

(transpose-mat m) = ((1 4 6) (2 5 7) (3 6 8) (4 6 9))

m = ((1 2) (3 4))

n = ((1 -1) (1 -1))

(matrix-*-matrix m n) = ((3 -3) (7 -7))