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

ループの表現：問題2.40～2.41

問題2.38～2.39は一応fold-leftの実装はしたが、

有理数の型が面倒なのと、あまり興味ないのでパス。

enumerate-intervalで数のリストを作って、

mapとaccumulateを使うなんていうループの表現法にびっくり。

Haskellの本にも書いてあるし、関数型でループを表現する定番テクニックみたいだな。

テンプレート関数を手続きとして他の手続きに渡すときに、

いちいちfunctionラッパで包まなきゃいけないのが面倒だなあ。

しかもそうしなきゃいかんのをすぐ忘れちゃって、

テンプレートマッチングのエラーの嵐になる。

型が決まってる関数なら、ラムダで定義してはじめから包んじゃえるんだけど。

まーそうやって苦労して、何連鎖もの関数が通ると気持ちいいんだけどさ。

型構造を強く意識しなきゃいけない関係で、

コードの内容をしっかり理解しないとだから、

コードの理解はSchemeで組んでた時よりもずっと進むんだと思うことにしておこう。

これまでのところで、mapとかいろいろな基本的手続きを、

一般的な場合を意識してしっかり組んだせいか、

さすがに一発でコンパイルが通るのはなかなか無いけど、

段々テンプレートマッチングのミスが少なくはなり、

デバッグがすぐ終わるようになってきた。

序盤にテンプレートで散々苦労したことが、少しは報われてきたかな。

----

// flatmap

//e.g. LeafType=int, Accumulate=list<list<int>>

template <typename ReturnType,typename ArgType>

const List flatMap

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

 const List& sequence)

{

    const function<List(List,List)>

        addProcedure=append;

    return(accumulate(addProcedure,makeList(),

                      mapping(procedure,sequence)));

}

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

const function<int(int)> square=

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

// prime test: primitive method

const int findDivisor(const int n, const int testDivisor)

{

    if(square(testDivisor)>n){return(n);}

    else if(0==n%testDivisor){return(testDivisor);}

    return(findDivisor(n,testDivisor+1));

}

const int smallestDivisor(const int n)

{return(findDivisor(n,2));}

const bool isPrime(const int n)

{return(smallestDivisor(n)==n);}

//unique pair

const List uniquePair(const int n){

    const function<List(int)> makePermutationPair

        =[](const int i)

        {

            const function<List(int)> makeIntPair

            =[i](const int j){return(makeList(i,j));};

            return(mapping(makeIntPair,enumerateInterval(1,i-1)));

        };

    return(flatMap(makePermutationPair,enumerateInterval(1,n)));

}

//unique trio for excersize 2.41

const List uniqueTrio(const int n){

    const function<List(int)> makePermutationTrio

        =[](const int i)

        {

            const function<List(List)> consI

            =[i](const List& intPair){return(cons(i,intPair));};

           

            return(mapping(consI,uniquePair(i-1)));

        };

    return(flatMap(makePermutationTrio,enumerateInterval(1,n)));

}

// prime pair

const bool isPrimeSum(const List& intPair)

{return(isPrime(value<int>(car(intPair))+value<int>(cadr(intPair))));}

const List makePairSum(const List& pair)

{

    return(makeList

           (value<int>(car(pair)),value<int>(cadr(pair)),

            value<int>(car(pair))+value<int>(cadr(pair))));

}

const List primeSumPairs(const int n)

{

    const function<bool(List)> filterPredicate=isPrimeSum;

    const function<List(List)> mapPair=makePairSum;

    const function<List(int)> generatePair=uniquePair;

    return(mapping

           (mapPair, filter

            (filterPredicate,uniquePair(n))));

}

// permutation

template <typename LeafType>

const List removeSet

(const LeafType& item,const List& setSequence)

{

    const function<bool(LeafType)> notEqualElement=

        [item](const LeafType x){return(!(x==item));};

    return(filter(notEqualElement,setSequence));

}

template <typename LeafType>

const List permutations(const List& inSet)

{

    if(isNull(inSet))return(makeList(inSet));

    const function<List(LeafType)>

        generatePermutation=[inSet](const LeafType& x)

        {

            const function<List(List)>

            leftCons=[x](const List& p)

            {return(cons(x,p));};

            return(mapping(leftCons,

                           permutations<LeafType>(removeSet(x,inSet))));

        };

    return(flatMap(generatePermutation,inSet));

}

   

const List sumTrios(const int n,const int sum)

{

    const function<bool(List)> isSumEqual

        =[sum](const List trio)

        {return(value<int>(car(trio))+value<int>(cadr(trio))

                +value<int>(caddr(trio))==sum);};

    const function<List(int)> uTrio=uniqueTrio;

   

    return(filter(isSumEqual,uTrio(n)));

}

int main(int argc, char** argv)

{

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

    cout<<"(permutations (1 2 3)) ="<<endl

        <<listString(permutations<int>(inSet))<<endl;

    int n(6);

    cout<<endl<<"Excersize 2.40:"<<endl

        <<"(unique-pair "<<n<<") = " <<endl

        <<listString(uniquePair(n))<<endl

        <<"(prime-sum-pairs "<<n<<") = "<<endl

        <<listString(primeSumPairs(n))<<endl;

    const int sum(10);

    cout<<endl<<"Excersize 2.41:"<<endl

        <<"(unique-trio "<<n<<") = " <<endl

        <<listString(uniqueTrio(n))<<endl;

    cout<<"(sum-trios "<<n<<" "<<sum<<") = "<<endl

        <<listString(sumTrios(n,sum))<<endl;

    return(0);

}

----

出力

----

(permutations (1 2 3)) =

((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))

Excersize 2.40:

(unique-pair 6) =

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

(prime-sum-pairs 6) =

((2 1 3) (3 2 5) (4 1 5) (4 3 7) (5 2 7) (6 1 7) (6 5 11))

Excersize 2.41:

(unique-trio 6) =

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

(sum-trios 6 10) =

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