JPEG エンコーダ書いた

以前、JPEGに関する画像圧縮技術やデータ構造などついて学んだので、折角だし自分で作ってみようと思い、フルスクラッチで書いて見た。といっても、性能自体はそんなに良いものではないと思うし、簡単のために色々と制限を設けているので実用的ではないと思うが。言語はC++1z。Structured bindings とか Class templates deduction とか普通に使っているので、C++1z に対応しないコンパイラではコンパイルできない。

github.com

仕様と諸々の説明は以下の通り。

出力された lena 氏の画像*1。左はカラーモード、右はグレースケールモードで出力した。グレースケール画像は、簡単のために、Cb値とCr値を 0 としてそのまま持たせている。

JPEG エンコーダをフルスクラッチで実装した事で、JPEG バイナリが読めるようになった。そしてデータ圧縮のロマンをより一層感じた。今後も時間があれば、機能拡張したりエフェクト付け加えたり、はたまたデコーダとかを書ければなと思う。

※追記

その後、JPEG デコーダもフルスクラッチで実装した。

*1:ブログに載せる上で画像の表示を小さくしている。

量子力学と量子コンピューターについての学習メモ #3

前回の続き。

データベース検索

データベースの例として電話帳を取り上げる。電話帳は、名前の五十音順に番号が付けられている。これは昇順ソートされたリストであると解釈できるので、バイナリーサーチの手法によって比較的高速かつ簡単にアクセスできる。次に、この電話帳に対して電話番号を入力して、誰のものなのかを問い合わせたいとしたい場合を考えると、この場合線形探索が必要となってしまい、とても効率が悪い。しかし量子コンピュータでは、この種のデータ探索をデータ数が とした場合 回で確実に完了するのである。これは、グローバーのアルゴリズムといわれている。 まず、以下のようなデータベース回路を用意する。

全ての量子ビットをアドレスビットとし、入力の値がデータベースと合致した場合、アドレスビット列の位相が反転する。この場合、 がデータベースに登録されている事となる。もしその入力が得られた場合、位相が反転する。これをDBゲートとする。 このゲートの通過結果に折り返し量子回路をかける。この折り返し量子回路は、各量子ビットに対するアダマールゲートとアドレスビット列が全て の状態のときのみその位相を反転するゲートによって容易に実現できるようだ(実装を調査したが、詳しい実装を見つける事ができなかった。もし詳細に関わるドキュメントなどをこのエントリを読んでいる方の中でご存知の方がいたら、是非ご教授願いたい)。
[ ※追記 独自に実装した。

中身が |11> なデータベースに対するグローバーのアルゴリズム,多分できた. pic.twitter.com/4j6U6shcIc

— roκi (@530506) 2017年6月19日

これは、データベースの中身が である場合の回路である。数式で流れを追うと明快である*1。

1. まず初期状態として2量子ビットとも にしておく。
2. アダマールゲートによって、2量子ビットとも重ね合わせ状態 となる。それぞれの確率振幅は なので、2量子ビットにおける全てのパターンそれぞれの確率振幅は である。
3. 次にターゲットである の位相のみ反転するために制御Zゲートを通過させると、次の数式の通りとなる。 となる。
4. 拡散変換D(折り返し回路)を通過する。アダマール変換、ビット変換、制御Zゲートにより構成される。これらを通過すると、次の式の通りとなる。

━━ 追記ここまで ]
この操作を何度か繰り返すことで、特定のビット列の発生する確率が高くなり、判定結果に対する信頼性が高まる。尚、これを繰り返すたびに、判定結果の量子ビット列の確率振り幅は 、 …と大きくなる。判定時に、そのビット列を入力してみて、正しく反転するか確認し、間違っていた場合はこれを繰り返す事で、ほぼ確実に内包するデータを取り出せる。

*1:Reference: https://quantumexperience.ng.bluemix.net/qx/tutorial?sectionId=8443c4f713521c10b1a56a533958286b&pageIndex=2

stack overflow からの小ネタメモ

stack overflow で得たちょっとした小ネタをメモがてら羅列してみる。

stackoverflow.com

質問は、ざっくり書くと、ラムダを関数ポインタに変換する明示的な記述なしでそのような事ができる方法はあるか？であるが、これに対して operator+ を適用すると、変換されると回答されている。これは何が起きているかと言うと回答にもある通り、built-in の unary operator + がラムダの持つ関数ポインタへの変換関数を呼び出すトリガーとなり、その結果関数へ渡せているのである。built-in の unary operator + については、[over.built]の通りである。以下はこの擬似コードである。

template<class T>
T call(T(*func)()){func();}

void(*built_in_plus(void(*f)()))() {return f;}

int main()
{
    call( built_in_plus([]{}) );
}

built-in unary operator+ のこういう使い方は思いつかなかった。ただ個人的には、関数ポインタに変換している旨をキャストによって明示した方が良いとは思う。

stackoverflow.com

initializer_list を使って range-based forを使う事で、より簡潔に記述できるが、意図した通りに動かないのでどうすれば良いかという質問であるが、これは勿論、 initializer_list に渡しているのがその対象のコピーであるため、まず意図したようには動かない。ここでは二つの回答があり、それぞれアドレスを渡すものと、reference_wrapper を渡すものである。 個人的にはreference_wrapperを渡す方が好みだが、std::refを全てに書くのも微妙なので、Boost.Fusion が使えれば使いたい…

template<class... Ts>
constexpr boost::fusion::vector<Ts&...> refs(Ts&... ts)
{
    return boost::fusion::vector<Ts&...>{ts...};
}

boost::fusion::for_each(refs(foo,bar,baz),[](std::list<int>& x){x.push_back(42);});

stackoverflow.com 2つの質問が挙げられている。1つは、[class.member.lookup] に反したclang++とclが間違っているという内容。これはまぁ良い(良くはないのだが)。2つ目は、質問文中にあるように2つのクロージャ型を継承し、クロージャの持つ関数を Using-declaration を行ったものと、一切行わなかったもので、それぞれ全てのコンパイラが通す、GCCだけ通さないという結果になった。さらに面白い事に、Using-declaration を片方だけにしたら、今度はclang++とGCCだけが通した。これは一体何が正しいのだろうかという内容。結論から言えば、GCCの挙動が正しい。質問文中の最後に焦点を当てる。以下のような場合を考える。

#include <cstdio>

auto print_int = [](int x) {
    std::printf("int %d\n", x);
};
typedef decltype(print_int) foo_int;

auto print_str = [](const char* x) {
    std::printf("str %s\n", x);
};
typedef decltype(print_str) foo_str;

struct foo : foo_int, foo_str {
    using foo_int::operator();
    //using foo_str::operator();
    foo(): foo_int(print_int), foo_str(print_str) {}
};

int main() {
    foo f;
    f(123);
    f("foo");
}

まずf(123)によって Using-declaration で導出された operator()(int) による呼び出しが行われる。これは普通の動作だ。次に、f("foo")によって、これまた operator() から呼び出そうと試みるが、その引数型はconst char*なので、どれも該当しない。しかし、これは、[over.call.object] に該当する。foo はクロージャ型が持つ、関数ポインタへの implicit conversion function を継承しており、かつその implicit conversion function の operator() は 当然ながらその関数ポインタと互換性のあるシグネチャとなるので、fooを関数へのポインタに変換し、これを呼び出す事ができるのだ。そして勿論の事、非 captureless nongeneric lambda は、function pointer への implicit conversion function を持たないため、コンパイルエラーとなるのである。

うむ期待通り. https://t.co/9AvrJZhFNw

— roκi (@530506) 2017年6月13日

これは、[over.call.object] のExampleが意味を明快に示している(簡単のため筆者によって若干改変されている)。

int f1(int){return 42;}
float f2(float){return 4.2f;}

typedef int (*fp1)(int);
typedef float (*fp2)(float);

struct A {
  operator fp1() { return f1; }
  operator fp2() { return f2; }
} a;

#include<iostream>

int main()
{
    int i = a(1); // calls f1 via pointer returned from conversion function
    std::cout << i << std::endl; // 42
    
    float f = a(4.2f); // calls f2 via pointer returned from conversion function
    std::cout << f << std::endl; // 4.2f
}

もうちょっと何個か良いネタがあれば羅列したいところだったが、現時点では特別見つからないので、良いネタを見つけ次第追記するかもしれない。

量子力学と量子コンピューターについての学習メモ #2

前回の続き。

ドイチュ-ジョサのブラックボックス

ジョサのアルゴリズムとは、ブラックボックスが蓄えているビット列が均一か等分かどちらなのかを判定するアルゴリズムである。よって、このアルゴリズムが有効であるのは、ブラックボックスが蓄えているビット列は、均一か等分かのどちらかに限定されている場合である(そうでない場合、その結果としてある程度の切り捨てが発生する)。

まず従来の方法では、一つ一つ順次検査していく。例えば としてブラックボックスが 個のビット列を持っていた場合、これを与えると最大で 回の検査が必要となるが、ドイチュ-ジョサの考案した量子コンピュータによるアルゴリズムでは、この操作を 回で行える。自然数 を具体的な大きな数値にするとこの計算量の少なさは明らかだ。例えば 、つまり のビット列の場合、古典的な方法では560兆あまりのステップが必要となるが、当アルゴリズムでは103ステップで完了するのである。当然ながら、量子アルゴリズムでは重ね合わせを利用するために、ブラックボックスの入出力は量子ビットで行われる。入力用に3つの量子ビット、結果の出力用に1つの量子ビット、合計4つの量子ビットを使う。先頭ビットに対する答えが知りたければ 、2つ目であれば 、3つ目であれば をセットする。例えば をセットしたとした場合、3つ目のビットが0の場合は、出力用ビットの値がそのまま出力される(出力用量子ビットは予め決められた初期値が設定されなければならない)が、1の場合には出力量量子ビットが反転されて出力される。
例えば、ブラックボックスの中身が という均一であった場合、そのブラックボックスは量子回路によって以下のように実装できる。

どんな入力を受け付けても、全て出力を反転してしまえば良い。これを、BBAとする。

例えば、ブラックボックスの中身が という等分であった場合、そのブラックボックスは量子回路によって以下のように実装できる。

入力が 以降となった場合に反転させなければ良い。これをBBBとする。ドイチュ-ジョサの量子アルゴリズムはこのような量子ブラックボックスに対して、等分が均一かを確実に超高速で判別することができるアルゴリズムである。まず、そのアルゴリズムを実装した量子回路を以下に示す。

上から4つの量子ビットそれぞれを とする。 をアドレスビット、 をレジスタビットという。回路の動きを追っていく。

1. まず量子ビットは全て にセットされ、アダマールゲートによって となる。中身を具体的に書くと、 という具合だ。
2. 次のステップで、量子ブラックボックス回路に入る。この時、量子ブラックボックスBBAを通過した段階では、 であり、量子ブラックボックスBBBを通過した段階では、 である。この段階で特徴として挙げられるのが、それぞれの項のレジスタビット が、ブラックボックスに蓄えられていたビット列と完全に一致することである。これはつまり、一度の操作でブラックボックスの中身を読み出せたことを意味する。
3. ここからさらに、レジスタビット に、制御位相シフトを行う。制御位相シフトは、対象とする量子ビットが である場合のみ、その位相をプラスからマイナスへと変化させるので、当操作によってそれぞれ 、 となる。
4. さらに、量子ブラックボックスを通過し、それぞれ、 、 となる。簡単のため、アドレスビットとレジスタビットを分けて、、 とする。
5. 最後にアダマールゲートを作用させる。 に作用させると に、 に作用させると となるため、例えば の状態に焦点を当てると、まず となり、真ん中のビットに作用させると となり、同じく右側のビットに作用させ、 となる。この具合に、全ての項をアダマール変換すると、BBA側の変換結果は、1回目のアダマール変換によって全ての量子ビットに位相シフトが起きた事から、 である事が言えるため、これらに対し再度アダマール変換を施すと、それぞれの量子ビットは となり、BBB側の変換結果は となる。

結果、ブラックボックスBBAは全て状態 である事から、観測すると必ず状態 が得られるため均一である事が言え、ブラックボックスBBBはそうではなく、どれを観測しても全て状態 が得られるわけではない事から、等分であることを当アルゴリズムによって立証することができる。等分の場合に部分的に位相が反転するようにする事で、プラスマイナスによる打ち消しを妨害し、 への収束を避ける事が当アルゴリズムのポイントである。

次回はデーターベース検索のアルゴリズムに続く。

量子力学と量子コンピューターについての学習メモ #1

量子力学、量子コンピュータについての個人的な学習メモ。学習を促すものでも入門記事でもなくあくまで個人的な学習過程でのメモである事に注意。

量子コンピュータ―超並列計算のからくり (ブルーバックス)

量子コンピュータのメカニズムについて理解を深めるためには、量子力学について理解しなければならない。量子力学について理解するには、量子の代表例であり実験例としても最も多彩に業績の残る”光”についてまずは理解せねばならない。

光

光を巡る様々な仮説

光を理解するためには簡単に歴史的経緯を振り返ると理解しやすい。

• かつて光に関して、二つの説が立説されていた。一つは「光は粒子」、もう一つは「光は波」。それぞれニュートンとホイヘンスが立説したもの。
• 前者は、光の直進性に目をつけ光をとても軽い「粒子」であると考えた。一方後者は、ある実験から「光は粒子」という説を真向から否定して立説した。ある実験とは、小さな丸い穴に向けて光を照射して、穴の後ろに配置されたスクリーンでその光を結像させるという実験であり、もし光が直進する粒子だとするならば、その穴がどんなに小さくても、その穴の通りにスクリーンに結像されるはずであるが、実際には波のような縞模様を描いた。これを光の波動説と言う。
• しかし光を波とした場合、光の直進性の説明が難しくなる。媒質中を伝わる波（または波動）に対し障害物が存在する時、波がその障害物の背後など、つまり一見すると幾何学的には到達できない領域に回り込んで伝わっていく*1のである。これを回折という。
• 光の波動説が立説されてから暫くは、光は波であると決着がついていたがそれから約20年後、光電効果という現象が波動説での説明を困難にした。光電効果とは、金属に光を当てると、光を当てられた金属から電子が飛び出すという現象の事を示す。光の波動説に則ってこの現象を捉えると、大きな電気と電磁場の波がやってきたために、金属の中の電子が強く揺さぶられるので、もはや金属の中に留まれなくなって飛び出すと考えられる。しかし、実際の実験結果は、光の強さではなく、光の波長によって*2電子が飛び出すかが変化した。光を強くすると、それに応じて飛び出す電子の数は増加したが、どれだけ光を強くしても波長の長い光では電子は飛び出さず、波長の短い光において飛び出す電子の数が増加した。この実験結果を光の波動説で説明することは困難である。
• この光電効果の実験結果を、うまく説明するに至った説が、アインシュタインによる光量子仮説であり、これは光のエネルギーの基本単位を仮定した。
• 基本単位は、光の振動数に比例し、光の波長に反比例するというもので、比例定数はプランク定数と呼ばれ、 である。光のエネルギーは連続的な値を取らず、光量子エネルギーの整数倍である、離散的な値しか持たないと考え、さらに、光が当たった時に電子が呼び出すという現象には、1つの光量子が1つの電子に吸収されてそのエネルギーを得た電子が飛び出すというように考える。まれに2つの光量子が1つの電子に吸収されるかもしれないが、プランク定数に則って計算すると、光が非常に強い場合を除いて、低確率でしか起こり得ずその挙動を無視できる。こう仮定すると、周波数を上げていく過程で電子の飛び出す量が増えることに説明がつき、高周波中に電子の飛び出す量が増えたという結果に対しても、単純に光量子の数が増えるためにあると説明することができる。*3*4
• 光量子は、現在光子と呼ばれることが多いため、後の記述では「光子」を使う。

結局光とは何なのか

もっとも重要なのは「スリットを通った光は干渉縞を示す」という結果と光電効果に見られた結果を事実として捉えることであり、つまり、断定して言えることは光は波や粒子といったものではないと言うこと。更に、光は基本的には波だが、それぞれの波長の光に対してエネルギーの基本単位があり、その基本単位を分割することはできない、二重性のものであるということ。

波の性質を持つ粒子

光は波であると同時に粒子的な性質を持つ二重性のものであるが、以前まで粒子であると考えられていた電子や原子なども波としての性質を持つことがわかっている。*5*6。

量子力学

二重性のものに対する知見を得て、量子力学について入門する前に、少し用語とこれまでの概要を簡潔にまとめる。

• 先の実験によって、光は光子からできており、また、電気は電子からできている事が示された。このようなある基本的な単位量のことを、量子と呼ぶ。
• 先の実験のように、量子による現象や作用は、我々が日常的に体感するスケールでの物理現象における理論、つまり古典力学によって、辻褄の合うよう説明する事ができない。よって、量子スケールの微視的な物理現象を、古典力学と切り分けて定める力学が新たに設けられた。これを、量子力学という。
  つまり古典力学は、量子の集合体としての姿(物質や光などは量子から成り立っているため)における物理現象にのみ正しい理論である。よって量子力学から古典力学を導く事が可能であると考えられると同時に、世の中の全てを量子力学によって解明できるのではないかとの考察をするに値する。

光の偏光

• 古典論的解釈では、光は電磁波の一種であり、通常その進む方向と直角に電場と磁場が振動する。電場および磁場が特定の（振動方向が規則的な）方向にのみ振動する光のことを偏光という。 電磁波の場合は偏波と呼ぶ。 光波の偏光に規則性がなく、直交している電界成分の位相関係がでたらめな場合を非偏光あるいは自然光と呼ぶ*7。
• 偏光には電場（および磁場）の振動方向が一定である直線偏光、電場（および磁場）の振動が伝播に伴って円を描く円偏光(回転方向によって、右円偏光と左円偏光がある。角運動量を持つ。)、電場（および磁場）の振動が時間に関して楕円を描く、楕円偏光(右楕円偏光と左楕円偏光がある。)がある。以下にその図を示す。左からそれぞれ直線偏光、円偏光、楕円偏光を示している。
  
  

By Superborsuk - Transferred from pl.wikipedia, パブリック・ドメイン, Link
Copyrighted free use, Link
By from [1], Copyrighted free use, Link

• 上図のように、特に直線偏光における進む方向と直角な向きは様々である。電場が水平方向に振動する光を水平偏光、垂直な方向に振動する光を垂直偏光という*8。
• この偏光の性質を工学的に利用したものの代表例として、ある特定の偏光だけを通す性質を持つ、偏光フィルタというものがある。これは、ある特定の方向の偏光だけを通す性質を持つ。例えば垂直偏光だけを通し水平偏光を全く通さない偏光フィルタの場合、当然水平偏光がそのフィルタを通過して到達する事はない。水平と垂直の中間の偏光がこの偏光フィルタに入った場合、その角度に応じて垂直偏光が出てくる。例えば角度45度で入射した場合は、入射した丁度半分のエネルギーを持った垂直偏光が出てくるのである。
  
  

パブリック・ドメイン, Link

• 二枚の偏光フィルタがあり、それぞれの透過する変更の方向が互いに垂直である場合(例：片方が垂直偏光を遮断する偏光フィルタ、片方が水平方向を遮断する平行フィルタ)、その二枚の偏光フィルタを重ねた部分は光が一切透過できないため真っ黒になる。この場合、1枚目の偏光フィルタによって水平方向の偏光を透過するが、2枚目の偏光フィルタによって水平方向の偏光を遮断するため、当然の原理である。

• 偏光フィルタと似たような昨日を持つ光学素子として、偏光ビームスプリッタというものがある。偏光フィルタでは、透過する偏光の垂直方向にある偏光を遮断するが、偏光ビームスプリッタは、その偏光を丁度90度直角方向に反射する。

• この偏光ビームスプリッタに対して45度偏光を入射すると、水平偏光と垂直偏光の2つの偏光に均等なエネルギーで分解されて出てくる。つまり、例えば仮にある光がどのような偏光なのかを調べたいとした時に、偏光ビームスプリッタへ入射して、二つの出射面から出てくる光の強度を検出器で調べれば、その光がどのような偏光なのか分かるのである。水平偏光、または垂直偏光の場合は、どちらか一方だけの検出器で光が検出されるため、それもすぐに断定する事ができるのである。

光子の偏光

• 光子 1 つに偏光を持たせて偏光ビームスプリッタへ入射した場合、つまり、垂直方向、水平方向の光子を入射すると、それぞれ透過あるいは直角に反射される。しかし、ここに45度偏光の光子を入射するとすると、光子は量子であり、エネルギーの最小単位であるため二つに分割される事はないはずである。もしこれが仮に分割されてしまえば、アインシュタインによる光量子の考え方に反することとなるためである。実際の実験結果は、透過した側で検出される場合と90度反射された側で検出された場合がでたらめに現れる事となる。
• この実験を幾度も繰り返すと、偏光ビームスプリッタによって透過する光子と反射する光子の割合がほぼ厳密に等しく収束する。この実験を幾度も繰り返すという事は、たくさんの光子、つまり通常の光を用いて実験する事に等しく、この結果は45度偏光を入射した場合の結果と対応している。
• 1つ1つの光子が偏光ビームスプリッタを通過しようとする際、透過側に出るのか、反射側に出るのかを完全に予想する手段はない。これを不確定性定理という。

45度偏光の光子1つ1つを打ち込んで割合が均等になっていく様子を観測してみたい。

— roκi (@530506) 2017年6月5日

重ね合わせ

量子力学、量子コンピュータ実用化における核心である重ね合わせについて理解する。重ね合わせの理解には、先ほどの偏光ビームスプリッタの代わりに半透鏡という道具を用いて、実験を元に考察する。

半透鏡

半透鏡とは、入射した光の丁度半分の光だけが透過し、半分の光が反射する性質を持つ鏡である。実用例としては、マジックミラーなどが挙げられる。明るい空間とくらい空間をマジックミラーで仕切ると、暗い空間にいる人は自分のいる空間からの光が鏡を反射してくるのよりも、明るい空間からの光が鏡を通過してくる方が強いため、明るい空間の様子が分かるが、明るい空間にいる人から見ると、自分のいる空間の光がか鏡で反射する方が暗い空間からの光よりも強いため、一見ただの鏡のように見える。これが、マジックミラーの原理である。

干渉計

• 半透鏡に単一の光子と比較して強い光を入射すると、偏光ビームスプリッタのように、半分は透過し、半分は反射される。半分になった光をそれぞれ鏡で更に反射させて、戻ってきた交点にまた半透鏡を置くと、その鏡の位置によって、半透鏡から出る光の一方が強まったり、両方同じ強さで出たりする。これを干渉計という*9*10。このような干渉計などで2つの光が重なり、その2つの光の山谷がぴったり重なり合う状態を、位相差が0の状態、位相が一致した状態という。またそうでない場合を、位相がずれた状態という。
• 半透鏡に1つの光子を入射したとしても、光子は2つに分割される事はない。よって、光子は2つの出口からでたらめに検出される。これは、半透鏡は光子をでたらめに反射しているように思える。
• 次に、干渉計に光子を入射する。この場合、干渉計の一方の出力から光子が射出される確率は経路の長さに応じて変化する。つまり、2つの経路が全く同じ長さであれば単一の光子ではない強い光を入射した時と同じように、必ず射出される出口とそうでない出口が確定し、経路の長さが波長の半分だけ異なる場合は、必ず射出される出口とそうでない出口が入れ替わり、確実にそのように射出される。
• つまり、半透鏡は、光子をでたらめに反射しているのではない。光子が1粒になったとしても、それは波としての性質を持つ事がここでも伺える。しかし、半透鏡はたった1 粒の光子から、どのように両方の経路の差を知る事ができているのか。これは、確率波という概念で説明される。半透鏡に光子を入射した時の光子は、粒ではなく、ある振幅を持った2つの経路の確率波であるという*11。この概念は、干渉計の中で光子が、単純にどちらかの経路にのみ存在するというわけではないし、更に、光子が二つに分割されてそれぞれの経路へ進行したわけでもない事を示す、今まで通りの量子力学らしい正に辻褄合わせのような概念である*12。
• このような確率波の概念でしか説明する事のできない、つまり、ある振り幅を持った2つの確率波として表される状態にあるとしか言えない状態を、重ね合わせ状態という。
  
• 重ね合わせ状態は、どちらの状態にあるかを知る、つまり観測しようとすると、重ね合わせ状態が崩壊してしまう。つまり、でたらめにどちらかの経路に存在するという状態になる。これを重ね合わせ状態の破壊、デコヒーレンスという。ちょうど、先の偏光ビームスプリッタの実験は、重ね合わせ状態を破壊しているといえる。

物理学とコンピュータ

量子力学の理論をコンピューターの演算処理の原理として応用しようというものが、量子力学とコンピュータの関係性であり、これを量子コンピュータという。この確率波と重ね合わせ状態を駆使して膨大な並列計算を一気に行おうというアイデアが量子コンピュータの根本にある。そもそも、今私もこのエントリを執筆しているのに用いるコンピュータは、古典力学的な物理法則に則って動作している。しかし、その根本を構成するにあたる現代的な物理学、量子力学の物理法則に則ってコンピュータが動作すれば、この世界の最大限の能力を引き出して演算処理を実行する事ができるのである。

量子ビット

量子ビットは、従来のビットの概念とは異なり、0と1の二つの状態だけでなく、その重ね合わせ状態をとる。これはまず、0と1の中間の状態を持っている、もしくは確率的に0または1の状態であるというようなものではない。先の実験の考察から、重ね合わせ状態を説明するには、確率波という概念が必要であった。つまり量子ビットは、0または1の二つの状態をとる確率波そのものである。量子ビットの状態を知るには、0または1である確率に関する情報の他に、位相という情報が必要になる。0または1である確率を、重みという。
量子ビットは、ブロッホ球といわれる、三次元球体で表現する事ができ、その状態は、球面状の1点で表される。

By Smite-Meister - 投稿者自身による作品, CC 表示-継承 3.0, Link

以下に要点をまとめる。

1. ブロッホ球は、ブラ-ケット記法という記法によって、式にする事ができる。ブラ-ケット記法は、量子の状態を で表す。この時例えば、 は、 の振り幅が 、 は、 の振り幅が である事を示す。
2. ブロッホ球の緯度と経度それぞれの軸は、緯度が か かの重さを、経度が重ね合わせ状態の位相の違いを表している。
   尚、上図のように示される状態は、次の式 に対応している。
3. 0の状態の量子ビットは北緯90度の北極に対応し、式では、 と表される。
4. 1の状態の量子ビットは、南緯90度の南極に対応し、式では、 と表される。
5. と が成り立つ時、2.にて上掲された式から、次の式 が成り立つ。例えばこの状態でこの量子ビットを観測、つまり、量子ビットの または の確率を知りたい場合、それぞれの係数を2乗したもので得る事ができる。つまり、4で前掲された条件の場合、 が である確率、 が、 である確率を表す事となり、 が成り立つ。よって例えば であれば、量子ビットは の状態であり、 であれば、量子ビットは の状態である事がいえる。
6. 例えば、赤道上の1点であった場合、丁度0と1が同じ割合だけ重なり合ったような状態の量子ビットに対応する。式では、 または と表される。それぞれブロッホ球上の裏表の関係に値する。

量子ビットから成るコンピューターの構成

このような量子ビットをビットの代わりに用いる時、当然ながら従来のコンピューターでビットが扱われるパーツが取って代わる事になる。つまり、メモリとレジスタが、量子ビットによって構成された量子メモリと量子レジスタに代わる。2ビットの従来型メモリで考えた場合、そのメモリには、00、01、10、11のいずれかの値が乗る事になるが、2つの量子ビットである場合は 、 、 、 のどれか1つではなく、これらの重ね合わせ状態となる事ができる(式で表すならば、2つの量子ビットをそれぞれ として、全ての状態が同じ重さである場合は、 という関係にある。)ので、量子ビット数の増加による一度に扱える重ね合わせ状態の数は、従来のビットとは比べ物にならないほど爆発的に飛躍する。これが、大規模な並列計算を支援するのである。

量子ゲート

古典的な計算では、演算に論理回路を使う事で演算するが、量子ビットでは量子論理回路を使う。量子論理回路は、量子ビットを入出力に持ち、量子ビットに対して量子ゲートを作用させる。量子ゲートには様々な種類があるが、量子ゲートにおける万能ゲートは回転ゲートと制御ノットゲートの二つである。

回転ゲート

1つの量子ビットに対してのみ作用するゲートで、三次元で表された量子ビットをある与えられた角度だけ回転させる。

• を軸方向に180度回転させた場合、 となる。これを更に軸方向に180度回転させれば、 となる。これは、古典ゲートのNOTゲートに相当し、これをゲートと言う。
• を軸方向に90度回転させた場合、 となる。更に90度回転させた場合、 となり、これを更に2回90度回転させていくと 、 というように戻ってくる。

アダマールゲート

回転ゲートの一種で、ブロッホ球上のz軸とx軸方向に45度傾いた方の軸周りに180度回転させるゲートである。 にアダマールゲートを作用させると、 に、再び作用させると に戻る。 にアダマールゲートを作用させると に 、再び作用させると に戻る。アダマールゲートを とした時、 、 が成り立つ。

制御ノットゲート

制御NOTゲートは、2つの量子ビットの入力に対して2つの量子ビットを入出力する。入力された2つの量子ビットの一方を制御ゲート、もう一方を目標ゲートとする(実際はやみくもにこれらが決まるのではない)。このゲートは、この2つの量子ビットに対して制御ビットが1の場合のみ、信号ビットを反転させる。例えば が制御ビット、 が信号ビットとし、制御NOTゲートへ入力する時、 である場合、 であろうが であろうが信号ビット は変化しない。 である場合、 であれば に、 であれば というように信号ビットが反転する。制御NOTゲートは、制御ビットの重ね合わせ状態に依存して信号ビットが変動するため、2つの量子ビットの状態を切り離して考える事ができなくなる事がある。これを量子もつれ合い状態や、エンタングル状態という。回転ゲートが1つの量子ビットの状態をある状態から別の状態に変化させる事しかできないのに対して、量子もつれあい状態を唯一作る事ができるのが、制御NOTゲートである。制御NOTゲートが対象とする制御ビットは必ずしも一つだけでなければならないわけではなく、以下のツイートのように二重制御NOTゲートと呼ばれる、2つの制御ビットの値が両方ともの時だけ信号ビットを反転させるなどといったような回路も組める。

制御NOTゲートを覚えた事で1+0,1+1の量子回路組めた.画像は1+1.入力用の量子ビットを制御ビットとして固定してるから簡単. pic.twitter.com/fam6OW9LOF

— roκi (@530506) 2017年6月8日

各量子ビットを上から とした場合、上記の状態は式 と表せる。そして、この回路を通すと、 という状態になったと言える。上記のような演算の場合、古典回路で何ら問題がないわけだが、この回路が強力なのは、重ね合わせ状態の量子ビットを入力できる点である。例えば入力が、 という重ね合わせ状態の量子ビットだったとした場合、演算の結果、 を得ることができるのである。しかし、この状態をそのまま観測しても4つの答えを同時に得ることは当然ながら出来ず、どれか1つをでたらめに得られる。

次回では、このような問題に対する解決策や量子コンピュータにおけるアルゴリズムについて取り上げる。

*1:https://ja.wikipedia.org/wiki/回折

*2:光の波長については前提知識があったので省略している。一応、光の波長について参考となりそうなものを貼っておく：https://www.konicaminolta.jp/instruments/knowledge/color/part2/02.html

*3:光が粒子のような性質も持つことを更に確定的なものとした実験に、コンプトン散乱がある。

*4:更に詳しい歴史的経緯はWikipediaに分かりやすく網羅されている。

*5:ド・ブロイの仮説によるド・ブロイ波などを参照

*6:古典論、つまり電子を粒子とした論では説明のできない実験事実の代表例として、「水素原子がなぜ安定に存在できるのか」という問題に対する考察を参照

*7:https://ja.wikipedia.org/wiki/偏光

*8:参考：http://www.luceo.co.jp/technical/pdf/henkou1-1.pdf

*9:https://www.ibm.com/developerworks/jp/cloud/library/cl-quantum-computing/index.html

*10:マクスウェルの方程式参照

*11:光子がその経路に存在する確率は、確率波の振幅の二乗である

*12:アインシュタインも、最後までこの考え方には納得していなかったらしい

scala 始めました

scala警察が怖いという話題で少し盛り上がっていたので、始めてみた。sbtとscalaはbrewから導入した。sbt consoleを使ってbuild.sbtの内容を読み込み、チマチマplay groundを遊ぶ。build.sbtにはscalaのバージョンと、-deprecation,-feature,-unchecked,-XlintをscalacOptionsに指定している。本項では、scalaを始めていく中で個人的に興味深く感じる部分などをつらつらと学習メモがてらにまとめている。決して入門を促す記事ではないし、個人的見解が多分に含まれる事、留意して頂きたい。

そんなわけで、取り敢えずクイックソートを書いてみた。

scala> import scala.util.Random
import scala.util.Random

scala> def qsort(lst:List[Int]): List[Int]=
     | lst match{
     | case p::ys=>
     | qsort(for(y<-ys if y<p)yield y) ::: List(p) ::: qsort(for(y<-ys if y>=p)yield y)
     | case _ => Nil
     | }

qsort: (lst: List[Int])List[Int]

scala> qsort(List.fill(20)(Random.nextInt(20)))
res1: List[Int] = List(0, 1, 2, 4, 4, 5, 5, 6, 7, 10, 10, 10, 12, 12, 13, 14, 14, 16, 18, 18)

forのyieldだったり、Listを平面化しながらのappendが:::で済むというのが、やはり良い。あと型に対するパターンマッチはやはり素晴らしい。C++でやろうとすればif constexprとtype traitsやSFINAE、テンプレートの特殊化を使うことになるだろうが、直感的に書けるパターンマッチという機能は便利だ。filterを使えばこのコードは更に単純化できる。

import scala.util.Random

object obj{
  def qsort(lst:List[Int]):List[Int] = lst match{
    case pivot::tail => qsort(tail filter{_ < pivot}) ::: List(pivot) ::: qsort(tail filter{_ >= pivot})
    case _ => Nil
  }
  def main(Args:Array[String]):Unit = {
    val lst = List.fill(20)(Random.nextInt(20))
    println(lst)
    println( qsort(lst) )
  }
}

C++で全く同じ事を書こうとすればこうなるだろうか。

#include<iostream>
#include<numeric>
#include<random>
#include<boost/range/algorithm/copy.hpp>
#include<vector>
#include<array>
#include<experimental/iterator>

template<class T>
T& qsort(T& v)
{
        if(v.empty())return v;

        std::vector<typename T::value_type> left,right;
        std::partition_copy(
                        std::next(std::begin(v),1),std::end(v),
                        std::back_inserter(left),std::back_inserter(right),
                        [pivot=*std::begin(v)](auto&& x){return x < pivot;}
        );
        std::vector<typename T::value_type> l = qsort(left),r = qsort(right);
        typename T::value_type pivot = *std::begin(v);

        boost::copy(left,std::begin(v));
        v[left.size()]=std::move(pivot);
        boost::copy(right,std::next(std::begin(v),left.size()+1));
        return v;
}

template<class T>
std::ostream& operator<<(std::ostream& os,T&& ar)
{
        boost::copy(std::forward<T>(ar),std::experimental::make_ostream_joiner(os,","));
        return os;
}

int main()
{
        std::array<int,42> ar;
        std::iota(std::begin(ar),std::end(ar),0);
        std::shuffle(std::begin(ar),std::end(ar),std::mt19937());
        qsort(ar);
        std::cout << ar << std::endl;
}

やはり連結の機能が乏しく感じる...。入力をイテレータから受け付けるのであれば下記のように無駄なコピーとかは省けるが

template<class Iter>
void qsort(Iter first,Iter last)
{
        if(first==last)return;
        Iter l=first,r=std::next(last,-1);
        while(l<r){
                for(; *r>*first; --r);
                for(; *l<=*first and l<r; ++l);
                std::iter_swap(l,r);
        }
        std::iter_swap(first,l);
        qsort(first,l);
        qsort(std::next(l,1),last);
}

Scalaに比べて冗長的だ。
ただ、Scalaで一つ不便に思ったのは、コレクションの内部型(という言い方がscala的には正しいのか定かではないが)によって分岐するパターンマッチは書けないというところ。

scala> val lst:List[Int] = List.fill(5)(0)
lst: List[Int] = List(0, 0, 0, 0, 0)

scala> lst match{
     | case _:List[String] => println("is String")
     | case _:List[Int] => println("is Int")
     | }
<console>:14: warning: fruitless type test: a value of type List[Int] cannot also be a List[String] (the underlying of List[String]) (but still might match its erasure)
       case _:List[String] => println("is String")
              ^
<console>:15: warning: unreachable code
       case _:List[Int] => println("is Int")
                                  ^
is String

これはscalaコンパイラによるerasureという動作によってコレクションの内部型情報が削除されてしまうために上記の場合List[String]とList[Int]の判別ができない。もしこれを判別したければ、以下のようにしてワイルドカードを用いて内部でさらにパターンマッチを行うしかないのだろうか。何か良い方法がありそうだが。

scala> import java.util.Locale
import java.util.Locale

scala> val lst:List[AnyRef]=List.fill(5)("hoge")
lst: List[AnyRef] = List(hoge, hoge, hoge, hoge, hoge)

scala> lst match{
     | case x:List[_] =>
     | x.head match {
     | case _:java.lang.Integer => println("is integer")
     | case _:String => println("is String")
     | case _ => println("other")
     | }
     | case _ => println("other")
     | }
is String

さて、話は変わって演算子のオーバーロードができるようだ。

scala> class Point(val x:Int,val y:Int){
     | def +(other:Point): Point = new Point(other.x+x,other.y+y)
     | override def toString():String = "(" + x + "," + y + ")"
     | }
defined class Point

scala> val p = new Point(42,42)
p: Point = (42,42)

scala> println(p + p)
(84,84)

toStringはprintlnで出力するためにオーバーライドして定義する。それと、メソッドのシグネチャに複数の引数リストを作る構文がある事に驚きだ。これはつまりカリー化という概念を文法としてサポートする事を意味する。

scala> def plus(x: Int)(y: Int):Int = x+y
plus: (x: Int)(y: Int)Int

scala> val plus10 = plus(10)_
plus10: Int => Int = $$Lambda$1202/791874361@70061cf6

scala> plus10(20)
res3: Int = 30

C++では、主にラムダをネストしていく事でカリー化を実現するが、これもscalaでは簡潔に書ける。さて、クラスの継承は以下のように書く。

scala> class X(){
     | def print():Unit = println("X")
     | }
defined class X

scala> class Y() extends X{
     | override def print():Unit = println("Y")
     | }
defined class Y

scala> new X().print()
X

scala> new Y().print()
Y

scalaでは親クラスと同名のメソッドをoverrideキーワードなしで定義しようとするとエラーとなる。オーバーライドしたつもりになる可能性を考えれば、まぁ確かに禁止にするのも良い方針か。

scala> class Y() extends X{ def print():Unit = println("Y")}
<console>:12: error: overriding method print in class X of type ()Unit;
 method print needs `override' modifier
       class Y() extends X{ def print():Unit = println("Y")}
                                ^

また、scalaのobjectにおいて、applyという名前のメソッドが、scala処理系では特別に扱われる。

scala> class X()
defined class X

scala> object X{
     | def apply():X = new X()
     | }
defined object X
warning: previously defined class X is not a companion to object X.
Companions must be defined together; you may wish to use :paste mode for this.

scala> X()
res0: X = X@2ad7126

この場合、X()という記述によってX.apply()が呼ばれる事となる。また、クラス名と同じ名前のシングルトンオブジェクトはコンパニオンオブジェクトと呼ばれ、対応するクラスのprivate[this]以外のprivateフィールドに対して特権的な権限を持っており、その性質を無視してアクセスを可能とする。 クラスとコンパニオンオブジェクトの関係性を正しくコンパイラに示すためには、両者の記述を同一ファイル中に示す必要がある。REPLでは上記のように、一つ一つの入力でコンパニオンオブジェクトを定義した場合、その関係性を正しく認識できないとの事で、警告文が出力されている。よってREPLでは、:pasteコマンドによってペーストモードへ移行し、そのモード中にクラスとそれに対するコンパニオンオブジェクトを一度に入力する必要がある。

scala> :paste
// Entering paste mode (ctrl-D to finish)

class X(private val x:Int)
object X{
def print():Unit = {
val a:X = new X(42)
println(a.x)
}
}

// Exiting paste mode, now interpreting.

defined class X
defined object X

scala> X.print()
42

scalaでは、トレイトの実体化は行えないが、new trait{}というようにするとそのトレイトを継承した空のクラスが暗黙生成され実体化されるとのことで、トレイトそのものの実体化ではないことに留意。

scala> trait traitT{def f():Unit = println("f")}
defined trait traitT

scala> new traitT{}.f()
f

また、scalaでは、菱形の継承関係にある実態に対する曖昧さ解決に主に二つの方法が取られる。1つは、他の言語でも馴染みのある、型を明示的に指定する方法。

scala> trait A{def f():Unit}
defined trait A

scala> trait B extends A{def f():Unit = println("B::f")}
defined trait B

scala> trait C extends A{def f():Unit = println("C::f")}
defined trait C

scala> class X extends B with C{
     | override def f():Unit = println("X::f")
     | }
defined class X

scala> class Y extends B with C{
     | override def f():Unit = super[B].f()
     | }
defined class Y

scala> class Z extends B with C{
     | override def f():Unit = super[C].f()
     | }
defined class Z

scala> (new X).f()
X::f

scala> (new Y).f()
B::f

scala> (new Z).f()
C::f

scala> class ZZ extends B with C{
     | def f():Unit = println("non override")
     | }
<console>:14: error: overriding method f in trait C of type ()Unit;
 method f needs `override' modifier
       def f():Unit = println("non override")
           ^

菱形の継承関係にあるクラスで該当するメソッドのオーバーライドを行わない事は許されず上記の通りエラーとなる。
もう一つはlinearizationという方法。この方法は、菱形関係になりうるトレイトの定義内の関数において、overrideキーワードを付与する事でその効果が発揮される事を示す。linearizationを行うと、トレイトのミックスインの順序に依存して、つまり最後にミックスインされたトレイトの同メソッドを呼び出すようになる。

scala> trait A{def f():Unit}
defined trait A

scala> trait B extends A{override def f():Unit = println("B::f")}
defined trait B

scala> trait C extends A{override def f():Unit = println("C::f")}
defined trait C

scala> class X extends B with C
defined class X

scala> (new X).f()
C::f

scala> class X extends C with B
defined class X

scala> (new X).f()
B::f

このような線形化によるトレイトの積み重ねの処理をStackable Traitと呼ぶ。また、scalaにはself type annotationsまたはself typeと呼ばれる機能がある。self type annotationは、自身の型にアノテーションを追加記述できるように設定する事で、機能を後に注入する事ができる機能である。

scala> trait T{ def f():Unit }
defined trait T

scala> trait X{
     | self: T =>
     | def invoke():Unit = f()
     | override final def toString = "X"
     | }
defined trait X

上記のコードだと、メソッドfに対して機能を後に定義する事ができる。

scala> trait printHello extends T{
     | def f():Unit = println("Hello")
     | }
defined trait printHello

scala> val t = new X with printHello
t: X with printHello = X

scala> t.f()
Hello

このように、後から利用するモジュールの実装を与えることを依存性の注入（Dependency Injection）と呼ぶ。

トレイトには、初期化を遅延する方法がある。例えば、以下のような場合

scala> trait A{ val s:String }
defined trait A

scala> trait B extends A { val bar:String = s + "World" }
defined trait B

scala> class C extends B{
     | val s:String = "Hello"
     | def print():Unit = println(bar)
     | }
defined class C

scala> (new C).print()
nullWorld

scalaのトレイトは、上から順番に初期化されていくため、trait A内のsが末初期化の状態でtrait Bのbarの初期化に使われる。同時点で、末初期化のs、つまりnullと"World"というStringオブジェクトが連結されて初期化されるため上記のような結果となる。このような事を未然に防ぐためには、初期化順序をよく把握している事が最も重要であるが、初期化の遅延を行うlazyキーワードを用いる事でも可能である。

scala> trait A{ val s:String }
defined trait A

scala> trait B extends A { lazy val bar:String = s + "World" }
defined trait B

scala> class C extends B{
     | val s:String = "Hello"
     | def print():Unit = println(bar)
     | }
defined class C

scala> (new C).print()
HelloWorld

lazyキーワードが付与されたオブジェクトは実際に使われる部分で初期化が行われる。しかしその分若干オーバーヘッドが発生してしまい、マルチスレッド下では最悪デッドロックが発生してしまう可能性がある。トレイトの初期化順序を遅延させるもう1つの方法として、事前定義（Early Definitions）を使う方法もある。

scala> trait A{ val s:String }
defined trait A

scala> trait B extends A{ val bar = s + "World" }
defined trait B

scala> class C extends { val s = "Hello" } with B { def f():Unit = println(bar) }
defined class C

scala> (new C).f()
HelloWorld

Early Definitionsはクラス定義の時点での回避方法、つまり利用者側の回避方法となるため、利用者側で止むを得ない場合に当機能を利用するかもしれないが、問題の起因はトレイトB側にあるためトレイトBの定義を改変できない特別な理由がない限りは当機能を使うことはないだろう。

クラス、メソッドには型パラメータという機能を用いることができるとのこと。C++のテンプレートといったところか。

scala> class X[T](var l:T,val r:T){
     | final override def toString():String = "(" + l + "," + r + ")"
     | }
defined class X

scala> new X(42,42)
res0: X[Int] = (42,42)

しかし、Variadic templates的な機能はないようで、例えばタプルはTuple1からTuple22までがコピペコードによって標準搭載されているとのこと。Variadic templatesは欲しかったなぁ。

scala> new Tuple3(42,"hoge",42.4)

res2: (Int, String, Double) = (42,hoge,42.4)

scala> (42,"hoge",42.4)
res3: (Int, String, Double) = (42,hoge,42.4)

scala> (42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42)
<console>:1: error: too many elements for tuple: 23, allowed: 22
(42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42,42)

上記の通り、オブジェクトを()で囲むと、タプルが暗黙生成されるようだ。23以上になると、当然タプルの生成ができないのでエラーとなる。

また、Scalaでは、何も指定しなかった型パラメータは通常はinvariantとなる。

scala> class X[T](x:T){ override def toString():String = x.toString }
defined class X

scala> var a = new X(42)
a: X[Int] = 42

scala> val b = new X(53)
b: X[Int] = 53

scala> a = b
a: X[Int] = 53

scala> class A{ override def toString():String = "This is A" }
defined class A

scala> class B extends A{ final override def toString():String = "This is B" }
defined class B

scala> var a = new X(new A())
a: X[A] = This is A

scala> val b = new X(new B())
b: X[B] = This is B

scala> a = b
<console>:13: error: type mismatch;
 found   : X[B]
 required: X[A]
Note: B <: A, but class X is invariant in type T.
You may wish to define T as +T instead. (SLS 4.5)
       a = b
           ^

covariantの動作を行うためには、型パラメータに+を付与する。

scala> class X[+T](x:T){ override def toString():String = x.toString }
defined class X

scala> class A{ override def toString():String = "This is A" }
defined class A

scala> class B extends A{ final override def toString():String = "This is B" }
defined class B

scala> var a = new X(new A())
a: X[A] = This is A

scala> val b = new X(new B())
b: X[B] = This is B

scala> a = b
a: X[A] = This is B

covariantでは継承元に継承先を代入することができる機能であるがそれに対してcontravariantという機能もある。これは、継承先に継承元の代入を許す。記述としては、型パラメータに対して-を付与する。

scala> class X[-T](x:T){ override def toString():String = x.toString }
defined class X

scala> class A{ override def toString():String = "This is A" }
defined class A

scala> class B extends A{ final override def toString():String = "This is B" }
defined class B

scala> val a = new X(new A())
a: X[A] = This is A

scala> var b = new X(new B())
b: X[B] = This is B

scala> b = a
b: X[B] = This is A

また、型制約を設けることもできる。これはとても良い。渡されたオブジェクトが、E >: Tの継承関係にある場合に呼び出すようにしてみると以下のようになる。

scala> class X[T]{ def f[E >: T](t:T): Unit = println("ok") }
defined class X

scala> class Y
defined class Y

scala> (new X[Int]).f(new Y)
<console>:14: error: type mismatch;
 found   : Y
 required: Int
       (new X[Int]).f(new Y)
                      ^

scala> class Z extends Y{ final override def toString():String = "This is Z" }
defined class Z

scala> (new X[Y]).f(new Z)
ok

また、scalaでは、関数と言ったら、それは大抵標準搭載されたFunction0〜Function22のトレイトの無名サブクラスのインスタンスの事を示すのだとのこと。

scala> val plus = new Function2[Int,Int,Int]{
     | def apply(x:Int,y:Int):Int = x + y
     | }
plus: (Int, Int) => Int = <function2>

scala> plus(10,20)
res0: Int = 30

Functionnの三つの引数は左からそれぞれのパラメータ型、最後が返却型となっている。これは以下のようなsyntax sugerが搭載されている。

scala> val plus = (x:Int,y:Int) => x + y
plus: (Int, Int) => Int = $$Lambda$1328/628570906@4c524cb9

scala> plus(10,20)
res1: Int = 30

scala> val plus = (_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int)
<console>:1: error: too many elements for tuple: 23, allowed: 22
val plus = (_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int,_:Int)

これも、23以上のFunctionは標準搭載されていないので、暗黙生成させることはできない。 また、関数の型は、以下のように省略する事ができる。

scala> val plus:Function2[Int,Int,Int] = (x:Int,y:Int) => x + y
plus: (Int, Int) => Int = $$Lambda$1349/1622814373@55417169

scala> val plus:(Int,Int)=>Int  = (x:Int,y:Int) => x + y
plus: (Int, Int) => Int = $$Lambda$1350/566120649@771e97aa

scala> val plus:Function1[Int,Function1[Int,Int]] = (x:Int) => ((y:Int) => x + y)
plus: Int => (Int => Int) = $$Lambda$1362/1779572183@64635707

scala> val plus:Function1[Int,(Int)=>Int] = (x:Int) => ((y:Int) => x + y)
plus: Int => (Int => Int) = $$Lambda$1363/969408428@24bc022

scala> val plus:(Int) => (Int) => Int = (x:Int) => ((y:Int) => x + y)
plus: Int => (Int => Int) = $$Lambda$1364/1710966481@35c89f3b

下三つは全て同じ意味となる。カリー化に関して言えば、複数の引数リストを用いる事でも同様の事が実現できる。しかしこれは関数ではなくメソッドであることに留意されたし。

scala> def plus(l:Int)(r:Int):Int = l + r
plus: (l: Int)(r: Int)Int

scala> val plus10 = plus(10)_
plus10: Int => Int = $$Lambda$1375/155403162@28c4ecfb

scala> plus10(100)
res6: Int = 110

scala> val func_plus = plus _
func_plus: Int => (Int => Int) = $$Lambda$1376/1282098776@98b2097

scala> func_plus(10)(100)
res7: Int = 110

scala> val func_plus:Function1[Int,Function1[Int,Int]] = plus _
func_plus: Int => (Int => Int) = $$Lambda$1378/816291015@60b0b8ea

冒頭ではplusメソッドを定義しているが、引数リストの一部にワイルドカードを使用すると関数が得られる。この時得られるのはメソッドではなく関数であるため、Functionnトレイトの無名サブクラス型のオブジェクトが返される。これはつまり、値が得られるという事を意味する。scalaでは、このようにメソッドと関数が厳密に区別される。両者の違いは、値が得られるかそうでないかが最も大きな差異となる。主にdefキーワードを用いて定義されたものはメソッドであり、メソッドそのものをオブジェクトとする事はできない。

scala> def predicater(l:Int,r:Int,f:(Int,Int) => Boolean):Boolean = f(l,r)
predicater: (l: Int, r: Int, f: (Int, Int) => Boolean)Boolean

scala> val less= (x:Int,y:Int) => x < y
less: (Int, Int) => Boolean = $$Lambda$1379/134733223@1db6fc87

scala> def predicater(l:Int,r:Int,f:(Int,Int) => Boolean):Boolean = f(l,r)
predicater: (l: Int, r: Int, f: (Int, Int) => Boolean)Boolean

scala> val less = (x:Int,y:Int) => x < y
less: (Int, Int) => Boolean = $$Lambda$1380/1245768732@7244e3f7

scala> val greater = (x:Int,y:Int) => !less(x,y)
greater: (Int, Int) => Boolean = $$Lambda$1382/1363010125@546ad6ad

scala> predicater(10,20,less)
res8: Boolean = true

scala> predicater(10,20,greater)
res9: Boolean = false

これを高階関数という。これは関数ではなくメソッドであるのだが、便宜上高階関数と言うのだとか。

あと例外も使えるようだ。

scala> def f(g:()=>Unit,h:()=>Unit):Unit = {
     | try{g()}finally{h()}
     | }
f: (g: () => Unit, h: () => Unit)Unit

scala> f( () => println("Maybe no throw"), () => println("Call") )
Maybe no throw
Call

scala> f( () => throw new Exception("throw exception"), () => println("But call") )
But call
java.lang.Exception: throw exception
  at .$anonfun$res3$1(<console>:13)
  at scala.Function0.apply$mcV$sp(Function0.scala:34)
  at .f(<console>:12)
  ... 39 elided

foldは、左右ともにサポートされている。

scala> (1 to 10).foldLeft(0)((x,y) => x + y)
res5: Int = 55

scala> def reverse[T](lst:List[T]):List[T] = lst.foldLeft(Nil:List[T])((a,b) => b::a)
reverse: [T](lst: List[T])List[T]

scala> reverse((1 to 10).toList)
res6: List[Int] = List(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)

ケースクラスといわれる機能もある。C++でのスコープ付きenumっぽい感じだ。

scala> sealed abstract class Student
defined class Student

scala> case object Bob extends Student
defined object Bob

scala> case object Tom extends Student
defined object Tom

scala> case object Jejus extends Student
defined object Jejus

scala> case object Maria extends Student
defined object Maria

scala> val x:Student = Maria
x: Student = Maria

sealedというキーワードはスーパークラス/トレイトに付与すると、その基の直接的なサブクラス/トレイトが同じファイル内でしか定義できないようにする修飾子である。ケースクラスの機能を使う場合に多様されるらしく、sealedキーワードを付与することで、パターンマッチングの際のパターンとして網羅できていない場合に、コンパイラが警告文を発してくれるようになるとのこと。

scala> x match {
     | case Bob => ()
     | case Tom => ()
     | case Maria => ()
     | }
<console>:16: warning: match may not be exhaustive.
It would fail on the following input: Jejus
       x match {
       ^

C++のスコープ付きenumなどと異なる点は、Scalaではあくまでクラスであるため、各々のデータが独立してパラメータを持てる点だ。

scala> sealed abstract class Expression
defined class Expression

scala> case class Add(lhs:Expression,rhs:Expression) extends Expression
defined class Add                                                             ^

scala> case class Sub(lhs:Expression,rhs:Expression) extends Expression
defined class Sub

scala> case class Mul(lhs:Expression,rhs:Expression) extends Expression
defined class Mul

scala> case class Div(lhs:Expression,rhs:Expression) extends Expression
defined class Div

scala> case class int(value:Int) extends Expression
defined class int

scala> val exp = Add(int(42),Div(int(10),int(10)))
exp: Add = Add(int(42),Div(int(10),int(10)))

scala> def eval(exp:Expression):Int = exp match {
     | case Add(l,r) => eval(l)+ eval(r)
     | case Sub(l,r) => eval(l)- eval(r)
     | case Mul(l,r) => eval(l)* eval(r)
     | case Div(l,r) => eval(l)/ eval(r)
     | case int(v) => v
     | }
eval: (exp: Expression)Int

scala> eval(exp)
res3: Int = 43

無効な値を意味するoptionも勿論準備されている。

scala> val op:Option[Int] = Option(42)
op: Option[Int] = Some(42)

scala> op.get
res0: Int = 42

scala> op.isEmpty
res1: Boolean = false

scala> op.isDefined
res2: Boolean = true

scala> val op:Option[Int] = None
op: Option[Int] = None

scala> op.isEmpty
res3: Boolean = true

scala> op.isDefined
res4: Boolean = false

scala> op.get
java.util.NoSuchElementException: None.get
  at scala.None$.get(Option.scala:349)
  at scala.None$.get(Option.scala:347)
  ... 39 elided

scala> op.getOrElse(42)
res7: Int = 42

scala> op.getOrElse(throw new RuntimeException("except"))
java.lang.RuntimeException: except
  at .$anonfun$res8$1(<console>:13)
  at scala.Option.getOrElse(Option.scala:121)
  ... 39 elided

scala> op match {
     | case Some(x) => x
     | case None => 42
     | }
res9: Int = 42

scala> val x = Option(42)
x: Option[Int] = Some(42)

scala> x.filter(_ < 43)
res34: Option[Int] = Some(42)

scala> x.filter(_ > 43)
res35: Option[Int] = None

scala> x ++ Option(84)
res36: Iterable[Int] = List(42, 84)

scala> x ++ None
res37: Iterable[Int] = List(42)

上記の通り、例えNoneであったとしてもgetメソッド以外の操作では例外を発する事はなく、単にNoneが返ってきたり値から除外されたりなど、統一的な記述ができるようになっている。連結もなんのそのである。尚、NoneなOptionに対してmap操作などを行うと、必ずNoneが返ってくる。

scala> val x:Option[Int] = Some(6)
x: Option[Int] = Some(6)

scala> x.map(_ * 7)
res23: Option[Int] = Some(42)

scala> val x:Option[Int] = None
x: Option[Int] = None

scala> x.map(_ * 7 )
res24: Option[Int] = None

scala> x.filter(_ >= 20)
res25: Option[Int] = None

getOrElseと同じようなものとしてfoldメソッドなどがある。

scala> Option[Int](7).fold(throw new RuntimeException){_ * 6}
res5: Int = 42

scala> val none:Option[Int] = None
none: Option[Int] = None

scala> none.fold(throw new RuntimeException){_ * 6}
java.lang.RuntimeException
  at .$anonfun$res6$1(<console>:13)
  at scala.Option.fold(Option.scala:158)
  ... 39 elided

あまり動きは以下と変わらない気がする。

scala> val f = (op:Option[Int]) => op.getOrElse(throw new RuntimeException) * 6
f: Option[Int] => Int = $$Lambda$1904/1963014637@729c62e9

scala> f(Some(7))
res2: Int = 42

scala> val none:Option[Int] = None
none: Option[Int] = None

scala> f(none)
java.lang.RuntimeException
  at .$anonfun$f$2(<console>:11)
  at scala.Option.getOrElse(Option.scala:121)
  at .$anonfun$f$1(<console>:11)
  at .$anonfun$f$1$adapted(<console>:11)
  ... 39 elided

containsメソッドを使うと、Optionの中身の値と比較することができる。この時中身がNoneであっても例外は投げられない。

scala> val x:Option[Int] = None
x: Option[Int] = None

scala> x.contains(42)
res16: Boolean = false

flatten系も健在である。

scala> (x map { v1 => y map { v2 => v1 + v2 }}).flatten
res2: Option[Int] = Some(13)

scala> x flatMap { v1 => y map { v2 => v1 + v2 }}
res4: Option[Int] = Some(13)

これらは、for式でリファクタリングできる。

scala> val a = Option(2)
a: Option[Int] = Some(2)

scala> val b = Option(3)
b: Option[Int] = Some(3)

scala> val c = Option(7)
c: Option[Int] = Some(7)

scala> for(i <- a; j <- b; k <-c )yield i * j * k
res2: Option[Int] = Some(42)

話は変わって、暗黙の型変換を定義することができるようだ。

scala> implicit def IntToString(arg:Int):String = arg.toString
<console>:11: warning: implicit conversion method IntToString should be enabled
by making the implicit value scala.language.implicitConversions visible.
This can be achieved by adding the import clause 'import scala.language.implicitConversions'
or by setting the compiler option -language:implicitConversions.
See the Scaladoc for value scala.language.implicitConversions for a discussion
why the feature should be explicitly enabled.
       implicit def IntToString(arg:Int):String = arg.toString
                    ^
IntToString: (arg: Int)String

暗黙の型変換を定義する際には、scala.language.implicitConversionsをimportすることが推奨されるようだ。まぁこれは、暗黙の型変換を定義していることを意図するためのimportだろう。それと、言語機能をimportさせることで言語そのもののをmodule likeにしたいという意味合いが込められているようだ。

scala> import scala.language.implicitConversions
<console>:11: warning: Unused import
       import scala.language.implicitConversions
                             ^
import scala.language.implicitConversions

scala> implicit def IntToString(arg:Int):String = arg.toString
IntToString: (arg: Int)String

scala> val x:String = 42
<console>:9: warning: Unused import
import scala.language.implicitConversions
                      ^
x: String = 42

暗黙の型変換が広く有用的に使われるのは、pimp my libraryと呼ばれる利用方法で、これは既存のクラスへメソッドを追加しているように見せかける。C++の型変換演算子をグローバルに定義したような感じだ。

scala> class ListSorted(x:List[Int]){
     | def concatSorted(y:List[Int]):List[Int] = (x:::y).sorted
     | }
defined class ListSorted

scala> implicit def toListSorted(arg:List[Int]):ListSorted = new ListSorted(arg)
toListSorted: (arg: List[Int])ListSorted

scala> List(4,1,9).concatSorted(List(6,3,2))
res0: List[Int] = List(1, 2, 3, 4, 6, 9)

暗黙の変換は単にクラスの引数に値を渡してnewしているだけなのでやや冗長だ。これは以下のように書ける。

scala> implicit class ListSorted(x:List[Int]){
     | def concatSorted(y:List[Int]):List[Int] = (x:::y).sorted
     | }
defined class ListSorted

scala> List(4,1,9).concatSorted(List(6,3,2))
res2: List[Int] = List(1, 2, 3, 4, 6, 9)

Implicit parameterという機能もある。これは、カリー化されたメソッドの最後の引数にimplicitキーワードを付与する事で、その関数の呼び出しの最も直近なimplicitが付与された変数をメソッド呼び出しの際の束縛とし、呼び出しの際に明示的な変数の差し込みをなくす事ができる機能だ。

scala> class X(val i:Int){
     | final override def toString():String = i.toString
     | }
defined class X

scala> def f()(implicit x:X):X = x
f: ()(implicit x: X)X

scala> implicit val x = new X(42)
x: X = 42

scala> f()
res0: X = 42

scala> f()(new X(53))
res2: X = 53

勿論上記の通り、明示的にもオブジェクトを渡す事ができる。

一通り文法は把握したはずなので、最後に、S-99: Ninety-Nine Scala Problemsが練習として良さそうだったので順に解いてみる。取り敢えず本エントリでは基本的なリスト操作までを書いてみるとする。
P01

scala> def last[T](lst:List[T]):T = {
     | lst match{
     | case tail::Nil => tail
     | case _::tail => last(tail)
     | case _ => throw new NoSuchElementException
     | }
     | }
last: [T](lst: List[T])T

scala> last((1 to 42).toList)
res0: Int = 42

P02

scala> def last_two[T](lst:List[T]):T = {
     | lst match{
     | case target::_::Nil => target
     | case _::tail => last_two(tail)
     | case _ => throw new NoSuchElementException
     | }
     | }
last_two: [T](lst: List[T])T

scala> last_two((1 to 42).toList)
res3: Int = 41

P03

scala> def nth[T](n:Int,lst:List[T]):T = (n,lst) match {
     | case (0,h::_) => h
     | case (n,_::tail) => nth(n-1,tail)
     | case _ => throw new IndexOutOfBoundsException
     | }
nth: [T](n: Int, lst: List[T])T

scala> val smplst = (1 to 42).toList
smplst: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42)

scala> nth(smplst.length - 1,smplst)
res1: Int = 42

scala> nth(smplst.length,smplst)
java.lang.IndexOutOfBoundsException
  at .nth(<console>:15)
  ... 29 elided

P04

scala> def size[T](lst:List[T]):Int = lst.foldLeft(0){(c,_) => c + 1 }
size: [T](lst: List[T])Int

scala> size((1 to 42).toList)
res0: Int = 42

P05

scala> def reverse[T](lst:List[T]):List[T] = lst.foldLeft(Nil:List[T])((a,b)=>b::a)
reverse: [T](lst: List[T])List[T]

scala> reverse((1 to 42).toList)
res0: List[Int] = List(42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1)

P06

scala> def is_palindrome[T](lst:List[T]):Boolean = lst == reverse(lst)
is_palindrome: [T](lst: List[T])Boolean

scala> is_palindrome( (1 to 42).toList ::: reverse((1 to 42).toList) )
res4: Boolean = true

scala> is_palindrome( (1 to 42).toList )
res5: Boolean = false

P07
この問題はflatMapを使う。flatMapは、mapされたものをflattenする機能である。

scala> List((1 to 5).toList,(1 to 5).toList) map { x => 42 +: x }
res6: List[List[Int]] = List(List(42, 1, 2, 3, 4, 5), List(42, 1, 2, 3, 4, 5))

scala> List((1 to 5).toList,(1 to 5).toList) flatMap { x => 42 +: x}
res7: List[Int] = List(42, 1, 2, 3, 4, 5, 42, 1, 2, 3, 4, 5)

これを使うと、この問題はとても楽に書けるだろう。

scala> def flat(lst:List[Any]):List[Any] = lst flatMap{
     | case x:List[_] => flat(x)
     | case x => List(x)
     | }
flat: (lst: List[Any])List[Any]

scala> val lst = List((1 to 5).toList,(1 to 3).toList,(1 to 4).toList)
lst: List[List[Int]] = List(List(1, 2, 3, 4, 5), List(1, 2, 3), List(1, 2, 3, 4))

scala> flat(lst)
res0: List[Any] = List(1, 2, 3, 4, 5, 1, 2, 3, 1, 2, 3, 4)

P08
この問題にはdropWhileサブコレクションを使う。dropWhileサブコレクションは、引数に記述される条件に合致するオブジェクトを排除する。尚、条件に合致しない要素が見つかった場合、そこから先はdropされない。

scala> val a = (1 to 10).filter(_ % 2 == 0).toList
a: List[Int] = List(2, 4, 6, 8, 10)

scala> val b = (1 to 10).filter(_ % 2 != 0).toList
b: List[Int] = List(1, 3, 5, 7, 9)

scala> (a ::: b ::: a).dropWhile(_ % 2 == 0)
res52: List[Int] = List(1, 3, 5, 7, 9, 2, 4, 6, 8, 10)

dropWhileの対となるサブコレクションとしてtakeWhileというサブコレクションもある。これは、引数に記述される条件に合致するオブジェクトのみに絞る。これも条件に合致しない要素に当たった瞬間に処理が止まる。

scala> (a ::: b ::: a).takeWhile(_ % 2 == 0)
res53: List[Int] = List(2, 4, 6, 8, 10)

これらに加えて、spanというサブコレクションも備えている。spanは条件に合致する集合とそうでない集合をそれぞれ一つの集合として分けて返す。spanも、条件に合致しないオブジェクトに当たった場合にその時点で処理が止まる。

scala> (a ::: b ::: a).span(_ % 2 == 0)
res56: (List[Int], List[Int]) = (List(2, 4, 6, 8, 10),List(1, 3, 5, 7, 9, 2, 4, 6, 8, 10))

これらを使えば、問題は以下のように解ける。

scala> def no_eleminate_duplicate(lst:List[Symbol]):List[Symbol] = lst match {
     | case Nil => Nil
     | case head::tail => head::no_eleminate_duplicate(tail.dropWhile(_ == head))
     | }
no_eleminate_duplicate: (lst: List[Symbol])List[Symbol]

scala> no_eleminate_duplicate( List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e) )
res0: List[Symbol] = List('a, 'b, 'c, 'a, 'd, 'e)

P09
まず書いてみたのは以下のような感じ。

scala> def pack_duplicate[T](lst:List[T]):List[Any] = { lst match {
     | case Nil => Nil
     | case head::tail => {
     | if(head == tail.head)
     | (List(head) ::: tail.takeWhile(_ == head)) :: pack_duplicate(tail.dropWhile(_ == head))
     | else
     | List(head) :: pack_duplicate(tail.dropWhile(_ == head))
     | }
     | case _ => throw new NoSuchElementException
     | }
     | }
pack_duplicate: [T](lst: List[T])List[Any]

scala> pack_duplicate( List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e) )
res0: List[Any] = List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))

この実装でも問題そのものは解決しているのだが、型がList[Any]な部分があまり宜しくないので、書き直した。

scala> def pack_duplicate[T](lst:List[T]):List[List[T]] = lst match {
     | case Nil => Nil
     | case x => {
     | val (packed,next) = x span{_ == lst.head}
     | if(next == Nil)List(packed)
     | else packed :: pack_duplicate(next)
     | }
     | }
pack_duplicate: [T](lst: List[T])List[List[T]]

scala> pack_duplicate( List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e) )
res0: List[List[Symbol]] = List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))

P10

scala> def run_length[T](lst:List[T]):List[(T,Int)] = pack_duplicate(lst) map { x => (x.head,x.length) }
run_length: [T](lst: List[T])List[(T, Int)]

scala> run_length( List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e) )
res1: List[(Symbol, Int)] = List(('a,4), ('b,1), ('c,2), ('a,2), ('d,1), ('e,4))

P11
この問題では、Eitherという型を使う。Eitherは指定した二つの型のどちらを入れる事ができる。型の指定には、Left、Rightメソッドを使う。C++ではstd::variantあたりに該当するだろうか。

scala> val e:Either[Int,List[Int]] = Left(42)
e: Either[Int,List[Int]] = Left(42)

scala> val e:Either[Int,List[Int]] = Right(List(42))
e: Either[Int,List[Int]] = Right(List(42))

これを使えば、問題は以下のように解ける。

scala> def run_length_mod[T](lst:List[T]):List[Either[T,(T,Int)]] = run_length(lst) map {
     | x => if(x._2 == 1)Left(x._1) else Right(x)
     | }
run_length_mod: [T](lst: List[T])List[Either[T,(T, Int)]]

scala> run_length_mod( List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e) )
res0: List[Either[Symbol,(Symbol, Int)]] = List(Right(('a,4)), Left('b), Right(('c,2)), Right(('a,2)), Left('d), Right(('e,4)))

P12

scala> def run_length_decode[T](lst:List[(Int,T)]):List[T] = lst flatMap{ x => List.fill(x._1)(x._2) }
run_length_decode: [T](lst: List[(Int, T)])List[T]

scala> run_length_decode( List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e)) )
res4: List[Symbol] = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)

P13

scala> def run_length[T](lst:List[T]):List[(T,Int)] = lst match {
     | case Nil => Nil
     | case x => val (packed,next) = x span { _ == lst.head }
     | (packed.head,packed.length) :: run_length(next)
     | }
run_length: [T](lst: List[T])List[(T, Int)]

scala> run_length( List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e) )
res5: List[(Symbol, Int)] = List(('a,4), ('b,1), ('c,2), ('a,2), ('d,1), ('e,4))

P14

scala> def make_duplicate[T](lst:List[T]):List[T] = lst match {
     | case Nil => Nil
     | case head::tail => (List.fill(2)(head)) ::: make_duplicate(tail)
     | }
make_duplicate: [T](lst: List[T])List[T]

scala> make_duplicate( List('a, 'b, 'c, 'c, 'd) )
res0: List[Symbol] = List('a, 'a, 'b, 'b, 'c, 'c, 'c, 'c, 'd, 'd)

P15

scala> def make_duplicate[T](i:Int,lst:List[T]):List[T] = lst match {
     | case Nil => Nil
     | case head::tail => (List.fill(i)(head)) ::: make_duplicate(i,tail)
     | }
make_duplicate: [T](i: Int, lst: List[T])List[T]

scala> make_duplicate( 3, List('a, 'b, 'c, 'c, 'd) )
res8: List[Symbol] = List('a, 'a, 'a, 'b, 'b, 'b, 'c, 'c, 'c, 'c, 'c, 'c, 'd, 'd, 'd)

P16

scala> def drop[T](target:Int,lst:List[T]):List[T] = (target,lst) match{
     | case (_,Nil) => Nil
     | case (1,_::tail) => tail
     | case (x,head::tail) => List(head) ::: drop(x-1,tail)
     | }
drop: [T](target: Int, lst: List[T])List[T]

scala> drop(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k) )
res0: List[Symbol] = List('a, 'b, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k)

zipWithIndexを使えば更に短く書ける。zipWithIndexはインデックス値とペアにした集合を返す。

scala> (1 to 10).zipWithIndex
res1: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((1,0), (2,1), (3,2), (4,3), (5,4), (6,5), (7,6), (8,7), (9,8), (10,9))

これを使って、指定されたインデックス値で除算しその結果が割り切れていないもののみを残す。

scala> def drop[T](target:Int,lst:List[T]):List[T] = lst.zipWithIndex filter {
     | x => ((x._2 + 1) % target) != 0
     | } map { _._1 }
drop: [T](target: Int, lst: List[T])List[T]

scala> drop( 3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k) )
res2: List[Symbol] = List('a, 'b, 'd, 'e, 'g, 'h, 'j, 'k)

P17 この問題は、take、dropメソッドを使うと簡単だ。take、dropはそれぞれ指定されたインデックス値までの値を取得、指定されたインデックス値まで捨てるメソッドである。

scala> val lst = (1 to 42).toList
lst: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42)

scala> lst.take(lst.length/2)
res6: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21)

scala> lst.drop(lst.length/2)
res7: List[Int] = List(22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42)

これらを使うと以下のように解ける。

scala> def split[T](target:Int,lst:List[T]):Either[List[T],(List[T],List[T])] = lst match {
     | case Nil => Left(Nil)
     | case x => Right((x.take(target),x.drop(target)))
     | }
split: [T](target: Int, lst: List[T])Either[List[T],(List[T], List[T])]

scala> split( 3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k ) )
res0: Either[List[Symbol],(List[Symbol], List[Symbol])] = Right((List('a, 'b, 'c),List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k)))

P18

scala> def slice[T](h:Int,t:Int,lst:List[T]):List[T] = lst match{
     | case Nil => Nil
     | case x => x.drop(h).take(t-h)
     | }
slice: [T](h: Int, t: Int, lst: List[T])List[T]

scala> slice( 3, 7, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k) )
res1: List[Symbol] = List('d, 'e, 'f, 'g)

P19

scala> def rotate[T](target:Int,lst:List[T]):List[T] = (target,lst) match {
     | case (_,Nil) => Nil
     | case (t,x) if t > 0 => x.drop(t) ::: x.take(t)
     | case (t,x) if t < 0 => x.drop(x.length+t) ::: x.take(x.length+t)
     | }
rotate: [T](target: Int, lst: List[T])List[T]

scala> rotate( 3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k) )
res0: List[Symbol] = List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k, 'a, 'b, 'c)

scala> rotate( -2, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k) )
res1: List[Symbol] = List('j, 'k, 'a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i)

P20
この問題はsplitAtを使うと容易に実装できる。splitAtは指定されたインデックス値で分割する。

scala> List(1,2,3).splitAt(2)
res2: (List[Int], List[Int]) = (List(1, 2),List(3))

これを使うと以下のように書ける。

scala> def removeAt[T](target:Int,lst:List[T]):(List[T],T) = lst.splitAt(target) match {
     | case (Nil,_) => throw new NoSuchElementException
     | case (_,Nil) => throw new NoSuchElementException
     | case (left,target::right) => (left ::: right,target)
     | }
removeAt: [T](target: Int, lst: List[T])(List[T], T)

scala> removeAt(1, List('a, 'b, 'c, 'd))
res11: (List[Symbol], Symbol) = (List('a, 'c, 'd),'b)

P21

scala> def insertAt[T](value:T,target:Int,lst:List[T]):List[T] = lst.splitAt(target) match {
     | case (Nil,_) => throw new NoSuchElementException
     | case (_,Nil) => throw new NoSuchElementException
     | case (left,target::right) => (left ::: List(value,target) ::: right)
     | }
insertAt: [T](value: T, target: Int, lst: List[T])List[T]

scala> insertAt('new, 1, List('a, 'b, 'c, 'd))
res14: List[Symbol] = List('a, 'new, 'b, 'c, 'd)

P22

scala> def range(head:Int,tail:Int):List[Int] = (head to tail).toList
range: (head: Int, tail: Int)List[Int]

scala> range(4,9)
res15: List[Int] = List(4, 5, 6, 7, 8, 9)

P23
乱数にはutil.Randomを使う。

scala> val rnd = new util.Random
rnd: scala.util.Random = scala.util.Random@10bb5dc9

scala> for(x <- 1 to 10)yield rnd.nextInt(10)
res28: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 9, 8, 7, 9, 1, 5, 0, 3, 5)

scala> def randomSelect[T](len:Int,lst:List[T]):List[T] = (len,lst,new util.Random) match {
     | case (x,l,_) if x >= l.length || l == Nil => Nil
     | case (x,l,rnd) => (for(i <- 0 until x)yield l.drop(rnd.nextInt(l.length-len)).take(1).head).toList
     | }
randomSelect: [T](len: Int, lst: List[T])List[T]

scala> randomSelect(3, List('a, 'b, 'c, 'd, 'f, 'g, 'h))
res3: List[Symbol] = List('c, 'b, 'd)

scala> randomSelect(4, List('a, 'b, 'c, 'd, 'f, 'g, 'h))
res4: List[Symbol] = List('b, 'c, 'c, 'a)

scala> randomSelect(5, List('a, 'b, 'c, 'd, 'f, 'g, 'h))
res5: List[Symbol] = List('a, 'b, 'a, 'b, 'a)

P24

scala> val lotto = (count:Int,max:Int) => randomSelect(count,List.range(1,max+1))
lotto: (Int, Int) => List[Int] = $$Lambda$1472/1152751947@774406ba

scala> lotto(6, 49)
res8: List[Int] = List(4, 36, 29, 11, 40, 9)

P25

scala> def removeAt[T](n:Int,lst:List[T]):(List[T],T) = lst.splitAt(n) match {
     | case (Nil,_) if n < 0 => throw new NoSuchElementException
     | case (_,Nil) => throw new NoSuchElementException
     | case (left,head::tail) => (left ::: tail,head)
     | }
removeAt: [T](n: Int, lst: List[T])(List[T], T)

scala> def randomSelect[T](n:Int,lst:List[T]):List[T] = (n,lst) match {
     | case (0,_) => List[T]()
     | case (_,Nil) => Nil
     | case (nm,l) => {
     | val index = (Math.random * l.length).toInt
     | val (short,item) = removeAt(index,l)
     | item :: randomSelect(nm-1,short)
     | }
     | }
randomSelect: [T](n: Int, lst: List[T])List[T]

scala> def randomPermute[T](lst:List[T]) = randomSelect(lst.length,lst)
randomPermute: [T](lst: List[T])List[T]

scala> randomPermute( List('a, 'b, 'c, 'd, 'e, 'f)
     | )
res0: List[Symbol] = List('f, 'b, 'a, 'd, 'e, 'c)

P26

scala> def combination[T](n:Int,lst:List[T]):List[List[T]] = (n,lst) match {
     | case (_,Nil) => Nil
     | case (0,_) => Nil
     | case (1,x) => lst.map(List(_))
     | case (nm,head::tail) => combination(nm-1,tail).map(head::_) ::: combination(nm,tail)
     | }
combination: [T](n: Int, lst: List[T])List[List[T]]

scala> combination( 3, List('a, 'b, 'c, 'd, 'e, 'f) )
res0: List[List[Symbol]] = List(List('a, 'b, 'c), List('a, 'b, 'd), List('a, 'b, 'e), List('a, 'b, 'f), List('a, 'c, 'd), List('a, 'c, 'e), List('a, 'c, 'f), List('a, 'd, 'e), List('a, 'd, 'f), List('a, 'e, 'f), List('b, 'c, 'd), List('b, 'c, 'e), List('b, 'c, 'f), List('b, 'd, 'e), List('b, 'd, 'f), List('b, 'e, 'f), List('c, 'd, 'e), List('c, 'd, 'f), List('c, 'e, 'f), List('d, 'e, 'f))

P27

scala> def group[T](left:List[Int],right:List[T]):List[List[List[T]]] = left match {
     | case Nil => Nil
     | case head :: tail => {
     | combination(head,right).foldLeft(List[List[List[T]]]()){
     | (lists,comb) => group(tail,(right diff comb)) match {
     | case Nil => lists ::: List(List(comb))
     | case other => lists ::: other.map(comb :: _ )
     | }
     | }
     | }
     | }
group: [T](left: List[Int], right: List[T])List[List[List[T]]]

scala> group(List(2, 2, 5), List("Aldo", "Beat", "Carla", "David", "Evi", "Flip", "Gary", "Hugo", "Ida"))
res9: List[List[List[String]]] = List(List(List(Aldo, Beat), List(Carla, David), List(Evi, Flip, Gary, Hugo, Ida)), List(List(Aldo, Beat), List(Carla, Evi), List(David, Flip, Gary, Hugo, Ida)), List(List(Aldo, Beat), List(Carla, Flip), List(David, Evi, Gary, Hugo, Ida)), List(List(Aldo, Beat), List(Carla, Gary), List(David, Evi, Flip, Hugo, Ida)), List(List(Aldo, Beat), List(Carla, Hugo), List(David, Evi, Flip, Gary, Ida)), List(List(Aldo, Beat), List(Carla, Ida), List(David, Evi, Flip, Gary, Hugo)), List(List(Aldo, Beat), List(David, Evi), List(Carla, Flip, Gary, Hugo, Ida)), List(List(Aldo, Beat), List(David, Flip), List(Carla, Evi, Gary, Hugo, Ida)), List(List(Aldo, Beat), List(David, Gary), List(Carla, Evi, Flip, Hugo, Ida)), List(List(Aldo, Beat), List(Dav...

この問題にはdiffを使っている。diffは排他的論理和的な処理で、双方の内一方だけが持つ要素を集合として返す。

scala> List.range(1,10) diff List.range(1,10).filter(_ % 2 == 0)
res12: List[Int] = List(1, 3, 5, 7, 9)

否定でフィルターをするfilterNotでも同じことができる。

scala> List.range(1,10) filterNot List.range(1,10).filter(_ % 2 == 0).contains
res24: List[Int] = List(1, 3, 5, 7, 9)

filterNotは条件としてpredicate functionを受け取るため、containsメソッドを使って指定された値を内包しているかどうかを返す関数を生成しそれを適用している。

scala> val has_value = List.range(1,10).filter(_ % 2 == 0).contains _
has_value: Any => Boolean = $$Lambda$1690/121969977@29463fba

scala> has_value(1)
res28: Boolean = false

scala> has_value(2)
res29: Boolean = true

P28

scala> def qsort[T](lst:List[T],pred:(T,T) => Boolean):List[T] = lst match {
     | case x if x.length <= 1 => x
     | case x => {
     | removeAt((Math.random * x.length).toInt,x) match {
     | case (other,pivot) => {
     | val empty = (List[T](),List[T]())
     | val (lesser,greater) = other.foldLeft(empty) {
     | (acc,ot) => acc match {
     | case (l1,l2) => pred(ot,pivot) match {
     | case true => (l1 ::: List(ot),l2)
     | case false => (l1,l2 ::: List(ot))
     | }
     | }
     | }
     | qsort(lesser,pred) ::: List(pivot) ::: qsort(greater,pred)
     | }
     | }
     | }
     | }
qsort: [T](lst: List[T], pred: (T, T) => Boolean)List[T]

scala> def lsort[T](lst:List[List[T]]) = qsort(lst,(x:List[T],y:List[T]) => x.length < y.length)
lsort: [T](lst: List[List[T]])List[List[T]]

scala> lsort(List(List('a, 'b, 'c), List('d, 'e), List('f, 'g, 'h), List('d, 'e), List('i, 'j, 'k, 'l), List('m, 'n), List('o)))
res0: List[List[Symbol]] = List(List('o), List('d, 'e), List('m, 'n), List('d, 'e), List('f, 'g, 'h), List('a, 'b, 'c), List('i, 'j, 'k, 'l))

総括

Scalaは楽しい。

— roκi (@530506) 2017年5月29日

後、書いている感じとしてはリスト操作では正にC++でのパラメータパックを利用した色々な事とやっている事はほぼ同じだな〜と。後はコップ本とかを買ってしっかり深く学習したい感じ。

k-meansクラスタリングで遊ぶ

k-meansがディスられていたので、取り敢えずどんなもんかと実装した。

exp:

#include<srook/k_means/k_means.hpp>

int main()
{ 
    srook::k_mns::k_means km("data",3);

//  km.set_initial_point(Point{2.0,90.0},Point{5.0,50.0}); // initial centerの独自設定も勿論可能
    km.clustering(); // 未設定の場合ベクトルの各min/max内で分布する乱数をinitial centerとする
    
    const char* result_file="result";
    std::ofstream ofs(result_file);
    ofs<<km;

    using namespace std::string_literals;

    srook::k_mns::ploter pl("output.png");
    std::string cmd="plot \""s+std::string(result_file)+"\" index 0,\"\" index 1,\"\" index 2";

    try{
        pl.output(cmd.c_str());
    }catch(const std::runtime_error& exp){
        std::cerr<<exp.what()<<std::endl;
    }
}

入力は,をデリミターとしたテキストデータから行う。出力はgnuplotで入力できる形式で吐き出す。

三つのclusteringの動作確認。initial centerはデータセットのx,yそれぞれのmin,max内で分布される値にしてるけど、割りとよく分類できてるような。 pic.twitter.com/dXSnII5VK8

— roκi (@530506) 2017年5月22日

折角なので、ミッxーマxスのシルエットのようなデータセットを与えて見る事にした。まずは、データセットを作成し、画像として出力しておく。

python3 random_circle.py
gnuplot -e "set terminal png; set output \"test.png\"; set datafile separator \",\"; plot \"mouse_data\" index 0"

さて、このデータセットのクラスタリングを行った結果、以下のようになった。

あー、確かに似たような出力になった。データセット：https://t.co/51NPJjfBnh pic.twitter.com/Aged2dtDX1

— roκi (@530506) 2017年5月23日

まぁこんなものだろう。このデータセットでは、initial centerやプロットの精度を上げても特に結果として大きな変化はなかった。まぁこのデータセットで考えればそうだろう。
一応、遊べるように、リポジトリを作ってある。 github.com また、お手軽に試せるように、gistにフルコードをアップロードしてある。 尚この機能は、SrookCppLibraries からも利用する事ができる。