こちらの記事で関数型プログラミングとやらが紹介されており、
すごーく面白そうだったので、自分なりに噛み砕いてみる。
また、某サイトの問題で、自分なりの関数型プログラミングを試してみた。
それ全然関数型じゃないよねって思われた場合、是非是非指摘を頂きたい。
関数型プログラミングの考え方
すでに【脱アルゴリズム宣言】シリーズで述べたように、関数型パラダイムは、まず最初にデータをまるごと用意し、そこに関数操作を加えていくという宣言をするという思考・指向でした。
上記一文と記事を見るに、まずはデータ、次に操作という
データ 操作 操作 操作
といった流れを意識すればよいのだろうか。
0から9までの数をすべて足す
$sum = 0;
for ($i = 0: $i < 10; $i++) {
$sum = $sum + $i;
}
echo $sum;
$nums = range(0, 9); //データのまとまりを用意する
echo array_sum($nums); //操作する
以下の例も同じように思えるが、$numsの値が変化している。
恐らく一度格納した変数の値を変更することは推奨されていないのでは？と思う。
特にPHPでは型の自動キャストがあるため、arrayからintへ変化しており、分かり辛い。
$nums = range(0, 9); //データのまとまりを用意する
$nums = array_sum($nums); //操作する
echo $nums;
だとすると、以下のような記述はありなのかな？変数多いけど。
$nums = range(0, 9); //データのまとまりを用意する
$sum = array_sum($nums); //操作する
echo $sum;
フローは不要
「0から9までの数をすべて足す」という問題内容には、「繰り返し」や「条件判断」といったフローは書かれていない
にも関わらず従来型では「for」（繰り返し）や「$i < 10」（条件判断）が出現している
（forは基本的に用いず、再起を使用するらしい）
問題の論理のみを記述する
$nums = range(0, 9); //0から9までの数
echo array_sum($nums); //~を全て足す（+ ~を出力する）
「0から9までの数」と「を全て足す」の2つだけで完結しており、バグの介入する余地が無い。
関数は論理の最小単位の部品
array_sumは「～を全て足す」という機能を持った関数である。
機能の論理は（これは標準関数だからアレだけど）、{}内で説明する。
手順を分割するな
$sum = 0;
for ($i = 0: $i < 10; $i++) {
$sum = $sum + $i;
}
echo $sum;
上記の例にあるような、$iや$sum といった状態変数は問題文には出てこない。
問題文はあくまで「0から9までの数をすべて足す」。
$sum = 0 + 1
$sum = 1 + 2
...
$sum = 36 + 9
上記の様な手順の分割はバグの温床になるため行わない。
論理を分割する
「0から9までの数をすべて足す」という問題の場合の論理は、
「0から9までの数」と「を全て足す」である。
つまり、
$nums = range(0, 9); //0から9までの数
echo array_sum($nums); //~を全て足す（+ ~を出力する）
こうなるのだ。
「まとまり」は美しい単一の論理構造
せっかく配列という「まとまり」にまるごと処理が出来る関数があるのに、繰り返し処理で「まとまり」を分解するな。
$nums = range(0, 9); //0から9までの数 array(0,1,2,3,4,5,6,7,8,9)
for ($i = 0: $i < 10; $i++) { // $i = 0, $i = 1...
...
結果の小出しは論理ではなく手順の分解だ。
高階関数すごい
PHPでいうところのarray_reduceとかarray_mapとか別の関数を取り扱うことの出来る関数超便利
例えば下記のようにまとまりの合計(array_sum)以外にも対応できるよう関数型を書き直した場合、
$nums = range(0, 9); //0から9までの数
echo array_reduce($nums, "sum"); //~を全て"○○"する（+ ~を出力する）
function sum($carry, $item) {
$carry += $item;
return $carry;
}
function minusSum($carry, $item) {
$carry -= $item;
return $carry;
}
上記のような形となる。
全てを引き算した合計を求めたい場合、array_reduce($nums, "sum")と記述されている箇所を、
array_reduce($nums, "minusSum")に変更すればいい。
論理を「全て足す」から「全て引く」へと変更するだけだ。なんて便利！
正直、現状ほとんど理解出来ていないので、従来のプログラミングとの違いがよく分かっていない。
forとかifとか使わないように、高階関数とか使うんだよね…？ぐらいの認識。
実際に問題を解いてみる
スペース区切りで与えられる2つの整数の合計を出力する
$input = explode(' ', trim(fgets(STDIN)));
$sum = 0;
foreach ($input as $i) {
$sum = $sum + $i;
}
echo $i;
$input = explode(' ', trim(fgets(STDIN))); //スペース区切りで与えられる2つの整数
echo array_sum($input); //~を全て足す
いくつか入力される数字を昇順に並び替えて出力する
while ($input = trim(fgets(STDIN))) {
$nums[] = $input;
}
sort($nums);
foreach ($nums as $num) {
echo $num . "\n";
}
$input = file('php://stdin', FILE_IGNORE_NEW_LINES | FILE_SKIP_EMPTY_LINES); //いくつかの数
sort($input); //~を全て昇順にソートする
echo implode("\n", $input); //~を全て出力する
スペース区切りで与えられる英単語列に含まれる英単語の出現回数を出現した順番に出力
$input = explode(' ', trim(file_get_contents('php://stdin')));
foreach (array_count_values($input) as $key => $value) {
echo $key . " " . $value . "\n";
}
$input = explode(' ', trim(file_get_contents('php://stdin'))); //~スペース区切りの英単語列
array_walk(array_count_values($input), function($value, $key) { //～を全て出現回数をカウント
echo $key . " " . $value . "\n";
});
echoで一つずつ出力しているのが少し気になる。
でも「～を全て順番に出力」の機能の論理と思えば普通かな。
後記
本当にこの理解で正しいのか分からないので、この連休にもっと勉強してゆきます。
問題も続きをやり次第どんどん更新していきます。
追記
これ、関数型で解ける気がしない…。誰かヘル－プ！！！！！！！！
$isSitting = array();
$preSitting = array();
list($seats, $group) = getStdin();
$isSitting = array_fill(1, $seats, null);
for ($i = 0; $i < $group; $i++) {
list($persons, $start) = getStdin();
$preSitting = $isSitting;
$goHome = false;
for ($j = 0; $j < $persons; $j++) {
$seat = $start + $j;
$seat = ($seat > $seats) ? ($seat - $seats) : ($seat);
if (isset($isSitting[$seat])) {
$goHome = true;
break;
}
$preSitting[$seat] = 1;
}
if ($goHome) continue;
$isSitting = $preSitting;
}
echo array_sum($isSitting);
function getStdin() {
return explode(' ', trim(fgets(STDIN)));
}
$input = file('php://stdin', FILE_IGNORE_NEW_LINES | FILE_IGNORE_NEW_LINES);
list($chairsCount, $groupsCount) = explode(' ', array_shift($input));
$callback = function($value) use ($chairsCount) {
list($peopleCount, $start) = explode(' ', $value);
return loopRange($start, $peopleCount, $chairsCount);
};
$groups = array_map($callback, $input); //来店したグループのまとまり
echo count(array_reduce($groups, function($carry, $item) { //無事に座席に着席出来ている人数
if (empty(array_intersect($carry, $item))) {
return $carry = array_merge($carry, $item);
}
return $carry;
}, array()));
function loopRange($start, $range, $chairsCount)
{
$end = $start + $range - 1;
$callback = function($value) use ($start, $end, $chairsCount) {
if ($end > $chairsCount) {
return (! ($value > $end - $chairsCount && $value < $start));
} else {
return ($value >= $start && $value <= $end);
}
};
$tmp = range(1, $chairsCount); //座席全体
return array_filter($tmp, $callback); //客が使用する予定の座席を返す
}
出来たには出来たけど保守性とは一体なんだったのか状態の上に
すごーーく従来型の方が読みやすい気がする。うーん何がまずかったのか。
参考
関数型プログラミングに目覚めた！IQ145で美少女JKの先輩から受けた特訓 5日間
Prog Blog From 憩い場所