てなぐさみのメモ: 2012/07

2012-07-31

SCIP in C++11 ― 1.3.2節

1.3.2節　lambdaを使う手続きの構築

問題1.34

いろいろやってみたが、(f square) やf(lambda(z)(* z (+ z 1)))の

対応物は作れるが、(f f)はコンパイルが通らない。

まー文法的に正しく書いても、

コンパイルの段階で無限ループに入るだろうなあ。

SCIP in C++11 ― 1.3.1節その2

問題1.30はScheme特有の話なのでパス。

問題1.31

aの再帰版のみ示す。反復版はあまり興味ないのでbはパス。

--------

template<typename TermResult, typename TermArgument,

typename NextResult,typename NextArgument>

const TermResult product

(const function<TermResult(TermArgument)>& term,

const NextArgument& lower,

const function<NextResult(NextArgument)>& next,

const NextArgument& upper)

{

if(lower>upper){return(1);}

return(term(lower)*product(term,next(lower),next,upper));

}

const function<int(int)> identity=[](const int x){return(x);};

template<typename ResultType>

const ResultType incrementFun(const ResultType x){return(x+1);}

const int productFactorial(const int upper)

{

const function<int(int)> increment=incrementFun<int>;

return(product(identity,1,increment,upper));

}

const double piProduct(const int upper)

{

const function<double(double)>

piProductElement=[](const double x){

return(4.0*x*(x+1.0)/(2.0*x+1.0)/(2.0*x+1.0));

};

const function<double(double)> increment=incrementFun<double>;

return(product(piProductElement,1.0,increment,

static_cast<double>(upper))*4.0);

}

int main(int argc, char** argv)

{

int upper(5);

cout<<upper<<"!="<<productFactorial(upper)<<endl;

upper=1000;

cout<<"pi="<<piProduct(upper)<<endl;

return(0);

}

------

出力

------

5!=120

pi=3.14238

問題1.32

accumulateと、accumulateを用いたsum,productのみ示す。

------

template<typename TermResult, typename TermArgument,

typename NextResult,typename NextArgument>

const TermResult accumulate

(const function<TermResult(TermArgument,TermArgument)>& combiner,

const TermResult& nullValue,

const function<TermResult(TermArgument)>& term,

const NextArgument& lower,

const function<NextResult(NextArgument)>& next,

const NextArgument& upper)

{

if(lower>upper){return(nullValue);}

return(combiner(term(lower),

accumulate(combiner,nullValue,term,

next(lower),next,upper)));

}

template<typename TermResult, typename TermArgument,

typename NextResult,typename NextArgument>

const TermResult sum

(const function<TermResult(TermArgument)>& term,

const NextArgument& lower,

const function<NextResult(NextArgument)>& next,

const NextArgument& upper)

{

const TermResult zero(0);

const function<TermResult(TermArgument,TermArgument)>

add=std::plus<TermResult>();

return(accumulate(add,zero,term,lower,next,upper));

}

template<typename TermResult, typename TermArgument,

typename NextResult,typename NextArgument>

const TermResult product

(const function<TermResult(TermArgument)>& term,

const NextArgument& lower,

const function<NextResult(NextArgument)>& next,

const NextArgument& upper)

{

const TermResult one(1);

const function<TermResult(TermArgument,TermArgument)>

mul=std::multiplies<TermResult>();

return(accumulate(mul,one,term,lower,next,upper));

}

------

問題1.33

filter付きaccumulateのみ示す。

a,bは特に実装してないけど・・・。

------

template<typename TermResult, typename TermArgument,

typename NextResult,typename NextArgument>

const TermResult filteredAccumulate

(const function<TermResult(TermArgument,TermArgument)>& combiner,

const TermResult& nullValue,

const function<bool(TermArgument)>& predicate,

const function<TermResult(TermArgument)>& term,

const NextArgument& lower,

const function<NextResult(NextArgument)>& next,

const NextArgument& upper)

{

if(lower>upper){return(nullValue);}

if(predicate(lower)){

return(combiner(term(lower),

filteredAccumulate(combiner,nullValue,predicate,

term,next(lower),next,upper)));

}

return(filteredAccumulate(combiner,nullValue,predicate,

term,next(lower),next,upper));

}

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

1.3.1節　引数としての手続き

最初は懸命にファンクタ使って、抽象ファンクタテンプレートを作り、スライシングに悩み、std::functionテンプレートクラスの使い方に悩み、後でラムダ出るしなあとテストしてもうまく行かなくてとか散々悩んで何度もコードを書き直し。

ラムダだけで押したらどうなるのかなと試してみたらなんと、すっげえよラムダ、ヤバイよラムダ、ラムダかわいいよラムダ。コードが一気にコンパクト化。これでやっと少し光が見えてきたか。

総和手続きと問題1.29

--------

template<typename TermResult, typename TermArgument,

typename NextResult,typename NextArgument>

const TermResult sum

(const function<TermResult(TermArgument)>& term,

const NextArgument& lower,

const function<NextResult(NextArgument)>& next,

const NextArgument& upper)

{

if(lower>upper){return(0.0);}

return(term(lower)+sum(term,next(lower),next,upper));

}

const function<int(int)> identity=

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

const function<int(int)> increment=

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

template<typename ResultType>

const ResultType squareFun(const ResultType x){return(x*x);}

template<typename ResultType>

const ResultType cubeFun(const ResultType x){return(pow(x,3));}

function<double(double)> piTerm=

[](const double x){return(1.0/x/(x+2.0));};

function<double(double)> piNext=

[](const double x){return(x+4);};

const int sumIntegers(const int lower, const int upper)

{

return(sum(identity, lower,increment, upper));

}

const int sumSquareIntegers(const int lower, const int upper)

{

const function<int(int)> square=squareFun<int>;

return(sum(square, lower, increment, upper));

}

const double piSum(const int lower,const int upper)

{

return(sum(piTerm,static_cast<double>(lower),

piNext,static_cast<double>(upper))*8.0);

}

const double integral

(const function<double(double)>& f,

const double lower, const double upper, const double dx)

{

const function<double(double)> addDx

=[dx](const double x){return(x+dx);};

return(sum(f, lower+dx/2.0, addDx, upper)*dx);

}

const double simpsonIntegral

(const function<double(double)>& f,

const double lower, const double upper, const double dx)

{

const function<double(double)> add2Dx

=[dx](const double x){return(x+2.0*dx);};

const function<double(double)> simpsonF=[dx,&f](const double x){

return(f(x-dx)+4.0*f(x)+f(x+dx));

};

return(sum(simpsonF, lower+dx, add2Dx, upper)*dx/3.0);

}

int main(int argc, char** argv)

{

int lower(1);

int upper(1000);

cout<<"sum_{i="<<lower<<"}^{"<<upper

<<"} i="<<sumIntegers(lower,upper)<<endl;

upper=10;

cout<<"sum_{i="<<lower<<"}^{"<<upper

<<"} i^2="<<sumSquareIntegers(lower,upper)<<endl;

upper=1000;

cout<<"sum_{i="<<lower<<"}^{"<<upper

<<"} 1/((4i+1)(4i+3))="<<piSum(lower,upper)<<endl;

lower=0;

upper=1;

const double dx(0.001);

const function<double(double)> cube=cubeFun<double>;

cout<<setprecision(16)<<"integral_{"<<lower

<<"}^{"<<upper<<"} cube(x) dx="

<<integral(cube,static_cast<double>(lower),

static_cast<double>(upper),dx)<<endl;

cout<<endl<<"Problem 1.29:"<<endl;

cout<<setprecision(16)<<"integral_{"<<lower

<<"}^{"<<upper<<"} cube(x) dx="

<<simpsonIntegral(cube,static_cast<double>(lower),

static_cast<double>(upper),dx)<<endl;

return(0);

}

----

出力

----

sum_{i=1}^{1000} i=500500

sum_{i=1}^{10} i^2=385

sum_{i=1}^{1000} 1/((4i+1)(4i+3))=3.13959

integral_{0}^{1} cube(x) dx=0.2499998750000006

integral_{0}^{1} cube(x) dx=0.2500000000000006

2012-07-17

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

1.2.2節　両替の計算

慣れないSchemeと違ってスゲー楽～ｗ

まあ本チャンは1.3節からだが

問題1.9、1.10はプロセスの読み方なのでパス

これでできちゃうんだ・・・魔法使いになったみたいｗ

----

int main(int argc, char** argv)

{

cout<<"# of exchanges for 1$="<<countChange(100)<<endl;

return(0);

}

const int countChange(const int amount)

{

return(cc(amount,5));

}

const int cc(const int amount, const int kindsOfCoins)

{

if(0==amount){

return(1);

}else if(0>amount||0==kindsOfCoins){

return(0);

}else{

return(cc(amount,kindsOfCoins-1)

+cc(amount-firstDenomination(kindsOfCoins),kindsOfCoins));

}

const int firstDenomination(const int kindsOfCoins)

{

if(1==kindsOfCoins){return(1);}

else if (2==kindsOfCoins){return(5);}

else if (3==kindsOfCoins){return(10);}

else if (4==kindsOfCoins){return(25);}

else if (5==kindsOfCoins){return(50);}

return(0);

}

----

出力

----

# of exchanges for 1$=292

2012-07-11

SCIP in C++11 ― 1.1節

1.1節　プログラムの要素

問題1.1～1.6はSchemeの練習なのでパス。

問題1.7～1.8：平方根計算の改善と立方根

----

//ヘッダincludeと関数プロトタイプ宣言は略

int main(int argc, char** argv)

{

cout<<"Excersize 1.7:"<<endl;

const double r1(calculateSquareRoot(2.0));

cout<<setprecision(16)<<"sqrt(2)="<<r1<<endl

<<"sqrt(2)^2="<<r1*r1<<endl;

const double r2(calculateSquareRoot(10000));

cout<<endl<<setprecision(16)<<"sqrt(10000)="<<r2<<endl

<<"sqrt(10000)^2="<<r2*r2<<endl;

const double r3(calculateSquareRoot(0.0001));

cout<<endl<<setprecision(16)<<"sqrt(0.0001)="<<r3<<endl

<<"sqrt(0.0001)^2="<<r3*r3<<endl;

cout<<endl<<"Excersize 1.8:"<<endl;

const double c1(calculateCubicRoot(2.0));

cout<<setprecision(16)<<"cbrt(2)="<<c1<<endl

<<"cbrt(2)^3="<<c1*c1*c1<<endl;

return(0);

}

const double calculateSquareRoot(const double x)

{

return(squareRootIteration2(1.0,x,x));

}

const bool isGoodEnoughSquareRoot(const double guess, const double x)

{

if (abs(x-guess*guess)<0.001){

return(true);

}

return(false);

}

const double average(const double x, const double y)

{

return((x+y)/2.0);

}

const double improveGuessSquareRoot(const double guess,const double x)

{

return(average(guess, x/guess));

}

const double squareRootIteration(const double guess, const double x)

{

if(isGoodEnoughSquareRoot(guess,x)){

return(guess);

}else{

return(squareRootIteration(improveGuessSquareRoot(guess,x),x));

}

const bool isGoodEnoughSquareRoot2(const double guess, const double oldGuess)

{

if (abs((guess-oldGuess)/guess)<0.001){

return(true);

}

return(false);

}

const double squareRootIteration2(const double guess, const double oldGuess, const double x)

{

if(isGoodEnoughSquareRoot2(guess,oldGuess)){

return(guess);

}else{

return(squareRootIteration2(improveGuessSquareRoot(guess,x),guess,x));

}

const double calculateCubicRoot(const double x)

{

return(cubicRootIteration(1.0,x));

}

const bool isGoodEnoughCubicRoot(const double guess, const double x)

{

if (abs(x-guess*guess*guess)<0.001){

return(true);

}

return(false);

}

const double improveGuessCubicRoot(const double guess,const double x)

{

return(average(guess, (x/guess/guess+2*guess)/3.0));

}

const double cubicRootIteration(const double guess, const double x)

{

if(isGoodEnoughCubicRoot(guess,x)){

return(guess);

}else{

return(cubicRootIteration(improveGuessCubicRoot(guess,x),x));

}

--------------

出力

--------------

Excersize 1.7:

sqrt(2)=1.41421356237469

sqrt(2)^2=2.000000000004511

sqrt(10000)=100.0000002549074

sqrt(10000)^2=10000.00005098149

sqrt(0.0001)=0.01000000002549074

sqrt(0.0001)^2=0.0001000000005098149

Excersize 1.8:

cbrt(2)=1.259765013452635

cbrt(2)^3=1.999257014785836

コックス「ガロワ理論」が最終15.5節で詰まっている。
というか、15.5節の演習問題3で、8.5節演習問題5の結果を使うようなのだが、
その8.5節演習問題5がどうもかっちりはまらなくて解けてない。
ボチボチやって早く代数幾何学やりたいなあ。
まあ15.4節まででもコックスの本はものすご～く楽しくて、
勉強になったのだけれど。
まさに「翼が生えたような」感覚を味わえた。
そういえば数学ガール「ガロア理論」よかった～。

とか言っている間に、仕事のほうでC++プログラムの
パフォーマンス追求のために、テンプレートが必要になった。

結城浩
数学ガール
ガロア理論

まあそれはなんとかやったのだが、
コード組みながらなんとなく感じていたのは、

「STLのアルゴリズムで、ちょっと複雑なことしようとすると、
ファンクタ使って実装しないといけなくて、何か大げさ・・・」

「テンプレートちょっと踏み込むと複雑でよくわかんない・・・
てかアレキサンドレスク変態すぎｗｗ」

「C++11で新しく加わった機能には、何がしたいのか、
全然わからないのもあるなあ・・・」

アレキサンドレスク
Modern C++ Design

という、多分見る人が見たら
「そんな低レベルでよくプログラム組んでんなヘタクソ」と言われそうなことで、

要するに自分の無知とスキル不足を感じていた。

変態アレキサンドレスクの中で、コンパイル時のテンプレートについて、
「コンパイル時に行われるすべての計算処理は、
値の変更を行うことが出来ない関数型言語を思い出させるような
テクニックに頼らなければならない」（3.5節）とあって、

関数型言語？なにそれおいしいの？と今更思って調べてみると、

「あーなんか最近雑誌でHaskellとか名前は見るなあ」とは思ったが、

雑誌記事とかウィキペとか読んでも何に使えるのか見えない。

関数型言語がなんかまあ流行りではあるみたいなので、

エイブルソン,
サスマン & サスマン
計算機プログラムの
構造と解釈 (SICP)

ちょっと覗いてみるかと、この分野じゃバイブル扱いらしい、

「計算機プログラムの構造と解釈」いわゆる「SCIP」を、

適当に興味を引いた演習問題を、初体験のSchemeを勉強しながら
実装していっていたら、この本すげえ。

「なんとなく意識していたが自分の中で明確になっていなかった発想」

「出来るのは知っていたが使ったことはない発想」

「眼から鱗の、考えたこともない発想」

が入れ替わり立ち代り、これでもかと高密度・大迫力で迫ってくる。

まだその迫力に気圧されて、頭の中でまとめられてないけどｗ

サッター
Exceptional C++

Schemeに慣れなくて、いや新発想に慣れなくて、

つまづきつまづき今は第3章を読み進めている。

が、ふつふつと湧き上がるのは、

「この演習問題を関数型言語的発想で、C++で実装するにはどうするか？」

という気持ち。

今まで普通に使っていたC++98ではすごく面倒そうだが、

C++11の新機能がなんか使えそう。

よくわからなかったC++11の新機能って、
関数型言語的なことがやりたかったのか。
いやまあboost使いにはずっと以前から知られてたことみたいだけど、
boost使ったことないのでよく知らんかった。
この度めでたくC++標準にいろいろ入ってきたので使ってみたいなあ。

メイヤーズ
Effective C++

SICPは計算機科学ではすごく有名みたいで、演習問題の解説で

Schemeのプログラムが置いてあるサイトには事欠かないが、

C++11で実装するサイトはあまり無いようだ。

というわけで、C++11の練習も兼ねて、SICPの演習問題に対する、

C++11での例をちょこちょこ書いていけたらなと思う。
gccも4.7になって、C++11の主要な部分は
（実験的ながら）一応使えるみたいだし。

まあサッター先生やメイヤーズ先生に「めっ！」と言われそうな、

下手なプログラムも多くなるだろうが・・・。
あと代数学の勉強からの浮気なので、いつまで続くかわからないｗ

自分のコードをくぱぁと晒すのはとっても恥ずかしいんだもん。

どうも仕事で圏論が要りそうな見通しになってきたなあ・・・もっともっと勉強しないとなあ・・・。

登録: 投稿 ( Atom )

てなぐさみのメモ

目次

2012-07-31

SCIP in C++11 ― 1.3.2節

SCIP in C++11 ― 1.3.1節その2

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

2012-07-17

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

2012-07-11

SICP 問題の解答例 in C++11

SCIP in C++11 ― 1.1節

次は・・・SICP?