無駄と文化

実用的ブログ

Lazy_K で九九表のすべてのマスの和

Lazy_K λ計算

前回の記事で 九九表のすべてのマスの和を求める問題 をいろいろな言語で書きました。
記事の最後でそのうち Lazy_K でも書きます的な事を宣言しておいたんですが、この度そのコードが完成しましたのでご報告します。


Lazy_K って何？

純粋関数型言語の1つです、位置づけとしては ジョーク言語, 難解言語, ホビー言語 などに分類されるんじゃないでしょうか。

特徴としては言語に組み込まれたシンボルの少なさです。
Unlambda記法であれば、s, k, i, ` の4つのシンボルだけでチューリング完全な表現力を持っています。
Lazy_K の言語的なおもしろさは以下の記事を読んでいただければ(分かる人には)分かると思います。


マイナーな言語ですのでやってみようと思うと実行環境の準備からしなければいけないんですが、幸いなことにブラウザで実行できる REPL がありました。
上の窓に「プログラムの本体」、下の窓に「プログラムへの入力」を入力して実行することができます。


コードを書く

九九表のすべてのマスの和を求めるにあたってアルゴリズムの大筋は前回 JavaScript で書いたものと同じです。
引用します。

// range(1, 9) の代わり
const ns = [...Array(9).keys()].map(i => i+1);

// flatten() の代わり
const flatten = arr => [].concat(...arr);

// sum() の代わり
const sum = ns => ns.reduce((i, j) => i+j, 0);

let result = sum(flatten(ns.map((i, _, ms) => ms.map(j => i*j))));
console.log(result);
// => 2025

数列を組み立てて、直積を求め、flatten して、sum を取る。これです。


ちなみに前回、こんなことを愚痴っていましたが、

Array.range() も Array.flatten() も Set.product() も Math.sum() も無いとかさすがにツラいです。

はい、実は Lazy_K にもこれらの関数はありません。
それどころか自然数も積も和も if then else などの制御構文も一切ありません。唯一あるのは関数適用だけです。

なので何もかも自分で作らないといけませんね。まいったまいった。


下準備

いくら Lazy_K がチューリング完全とはいえ、そのままでは人間がプログラムを書くのはツラすぎます。せめて λ抽象 があれば、という感じです。
なので Lazy_K に λ抽象 のシンタックスを追加して、それを Lazy_K のコードに変換するトランスレータを書きました。

github.com

これです。

このツールの使い方については Qiita に記事を上げておきました。

qiita.com


正直、このツールを作るのにもガッツリ Haskell 書いてるので下準備どころではないですが。


今度こそコードを書く

さて必要なパーツを淡々と作っていきます。
基本的には λ抽象 を含むコードを書いていきますが、純粋な Lazy_K のコードも適宜 見せていきます。

真理値

TRUE  = ^xy.x
# => k

FALSE = ^xy.y
# => `ki

IF    = ^BOOL THEN ELSE.``BOOL THEN ELSE
# => i


NOT = ^x.``xFALSE TRUE
# => ``s``si`k`ki`kk

AND = ^xy.``xyFALSE
# => ``ss`k`k`ki

OR  = ^xy.``xTRUEy
# => ``si`kk

ペア・リスト

複数のデータを保持するのには連鎖リストを使います。

CONS = ^xyf.``fxy
# => ``s``s`ks``s`kk``s`ks``s`k`sik`kk

CAR  = ^x.`xTRUE
# => ``si`kk

CDR  = ^x.`xFALSE
# => ``si`k`ki


NULL   = FALSE
# => `ki

ISNULL = ^x.``x^_ _ _.FALSE TRUE
# => ``s``si`k`k`k`k`ki`kk

不動点コンビネータ

再帰的関数を定義するために無名再帰が必要です。無名再帰のためには不動点コンビネータですよね。
今回はハスケル・カリー先生のYコンビネータを使います。

Y = ^f.`^x.`f`xx^x.`f`xx
# => ``s``s``s`ksk`k``sii``s``s`ksk`k``sii

自然数

自然数はチャーチ数として表現します。

0   = ^fx.x
# => `ki

1   = ^fx.`fx
# => i

2   = ^fx.`f`fx
# => ``s``s`kski

3   = ^fx.`f`f`fx
# => ``s``s`ksk``s``s`kski

4   = ```sii2
# => ```sii``s``s`kski

256 = ```sii4
# => ```sii```sii``s``s`kski

各種演算も定義しておかなければいけません。
商 DIV と余剰 MOD の定義には再帰を使います。先ほどのYコンビネータの出番です。

ISZERO = ^n.``n^_.FALSE TRUE
# => ``s``si`k`k`ki`kk


GTE = ^mn.`ISZERO``SUBnm           # 大なりイコール
# => ``s`k`s`k``s``si`k`k`ki`kk``s`k`s``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks`
     `s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kikk

GT  = ^mn.``AND `ISZERO``SUBnm `NOT `ISZERO``SUBmn
                                   # 大なり
# => ``s``s`ks``s`k`s`k``ss`k`k`ki``s`k`s`k``s``si`k`k`ki`kk``s`k`s``s`k`s``si`k
     ``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s
     `k`s`kk``s`k`sik`k`kk`k`k`kikk``s`k`s`k``s``si`k`ki`kk``s`k`s`k``s``si`k`k`
     ki`kk``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ks
     k`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kik

LTE = ^mn.`ISZERO``SUBmn           # 小なりイコール
# => ``s`k`s`k``s``si`k`k`ki`kk``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`
     ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kik

LT  = ^mn.``AND `ISZERO``SUBmn `NOT `ISZERO``SUBnm
                                   # 小なり
# => ``s``s`ks``s`k`s`k``ss`k`k`ki``s`k`s`k``s``si`k`k`ki`kk``s`k`s``si`k``s``s`
     ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk
     ``s`k`sik`k`kk`k`k`kik``s`k`s`k``s``si`k`ki`kk``s`k`s`k``s``si`k`k`ki`kk``s
     `k`s``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk
     `k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kikk

EQ = ^mn.``AND``GTEmn``LTEmn
                                   # イコール
# => ``s``s`ks``s`k`s`k``ss`k`k`ki``s`k`s`k``s``si`k`k`ki`kk``s`k`s``s`k`s``si`k
     ``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s
     `k`s`kk``s`k`sik`k`kk`k`k`kikk``s`k`s`k``s``si`k`k`ki`kk``s`k`s``si`k``s``s
     `ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`k
     k``s`k`sik`k`kk`k`k`kik


SUCC = ^n.^fx.`f``nfx             # 後者関数
# => `s``s`ksk


PLUS = ^mn.^fx.``mf``nfx          # 和
# => ``s`ks``s`k`s`ks`s`kk

MULT = ^mn.^f.`m`nf               # 積
# => ``s`ksk

POW  = ^mn.`nm                    # 累乗
# => ``s`k`sik


PRED = ^nfx.```n^gh.`h`gf^u.x^u.u # 前者関数
# => ``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s
     `k`s`kk``s`k`sik`k`kk`k`k`ki

SUB  = ^mn.``nPREDm               # 差
# => ``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``
     s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kik

DIV = `Y^DIV.^mn.```IF``LTmn 0 `SUCC ``DIV ``SUBmn n
                                  # 商
# => ```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks``s``s`ks``s`k`s`ki``s``
     s`ks``s`k`s`k``ss`k`k`ki``s`k`s`k``s``si`k`k`ki`kk``s`k`s``si`k``s``s`ks``s
     `k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k
     `sik`k`kk`k`k`kik``s`k`s`k``s``si`k`ki`kk``s`k`s`k``s``si`k`k`ki`kk``s`k`s`
     `s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s
     `k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kikk`k`k`ki``s`k`s`k`s`k`s``s`ksk``s`
     `s`ks``s`k`s`ks``s``s`ks``s`kk``s`ksk`k``s`k`s``si`k``s``s`ks``s`k`s`ks``s`
     `s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k
     `k`kik`k`ki

MOD = `Y^MOD.^mn.```IF``LTmn m ``MOD ``SUBmn n
                                  # 余剰
# => ```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks``s``s`ks``s`k`s`ki``s``
     s`ks``s`k`s`k``ss`k`k`ki``s`k`s`k``s``si`k`k`ki`kk``s`k`s``si`k``s``s`ks``s
     `k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k
     `sik`k`kk`k`k`kik``s`k`s`k``s``si`k`ki`kk``s`k`s`k``s``si`k`k`ki`kk``s`k`s`
     `s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s
     `k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kikkk``s``s`ks``s`k`s`ks``s``s`ks``s`
     kk``s`ksk`k``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s
     ``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kik`k`ki

自然数の表示

自然数を扱えるようになりましたが、文字列に変換しなければ表示ができません。
自然数を文字列に変換する TOSTRING 関数を定義します。
出力ストリームの終端を表す EOF という値も定義しておきます。

TOSTRING_ = `Y^TOSTRING_.^n.``CONS ``PLUS 48 ``MODn10 ```IF ``LTEn9 NULL `TOSTRING_``DIVn10
# => ```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`k``s``s`ks``s`kk``s`ks``s`
     k`sik`kk``s`k```s`ks``s`k`s`ks`s`kk````s`ks``s`k`s`ks`s`kk````s`ksk```sii``
     s``s`kski````s`ksk``s``s`kski``s``s`ksk``s``s`ksk``s``s`ksk``s``s`kski```s`
     `s`ksk``s``s`kski``s``s`kski``s```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`
     s``s`ks``s``s`ks``s`k`s`ki``s``s`ks``s`k`s`k``ss`k`k`ki``s`k`s`k``s``si`k`k
     `ki`kk``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`k
     sk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kik``s`k`s`k``s``si`k`ki`kk``s
     `k`s`k``s``si`k`k`ki`kk``s`k`s``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`
     k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kikkk`
     `s``s`ks``s`k`s`ks``s``s`ks``s`kk``s`ksk`k``s`k`s``si`k``s``s`ks``s`k`s`ks`
     `s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`k
     k`k`k`kik`k`ki`k````s`ksk``s``s`kski``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ks
     ki``s`k`s``s``s`ki``s``s`k`s`k``s``si`k`k`ki`kk``s`k`s``si`k``s``s`ks``s`k`
     s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`si
     k`k`kk`k`k`kik`k```s``s`kski``s``s`ksk``s``s`kski`k`ki``s``s`ksk`k``s```s``
     s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks``s``s`ks``s`k`s`ki``s``s`ks``
     s`k`s`k``ss`k`k`ki``s`k`s`k``s``si`k`k`ki`kk``s`k`s``si`k``s``s`ks``s`k`s`k
     s``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k
     `kk`k`k`kik``s`k`s`k``s``si`k`ki`kk``s`k`s`k``s``si`k`k`ki`kk``s`k`s``s`k`s
     ``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k
     `si``s`k`s`kk``s`k`sik`k`kk`k`k`kikk`k`k`ki``s`k`s`k`s`k`s``s`ksk``s``s`ks`
     `s`k`s`ks``s``s`ks``s`kk``s`ksk`k``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks`
     `s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kik
     `k`ki`k````s`ksk``s``s`kski``s``s`ksk``s``s`ksk``s``s`ksk``s``s`kski

TOSTRING = ^n.``REVERSE_ EOF `TOSTRING_ n
# => ``s`k````s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks``s`k`s``s`ki``s``
     si`k`k`k`k`ki`kkk``s``s`ks``s`k`s`ks``s``s`ks``s`kk``s`ksk`k``s`k`s``s`k``s
     ``s`ks``s`kk``s`ks``s`k`sik`kk``si`kkk`k`k``si`k`ki```sii```sii``s``s`kski`
     ``s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`k``s``s`ks``s`kk``s`ks``s`k
     `sik`kk``s`k```s`ks``s`k`s`ks`s`kk````s`ks``s`k`s`ks`s`kk````s`ksk```sii``s
     ``s`kski````s`ksk``s``s`kski``s``s`ksk``s``s`ksk``s``s`ksk``s``s`kski```s``
     s`ksk``s``s`kski``s``s`kski``s```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s
     ``s`ks``s``s`ks``s`k`s`ki``s``s`ks``s`k`s`k``ss`k`k`ki``s`k`s`k``s``si`k`k`
     ki`kk``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ks
     k`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kik``s`k`s`k``s``si`k`ki`kk``s`
     k`s`k``s``si`k`k`ki`kk``s`k`s``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k
     `s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kikkk``
     s``s`ks``s`k`s`ks``s``s`ks``s`kk``s`ksk`k``s`k`s``si`k``s``s`ks``s`k`s`ks``
     s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk
     `k`k`kik`k`ki`k````s`ksk``s``s`kski``s``s`ksk``s``s`ksk``s``s`ksk``s``s`ksk
     i``s`k`s``s``s`ki``s``s`k`s`k``s``si`k`k`ki`kk``s`k`s``si`k``s``s`ks``s`k`s
     `ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik
     `k`kk`k`k`kik`k```s``s`kski``s``s`ksk``s``s`kski`k`ki``s``s`ksk`k``s```s``s
     ``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks``s``s`ks``s`k`s`ki``s``s`ks``s
     `k`s`k``ss`k`k`ki``s`k`s`k``s``si`k`k`ki`kk``s`k`s``si`k``s``s`ks``s`k`s`ks
     ``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`
     kk`k`k`kik``s`k`s`k``s``si`k`ki`kk``s`k`s`k``s``si`k`k`ki`kk``s`k`s``s`k`s`
     `si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`
     si``s`k`s`kk``s`k`sik`k`kk`k`k`kikk`k`k`ki``s`k`s`k`s`k`s``s`ksk``s``s`ks``
     s`k`s`ks``s``s`ks``s`kk``s`ksk`k``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``
     s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kik`
     k`ki`k````s`ksk``s``s`kski``s``s`ksk``s``s`ksk``s``s`ksk``s``s`kski

EOF = 256
# => ```sii```sii``s``s`kski

ISEOF = ^x.``EQx256
# => ``s``s``s`ks``s`k`s`k``ss`k`k`ki``s`k`s`k``s``si`k`k`ki`kk``s`k`s``s`k`s``s
     i`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si
     ``s`k`s`kk``s`k`sik`k`kk`k`k`kikk``s`k`s`k``s``si`k`k`ki`kk``s`k`s``si`k``s
     ``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`
     s`kk``s`k`sik`k`kk`k`k`kik`k```sii```sii``s``s`kski

リスト操作の高階関数

お馴染みの map や append, reverse などを定義します。もう少しです。

MAP = `Y^MAP.^f XS.```IF `ISNULL XS NULL ``CONS `f`CAR XS ``MAPf`CDR XS
# => ```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s`k`s``s``s`ki``s``si`k`k`k`k`k
     i`kk`k`ki``s`k`s``s`ks``s`k`s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ksk`
     k``si`kk``s``s`ks``s`k`s`ks`s`kk`k`k``si`k`ki

APPEND = `Y^APPEND.^XS YS.```IF `ISNULL XS YS ``CONS `CAR XS ``APPEND `CDR XS YS
# => ```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks``s`ki``s``si`k`k`k`k`ki
     `kk``s`k`s``s`ks``s`kk``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``si`kk``s``s`k
     sk`k``si`k`ki

REVERSE_ = `Y^REVERSE_.^ACC XS.```IF `ISNULL XS ACC ``REVERSE_ ``CONS `CAR XS ACC `CDR XS
# => ```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks``s`k`s``s`ki``s``si`k`k
     `k`k`ki`kkk``s``s`ks``s`k`s`ks``s``s`ks``s`kk``s`ksk`k``s`k`s``s`k``s``s`ks
     ``s`kk``s`ks``s`k`sik`kk``si`kkk`k`k``si`k`ki

REVERSE = `REVERSE_ NULL
# => ````s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks``s`k`s``s`ki``s``si`k`
     k`k`k`ki`kkk``s``s`ks``s`k`s`ks``s``s`ks``s`kk``s`ksk`k``s`k`s``s`k``s``s`k
     s``s`kk``s`ks``s`k`sik`kk``si`kkk`k`k``si`k`ki`ki

CONCAT = `Y^CONCAT.^XSS.```IF `ISNULL XSS NULL ``APPEND `CAR XSS `CONCAT `CDR XSS
# => ```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s``s`ki``s``si`k`k`k`k`ki`kk
     `k`ki``s`k`s``s`k```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks``s`ki`
     `s``si`k`k`k`k`ki`kk``s`k`s``s`ks``s`kk``s`k``s``s`ks``s`kk``s`ks``s`k`sik`
     kk``si`kk``s``s`ksk`k``si`k`ki``si`kk``s``s`ksk`k``si`k`ki

RANGE = `Y^RANGE.^n.``CONS n ```IF `ISZEROn NULL `RANGE`PREDn
# => ```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s``s`ks``s`kk``s`ks``s`k`sik
     `kk``s`k`s``s``s`ki``s``si`k`k`ki`kk`k`ki``s``s`ksk`k``s``s`ks``s`k`s`ks``s
     ``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`
     k`k`ki

SUM = `Y^SUM.^NS.```IF `ISNULL NS 0 ``PLUS `CAR NS `SUM `CDR NS
# => ```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s``s`ki``s``si`k`k`k`k`ki`kk
     `k`ki``s`k`s``s`k``s`ks``s`k`s`ks`s`kk``si`kk``s``s`ksk`k``si`k`ki

九九表のすべてのマスの和

お待たせしました、やっと本題です。

NUMS = ``MAP SUCC `RANGE 8
# => `````s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s`k`s``s``s`ki``s``si`k`k`k`k
     `ki`kk`k`ki``s`k`s``s`ks``s`k`s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ks
     k`k``si`kk``s``s`ks``s`k`s`ks`s`kk`k`k``si`k`ki`s``s`ksk````s``s``s`ksk`k``
     sii``s``s`ksk`k``sii``s`k`s``s``s`ks``s`kk``s`ks``s`k`sik`kk``s`k`s``s``s`k
     i``s``si`k`k`ki`kk`k`ki``s``s`ksk`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``
     s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`ki```s``s`ksk`
     `s``s`kski``s``s`kski

KUKU = `SUM `CONCAT ``MAP ^n.``MAP ^m.``MULT n m NUMS NUMS
# => ````s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s``s`ki``s``si`k`k`k`k`ki`k
     k`k`ki``s`k`s``s`k``s`ks``s`k`s`ks`s`kk``si`kk``s``s`ksk`k``si`k`ki````s``s
     ``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s``s`ki``s``si`k`k`k`k`ki`kk`k`ki``
     s`k`s``s`k```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks``s`ki``s``si`
     k`k`k`k`ki`kk``s`k`s``s`ks``s`kk``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``si`
     kk``s``s`ksk`k``si`k`ki``si`kk``s``s`ksk`k``si`k`ki`````s``s``s`ksk`k``sii`
     `s``s`ksk`k``sii``s`k`s`k`s``s``s`ki``s``si`k`k`k`k`ki`kk`k`ki``s`k`s``s`ks
     ``s`k`s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ksk`k``si`kk``s``s`ks``s`k
     `s`ks`s`kk`k`k``si`k`ki``s``s`k```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`
     s`k`s``s``s`ki``s``si`k`k`k`k`ki`kk`k`ki``s`k`s``s`ks``s`k`s`k``s``s`ks``s`
     kk``s`ks``s`k`sik`kk``s``s`ksk`k``si`kk``s``s`ks``s`k`s`ks`s`kk`k`k``si`k`k
     i``s`ksk`k`````s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s`k`s``s``s`ki``s``
     si`k`k`k`k`ki`kk`k`ki``s`k`s``s`ks``s`k`s`k``s``s`ks``s`kk``s`ks``s`k`sik`k
     k``s``s`ksk`k``si`kk``s``s`ks``s`k`s`ks`s`kk`k`k``si`k`ki`s``s`ksk````s``s`
     `s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s``s`ks``s`kk``s`ks``s`k`sik`kk``s`k
     `s``s``s`ki``s``si`k`k`ki`kk`k`ki``s``s`ksk`k``s``s`ks``s`k`s`ks``s``s`ks``
     s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`ki``
     `s``s`ksk``s``s`kski``s``s`kski`````s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`
     k`s`k`s``s``s`ki``s``si`k`k`k`k`ki`kk`k`ki``s`k`s``s`ks``s`k`s`k``s``s`ks``
     s`kk``s`ks``s`k`sik`kk``s``s`ksk`k``si`kk``s``s`ks``s`k`s`ks`s`kk`k`k``si`k
     `ki`s``s`ksk````s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s``s`ks``s`kk``
     s`ks``s`k`sik`kk``s`k`s``s``s`ki``s``si`k`k`ki`kk`k`ki``s``s`ksk`k``s``s`ks
     ``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``
     s`k`sik`k`kk`k`k`ki```s``s`ksk``s``s`kski``s``s`kski

MAIN = ^_.``APPEND `TOSTRING KUKU EOF
# => `k`````s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks``s`ki``s``si`k`k`k`
     k`ki`kk``s`k`s``s`ks``s`kk``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``si`kk``s`
     `s`ksk`k``si`k`ki```s`k````s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks
     ``s`k`s``s`ki``s``si`k`k`k`k`ki`kkk``s``s`ks``s`k`s`ks``s``s`ks``s`kk``s`ks
     k`k``s`k`s``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``si`kkk`k`k``si`k`ki```sii
     ```sii``s``s`kski```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`k``s``s`k
     s``s`kk``s`ks``s`k`sik`kk``s`k```s`ks``s`k`s`ks`s`kk````s`ks``s`k`s`ks`s`kk
     ````s`ksk```sii``s``s`kski````s`ksk``s``s`kski``s``s`ksk``s``s`ksk``s``s`ks
     k``s``s`kski```s``s`ksk``s``s`kski``s``s`kski``s```s``s``s`ksk`k``sii``s``s
     `ksk`k``sii``s`k`s``s`ks``s``s`ks``s`k`s`ki``s``s`ks``s`k`s`k``ss`k`k`ki``s
     `k`s`k``s``si`k`k`ki`kk``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks`
     `s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kik``s`k`s`k`
     `s``si`k`ki`kk``s`k`s`k``s``si`k`k`ki`kk``s`k`s``s`k`s``si`k``s``s`ks``s`k`
     s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`si
     k`k`kk`k`k`kikkk``s``s`ks``s`k`s`ks``s``s`ks``s`kk``s`ksk`k``s`k`s``si`k``s
     ``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`
     s`kk``s`k`sik`k`kk`k`k`kik`k`ki`k````s`ksk``s``s`kski``s``s`ksk``s``s`ksk``
     s``s`ksk``s``s`kski``s`k`s``s``s`ki``s``s`k`s`k``s``si`k`k`ki`kk``s`k`s``si
     `k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si`
     `s`k`s`kk``s`k`sik`k`kk`k`k`kik`k```s``s`kski``s``s`ksk``s``s`kski`k`ki``s`
     `s`ksk`k``s```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks``s``s`ks``s`
     k`s`ki``s``s`ks``s`k`s`k``ss`k`k`ki``s`k`s`k``s``si`k`k`ki`kk``s`k`s``si`k`
     `s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`
     k`s`kk``s`k`sik`k`kk`k`k`kik``s`k`s`k``s``si`k`ki`kk``s`k`s`k``s``si`k`k`ki
     `kk``s`k`s``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s`
     `s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kikk`k`k`ki``s`k`s`k`s`k`s
     ``s`ksk``s``s`ks``s`k`s`ks``s``s`ks``s`kk``s`ksk`k``s`k`s``si`k``s``s`ks``s
     `k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k
     `sik`k`kk`k`k`kik`k`ki`k````s`ksk``s``s`kski``s``s`ksk``s``s`ksk``s``s`ksk`
     `s``s`kski````s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s``s`ki``s``si`k`
     k`k`k`ki`kk`k`ki``s`k`s``s`k``s`ks``s`k`s`ks`s`kk``si`kk``s``s`ksk`k``si`k`
     ki````s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s``s`ki``s``si`k`k`k`k`ki
     `kk`k`ki``s`k`s``s`k```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks``s`
     ki``s``si`k`k`k`k`ki`kk``s`k`s``s`ks``s`kk``s`k``s``s`ks``s`kk``s`ks``s`k`s
     ik`kk``si`kk``s``s`ksk`k``si`k`ki``si`kk``s``s`ksk`k``si`k`ki`````s``s``s`k
     sk`k``sii``s``s`ksk`k``sii``s`k`s`k`s``s``s`ki``s``si`k`k`k`k`ki`kk`k`ki``s
     `k`s``s`ks``s`k`s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ksk`k``si`kk``s`
     `s`ks``s`k`s`ks`s`kk`k`k``si`k`ki``s``s`k```s``s``s`ksk`k``sii``s``s`ksk`k`
     `sii``s`k`s`k`s``s``s`ki``s``si`k`k`k`k`ki`kk`k`ki``s`k`s``s`ks``s`k`s`k``s
     ``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ksk`k``si`kk``s``s`ks``s`k`s`ks`s`kk`k
     `k``si`k`ki``s`ksk`k`````s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s`k`s``s`
     `s`ki``s``si`k`k`k`k`ki`kk`k`ki``s`k`s``s`ks``s`k`s`k``s``s`ks``s`kk``s`ks`
     `s`k`sik`kk``s``s`ksk`k``si`kk``s``s`ks``s`k`s`ks`s`kk`k`k``si`k`ki`s``s`ks
     k````s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s``s`ks``s`kk``s`ks``s`k`s
     ik`kk``s`k`s``s``s`ki``s``si`k`k`ki`kk`k`ki``s``s`ksk`k``s``s`ks``s`k`s`ks`
     `s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`k
     k`k`k`ki```s``s`ksk``s``s`kski``s``s`kski`````s``s``s`ksk`k``sii``s``s`ksk`
     k``sii``s`k`s`k`s``s``s`ki``s``si`k`k`k`k`ki`kk`k`ki``s`k`s``s`ks``s`k`s`k`
     `s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ksk`k``si`kk``s``s`ks``s`k`s`ks`s`kk
     `k`k``si`k`ki`s``s`ksk````s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s``s`
     ks``s`kk``s`ks``s`k`sik`kk``s`k`s``s``s`ki``s``si`k`k`ki`kk`k`ki``s``s`ksk`
     k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``
     s`k`s`kk``s`k`sik`k`kk`k`k`ki```s``s`ksk``s``s`kski``s``s`kski```sii```sii`
     `s``s`kski

実行する

この MAIN を変換したものを実行します。結果が表示されるまでに3分くらいかかりますけどね。

f:id:todays_mitsui:20161030123900p:plain

はい。


まとめ

Lazy_K を使うプロジェクトで人が足りなくなったらいつでも呼んでください。


私からは以上です。

九九表のすべてのマスの和

Haskell JavaScript Python PHP

takatoh 様 が同じ問題を Ruby と Scheme で解いてくださいました。許可を得て転記させていたいています。
Ruby 版の簡素さはさすがという感じです。そして、Scheme 版の S式 は慣れないと読めないし分からないのが面白いですね。takatoh 様、本当にありがとうございます。


f:id:todays_mitsui:20161012233845p:plain


小ネタです。九九表の81マスに書かれている全ての数を足し合わせる計算をやってみましょう。
いろんな言語で書きます。

意味？特に無いですね。


Python2

import itertools
print(sum(map(lambda (x, y): x*y, itertools.product(range(1, 10), repeat=2))))
# => 2025

実行結果

途中で直積を求める必要があるんですが、itertools を使えば一撃です。さすが。


PHP

<?php
$sum = 0;

foreach (range(1, 9) as $i) {
    foreach (range(1, 9) as $j) {
        $sum += $i*$j;
    }
}

echo $sum;
// => 2025

実行結果

もっと関数型っぽくして行圧縮したかったんですけど、PHP なので潔く PHP らしく。

PHP で直積計算 も出来るようですが、直積だけで20行使ってるのにオエッとなりました。
3引数以上にも対応した一般的な書き方だからですかねぇ。


Haskell

import Control.Applicative
main = putStrLn . show . sum $ (*) <$> [1..9] <*> [1..9]
-- => 2025

実行結果

私が最も愛する言語 Haskell です。

Applicative Functor が便利ですね。
(,) <$> xs <*> ys で直積が取れるし (*) <$> xs <*> ys で直積の生成をすっ飛ばして九九表の全てのマスの生成ができます。


JavaScript (ES2015)

console.log([].concat(...[...Array(9).keys()].map(i=>i+1).map((i,_,ns)=>ns.map(j=>i*j))).reduce((i,j)=>i+j,0))
// => 2025

実行結果

たぶん初見では読めないので適度に分解すると、

// range(1, 9) の代わり
const ns = [...Array(9).keys()].map(i => i+1);

// flatten() の代わり
const flatten = arr => [].concat(...arr);

// sum() の代わり
const sum = ns => ns.reduce((i, j) => i+j, 0);

let result = sum(flatten(ns.map((i, _, ms) => ms.map(j => i*j))));
console.log(result);
// => 2025

こうやってみると JavaScript 貧弱ですねぇ。個人的には好きなんですけど。

Array.range() も Array.flatten() も　Set.product() も Math.sum() も無いとかさすがにツラいです。
直積計算を Array.prototype.map() で無理やりやってるところがダサさポイントですね。


Lazy_K

`k`````s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks``s`ki``s``si`k`k`k`k`ki`
kk``s`k`s``s`ks``s`kk``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``si`kk``s``s`ksk`k``
si`k`ki```s`k````s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks``s`k`s``s`ki``
s``si`k`k`k`k`ki`kkk``s``s`ks``s`k`s`ks``s``s`ks``s`kk``s`ksk`k``s`k`s``s`k``s``
s`ks``s`kk``s`ks``s`k`sik`kk``si`kkk`k`k``si`k`ki```sii```sii``s``s`kski```s``s`
`s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``s`k
```s`ks``s`k`s`ks`s`kk````s`ks``s`k`s`ks`s`kk````s`ksk```sii``s``s`kski````s`ksk
``s``s`kski``s``s`ksk``s``s`ksk``s``s`ksk``s``s`kski```s``s`ksk``s``s`kski``s``s
`kski``s```s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s``s`ks``s``s`ks``s`k`s`ki``
s`k`s`k``s``si`k`k`ki`kk``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k
`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kik``s``s`ks``s``s`ks`
`s`k`s`ki``s`k`s`k``s``si`k`k`ki`kk``s`k`s``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s
`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kikk
`k`k`kik``s``s`ks``s`k`s`ks``s``s`ks``s`kk``s`ksk`k``s`k`s``si`k``s``s`ks``s`k`s
`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk
`k`k`kik`k`ki`k````s`ksk``s``s`kski``s``s`ksk``s``s`ksk``s``s`ksk``s``s`kski``s`
k`s``s``s`ki``s``s`k`s`k``s``si`k`k`ki`kk``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`
ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kik`k
```s``s`kski``s``s`ksk``s``s`kski`k`ki``s``s`ksk`k``s```s``s``s`ksk`k``sii``s``s
`ksk`k``sii``s`k`s``s`ks``s``s`ks``s`k`s`ki``s`k`s`k``s``si`k`k`ki`kk``s`k`s``si
`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`
s`kk``s`k`sik`k`kk`k`k`kik``s``s`ks``s``s`ks``s`k`s`ki``s`k`s`k``s``si`k`k`ki`kk
``s`k`s``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k
``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kikk`k`ki`k`k`ki``s`k`s`k`s`k`s``s`ksk`
`s``s`ks``s`k`s`ks``s``s`ks``s`kk``s`ksk`k``s`k`s``si`k``s``s`ks``s`k`s`ks``s``s
`ks``s`k`s`ks``s`k`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`kik`
k`ki`k````s`ksk``s``s`kski``s``s`ksk``s``s`ksk``s``s`ksk``s``s`kski````s``s``s`k
sk`k``sii``s``s`ksk`k``sii``s`k`s``s``s`ki``s``si`k`k`k`k`ki`kk`k`ki``s`k`s``s`k
``s`ks``s`k`s`ks`s`kk``si`kk``s``s`ksk`k``si`k`ki````s``s``s`ksk`k``sii``s``s`ks
k`k``sii``s`k`s``s``s`ki``s``si`k`k`k`k`ki`kk`k`ki``s`k`s``s`k```s``s``s`ksk`k``
sii``s``s`ksk`k``sii``s`k`s``s`ks``s`ki``s``si`k`k`k`k`ki`kk``s`k`s``s`ks``s`kk`
`s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``si`kk``s``s`ksk`k``si`k`ki``si`kk``s``s`k
sk`k``si`k`ki`````s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s`k`s``s``s`ki``s``si
`k`k`k`k`ki`kk`k`ki``s`k`s``s`ks``s`k`s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s
`ksk`k``si`kk``s``s`ks``s`k`s`ks`s`kk`k`k``si`k`ki``s``s`k```s``s``s`ksk`k``sii`
`s``s`ksk`k``sii``s`k`s`k`s``s``s`ki``s``si`k`k`k`k`ki`kk`k`ki``s`k`s``s`ks``s`k
`s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s`ksk`k``si`kk``s``s`ks``s`k`s`ks`s`kk
`k`k``si`k`ki``s`ksk`k`````s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s`k`s``s``s`
ki``s``si`k`k`k`k`ki`kk`k`ki``s`k`s``s`ks``s`k`s`k``s``s`ks``s`kk``s`ks``s`k`sik
`kk``s``s`ksk`k``si`kk``s``s`ks``s`k`s`ks`s`kk`k`k``si`k`ki`s``s`ksk````s``s``s`
ksk`k``sii``s``s`ksk`k``sii``s`k`s``s``s`ks``s`kk``s`ks``s`k`sik`kk``s`k`s``s``s
`ki``s``si`k`k`ki`kk`k`ki``s``s`ksk`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k
`s`kk``s``s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`ki```s``s`ksk``s``s`ks
ki``s``s`kski`````s``s``s`ksk`k``sii``s``s`ksk`k``sii``s`k`s`k`s``s``s`ki``s``si
`k`k`k`k`ki`kk`k`ki``s`k`s``s`ks``s`k`s`k``s``s`ks``s`kk``s`ks``s`k`sik`kk``s``s
`ksk`k``si`kk``s``s`ks``s`k`s`ks`s`kk`k`k``si`k`ki`s``s`ksk````s``s``s`ksk`k``si
i``s``s`ksk`k``sii``s`k`s``s``s`ks``s`kk``s`ks``s`k`sik`kk``s`k`s``s``s`ki``s``s
i`k`k`ki`kk`k`ki``s``s`ksk`k``s``s`ks``s`k`s`ks``s``s`ks``s`k`s`ks``s`k`s`kk``s`
`s`ksk`k``s`k`s`k`si``s`k`s`kk``s`k`sik`k`kk`k`k`ki```s``s`ksk``s``s`kski``s``s`
kski```sii```sii``s``s`kski

書きました！
Lazy K Playground で走らせてみたら結果を得るまでに150秒以上かかりました...。


Ruby

九九表のすべてのマスの和 | blog.PanicBlanket.com より転記。

# encoding: utf-8


def sum_of_kuku
  a = (1..9).to_a
  a.product(a).map{|x,y| x * y}.inject(:+)
end


puts sum_of_kuku

なるほど .inject(:+) のようなメソッド呼び出しで sum() が実現できるんですね。
.product() が標準で提供されているのも流石 Ruby といった感じ。


Scheme

九九表のすべてのマスの和 | blog.PanicBlanket.com より転記。

(use srfi-1)

(define direct-product
  (lambda (lis1 lis2)
    (append-map
      (lambda (x) (map (lambda (y) (list x y)) lis2))
      lis1)))


(define sum-of-kuku
  (lambda ()
    (let ((l1 '(1 2 3 4 5 6 7 8 9))
          (l2 '(1 2 3 4 5 6 7 8 9)))
      (apply + (map (lambda (x) (apply * x)) (direct-product l1 l2))))))


(print (sum-of-kuku))

読めない...。
(apply + (map (lambda (x) (apply * x)) (direct-product l1 l2))) のあたりが本題なんだろうなという感じはしますが、式が評価される様を頭でイメージできなければ、コードの解読も厳しい感じがしますね。


私からは以上です。

Python+OpenCV で顔検出 - OpenCV に付属の評価器を試す

Python OpenCV

f:id:todays_mitsui:20161003015838j:plain


画像の中から人の顔が写っている場所を自動的に判定する 顔検出 ってやつをやってみようと思います。

そのために OpenCV という有名なライブラリを使用します。OpenCV 自体は様々な言語と組み合わせて使うことが出来るのですが、今回は自分が書き慣れている Python でいきます。
幸いに Python は OpenCV が公式でサポートしている言語(C++, Python, Java)の一つですしね。


評価器を用意する

顔検出をするためには「画像のこの部分は、人の顔である/人の顔ではない」という判定をする 評価器 という部品が必要です。
この評価器は通常、事前に用意した何千枚というテスト画像をプログラムに読ませ、学習させて(機械学習というやつですね)作らなければいけません。

この機械学習で評価器を用意するという工程にとてつもない労力が掛かります。
人の顔が写ったたくさんの画像を用意して、画像の中の顔の部分を指定するなどの下準備が必要になるからです。

ところが、ありがたいことに OpenCV には標準で多くの種類の評価器が付属しています。
今回は OpenCV 標準の評価器を GitHub から落としてきて使おうと思います。

github.com

顔以外の評価器もあるようですが、今回使うのは以下の7つです。

  • haarcascade_frontalcatface.xml
  • haarcascade_frontalcatface_extended.xml
  • haarcascade_frontalface_alt.xml
  • haarcascade_frontalface_alt_tree.xml
  • haarcascade_frontalface_alt2.xml
  • haarcascade_frontalface_default.xml
  • haarcascade_profileface.xml

6つは正面顔(front face)用、1つは横顔(profile face)用です。


基本的な顔検出

シンプルに顔検出して顔の部分を枠で囲むだけならば、非常に少ないコード量で可能です。

import cv2


# 画像の読み込み
image = cv2.imread("img/src/01.jpg")

# 処理速度を高めるために画像をグレースケールに変換
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)

# 評価器を読み込み
cascade = cv2.CascadeClassifier("opencv/data/haarcascades/haarcascade_frontalcatface.xml")

# 顔検出
facerect = cascade.detectMultiScale(
    gray,
    scaleFactor=1.11,
    minNeighbors=3,
    minSize=(30, 30)
)

if 0 != len(facerect):
    BORDER_COLOR = (255, 255, 255) # 線色を白に
    for rect in facerect:
        # 顔検出した部分に枠を描画
        cv2.rectangle(
            image,
            tuple(rect[0:2]),
            tuple(rect[0:2] + rect[2:4]),
            BORDER_COLOR,
            thickness=2
        )

# 結果の画像を保存
cv2.imwrite("img/dest/detected.jpg", image)

import cv2 で読み込んでいるモジュールが OpenCV です。
簡単ですね。


精度を高める

顔検出が簡単に行えるのは分かりました。問題は精度です。
顔検出の間違いには2つのパターンがあります。

  • 第一の過誤 - 顔ではない対象を顔であると誤って検出する
  • 第二の過誤 - 顔である対象を顔であると正しく検出できない

今回は顔検出の際のパラメーターをいろいろに変えつつ、7つの評価器を比べてみます。


と言いつつ、比べてみるパラメーターは minNeighbors だけです。
minNeighbors は信頼度に関するパラメーターで、値を大きくすると第一の過誤のリスクを抑える代わりに第二の過誤のリスクが増します。つまり、何でもない部分を顔だと勘違いしづらくなる代わりに人の顔の部分も見落としやすくなるわけです。
今回は minNeighbors を 3, 10, 20 と変えてそれぞれの評価器の精度を比べてみます。


評価器毎の精度を比較する

信頼度=3 のとき

というわけでこちらをご覧ください。

minNeighbors=3 で各評価器を使って顔検出を走らせた結果です。
ものによっては枠が30個以上描かれて大変なことになってる画像もありますね。これは人の顔ではない対象を誤検出してしまっている状態です。


各評価器の精度を数字で比べましょう。
まずは第一の過誤の割合から。

f:id:todays_mitsui:20161003013209p:plain

f:id:todays_mitsui:20161003013225p:plain

全部で12枚の画像があり、1枚あたり2.4個の顔が写っています。精度の悪い評価器では1枚あたり19.6カ所もの誤検出があるようです。
その中で frontalface_alt2 と profileface の精度が良いですね。frontalface_alt2 は1枚あたりの誤検出が0.2カ所、非常に優秀です。


第二の過誤についても比べてみましょう。

f:id:todays_mitsui:20161003013846p:plain

f:id:todays_mitsui:20161003013249p:plain

はい、人の顔を検出できなかった割合は、全て横並びで7%という結果になりました。
とは言っても、さきほどの結果の画像を並べたページを見てもらえれば分かるとおり評価器によっては手当たり次第に枠がついている状態なので、まさに下手な鉄砲も数打ちゃ当たるの結果ですね。

信頼度のパラメーターをいじってもう少し比べてみましょう。


信頼度=10のとき

minNeighbors=10 で試して見ます。誤検出は減り、検出できない顔が増えるはずです。


第一の過誤

f:id:todays_mitsui:20161003013858p:plain

f:id:todays_mitsui:20161003013907p:plain

さすがに誤検出は1枚あたり7カ所ほどに減りましたね。
そして先ほど優秀だった frontalface_alt2, profileface がイマイチになり、今度は frontalface_default が優秀です。はて。


第二の過誤

f:id:todays_mitsui:20161003013917p:plain

f:id:todays_mitsui:20161003013932p:plain

続いて見落とし率ですが、信頼度を上げ慎重になった代わりに見落としが増えています。
軒並み4,5割は見落としてますね。これはいただけない。


信頼度=20のとき

もう少し試してみましょう minNeighbors=20 です。


第一の過誤

f:id:todays_mitsui:20161003013941p:plain

f:id:todays_mitsui:20161003013951p:plain

再び frontalface_alt2 が優秀です。驚異の誤検出0%。

第二の過誤

f:id:todays_mitsui:20161003013958p:plain

f:id:todays_mitsui:20161003014006p:plain

5割以上の顔を見落とすようになってしまいました。これ以上 信頼度を上げていっても期待はできないですね。


まとめ

というわけで比較の結果、評価器は frontalface_alt2 を使い minNeighbors=3 の設定で顔検出するのが最も精度を高めることができました。
この設定では人の顔が映った個所を見落とす確率は7%、そして1枚あたり約0.2カ所の誤検出があります。

今回特に検出しづらかったのは、この方のお顔です。

f:id:todays_mitsui:20161003014115j:plain

横顔ですし天地も逆になってますからねぇ。このお方の顔を検出するには画像を回転させながら評価器にかけるなどの工夫が必要そうです。


今回の比較のためのコード一式は下記のリポジトリに置いています。

github.com


また、その他のパラメーターによって顔検出の制度がどのように変わるかについても興味深いところですが、それについてはMakoto Koikeさんが書かれた下記の記事でよく研究されていましたので、興味のある方はそちらを参考にしてみてください。

http://workpiles.com/2015/04/opencv-detectmultiscale-scalefactor/

http://workpiles.com/2015/04/opencv-detectmultiscale-minneighbors/


私からは以上です。