関数型プログラミングをする際にどう考えてコードに落とすか？
もう数年関数型プログラミングを断続的に勉強し続けていますが、作れと言われれば作れるものの出来上がるコードが全然関数型じゃないばかりかスマートじゃありません。これはもうオブジェクト指向や手続き型に脳みそが浸食されていて、考え方の部分から関数型ではないのだろうなと思いました。
そこでTwitterで以下のようなつぶやきをしたところ反応してくださった方々がいましたので、紹介しつつ理解したいと思います。
自分の手続き型な回答
まずは、自分がC#で順列を順列を列挙するプログラムを組んでみました。
C#で関数型のことは考えずに素直に書いたつもりです。
ideone.com
Ideone.com - 6uPhHY - Online C# Compiler & Debugging Tool
考え方としては、[1, 2, 3, 4]の順列を作るには、まずは先頭の4つを先頭にしたリストを作りその先頭以外についての順列を再帰で求める、です。
・最初の呼び出し
[1] ++ 再帰 [2, 3, 4]
[2] ++ 再帰 [1, 3, 4]
[3] ++ 再帰 [1, 2, 4]
[4] ++ 再帰 [1, 2, 3]
・[1]についての再帰呼び出し
[1, 2] ++ 再帰 [3, 4]
[1, 3] ++ 再帰 [2, 4]
[1, 4] ++ 再帰 [2, 3]
・[1, 2]についての再帰呼び出し
[1, 2, 3] ++ 再帰 [4]
[1, 2, 4] ++ 再帰 [3]
と上記を繰り返すことにより順列が全て求まります。
先頭の4つと、それ以外のリストを作るのに破壊的代入とループを使ってしまっています。
手続き型での素直な実装になっていると思います。
では、他の方の関数型での回答を理解してみようと思います。
@TheorieDuDroit さんの回答
permutation.hs · GitHub
permutation.hs · GitHub
与えられたリストの順列を列挙する - Qiita
最後のqiitaに全部まとまっているので、それを読みます。
ふぇぇ
なんでいきなりこんなにシンプルなコードに落ちるのか…(すごい)
「巡回を使うヴァージョン」の方は言っていることはわかるけど、これを自分で思いつくにはどうしたら…
「順列を頭から構成していくヴァージョン（結果は辞書順）」は僕の考え方と同じですね。ですが、シンプル。きれい。
concatMap, 再帰, mapを使うとできるということをどうすれば自然に思いつけるのか。
「攪乱順列を構成する（ほんのすこし発展）」、すみません。お手上げです。時間があるときに実行しながら考えます。
@nobsun さんの1回目の回答
順列列挙関数（素朴な実装） - Qiita
続・順列列挙関数 - Qiita
これはわかりやすい！(「続・順列列挙関数」の方は難しい)
こんなに丁寧に書いてくださって感謝感謝です。
トップダウンで「型を考える」→「再帰の停止条件を考える」のですね。
まだ途中までしか読めてないのですが、@its_out_of_tune さんのHaskellでポーカーを作るブログ(Haskellでポーカーを作ろう〜第一回 リストのシャッフルとカードの定義〜 - Creatable a => a -> IO b)もこんな感じですね。(ちゃんと全部読もう)
これが自然にできるにはどうしたら？？？
数をこなすしかないのかな。読んでいる分にはわかるわかるなのですが、自分で書くときにこれができるかというと…
まとめ
お二人の回答を見ていて思いました。
「あたまのデキが違う」
は認めたくないので、下記の2点
「更にこれらのそれぞれをたとえば[a,b,c,d][b,c,d,a][c,d,a,b][d,a,b,c]といったように 巡回(circulate [a,b,c,d])させてやれば相異なった4*3!=4!個の順列が得られ、 」
とか、
「次に元が整列済（考えられる順列で最小のもの）という仮定のもとで，x:xsになっているとすれば，先頭が，最小の要素，次に小さいもの，その次に小さいもの，...というぐあいに生成して，最後に連結すればよさそ．」
とかが俺には自然に思いつかない。
これらってプログラミングや数学の基礎知識ですよね。それが俺にはない。プロのプログラマだけど。
僕がプログラムや数学を考えるときは、まず小さな具体例を考える。それから法則を見つけ出して式やプログラムを導く。ただし、ここで使用できるのは自分の知っている知識の範囲でのみ。さらに、数をこなして知識になっていれば具体例さえ思い浮かべずに式やプログラムに落とせるはず。
なので、まだまだまだまだ勉強が足りない。
もうひとつ、自分は今の仕事ではC#しかほとんど使っていないし、最近はExcel, Wordとの格闘が長くプログラムすらあまり組んでいない。勉強と言っても実際に組んでいる時間が取れないので読むだけに徹している状態。やはり、Haskellなどで実際に書く、という訓練が全然足りてないんだろうなぁと感じました。
@TheorieDuDroit さん、@nobsun さん、番外編で、@its_out_of_tune さんありがとうございました。
自分が何がわかっていないのかがわかってきたと思います。
