はじめに:10時間の死闘の末に
Codewarsというサイト(Dojo, Kataなど道場インスピレーション)の、
- 8kyu(8級。最も簡単)
- clever(天才的な回答)
で学んだ話です。
経緯は前の記事にあります。
簡単に言うと、このコードが機能する理由を理解したい。
※注意!! 新しい記事のほうがきれいに書かれてます!!
module CheckFactor where
checkForFactor :: Int -> Int -> Bool
checkForFactor = (.) (== 0) . mod
因数かどうか調べる簡単なコードです。
問題
checkForFactor :: Int -> Int -> Bool
checkForFactor = (.) (== 0) . mod
-- 見やすい形に変換。hhは2引数関数であるの意。
f :: Int -> Int -> Bool
f = (.) g . hh -- 理解したい関数
解決方法
まず、最も簡単な答えを示しましょう。
f x y = g $ hh x y
これですね。異論は認めますが、おおよそこの形になるでしょう。
hh x y を先に計算し、gに入力します。
これを変換し、理解したい関数f = (.) g . hh
に近づけていきましょう。
関数合成の定義
まずは、関数合成の定義を学びましょう。
-- 関数合成の定義
(.) :: (b -> c) -> (a -> b) -> a -> c
-- 使い方の例
(.) funcA funcB = funcC
funcA . funcB = funcC
(.)
= 関数合成は、
- "aに対しbを返す関数"と
- "bに対しcを返す関数"を合成し
- "aに対しcを返す関数"を出力する。
もしくは、さらに値aを受け取り、値cを出力する。
この辺りは# Haskellの関数合成、または (.) 関数の「関数合成」の章までを読むのがわかりやすいと思います。
関数合成にしてみる
f x y = g $ hh x y -- 解1
f x y = (.) g (hh x) y -- 解2
f x y = (g . (hh x)) y -- 解3
解1は、先ほども出た最も簡単な答えですね。hh x y を先に計算し、gに入力します。
解2は、関数合成にしてみた形です。
hh x
となっているのは、1引数関数にしないと、関数合成の定義上、関数合成ができないため。
なぜこのやり方で1引数関数になるのか(1引数関数が出力されるのか)は複数の引数の渡し方(カリー化、部分適用について)で学びました。
解3は、.
を中置関数として使ってみた形ですね。上の式と等価です。
引数を減らしていく
f x= g . h x
f = g . h
この2つの式は等価です。
では、先ほどの式をよく見てみましょう。
f x y = (.) g (hh x) y
f x = (.) g (hh x)
f x y = (g . (hh x)) y
f x = g . (hh x)
それぞれ、下の形に変換できます。
これで引数を1つ減らせましたね。
ここから鬼ハードモード
※注意!! 新しい記事のほうがきれいに書かれてます!!
この調子で引数x
も減らせたらいいんですが……ここからが鬼門。
まずは、改めて定義をしましょう。
アルファベットだとややこしいのでひらがなで。
(== 0) :: Int -> Bool
g :: Int -> Bool
mod :: Int -> Int -> Int
hh :: Int -> Int -> Int
checkForFactor :: Int -> Int -> Bool
f :: Int -> Int -> Bool
checkForFactor = (.) (== 0) . mod
f = (.) g . hh
次に、(.)g
について考えてみます。関数合成は、本来2つの関数を必要としますが…
-- 関数合成の定義より
(.) = (b -> c) -> (a -> b) -> a -> c
-- (.) g は、gの定義より
(b -> c) = (Int -> Bool)
-- よって
b = Int
c = Bool
-- よって
(.) g = (Int -> Bool) -> (a -> Int) -> a -> Bool
よって、a -> Int
の関数と組み合わさる、a -> Bool
という関数に変換できました!
これが部分適用のはず。
次に、(.) g . hh
について考えてみます。
-- 関数合成の定義より
. = (b -> c) -> (a -> b) -> a -> c
-- (.) g と、hhの定義より
(.) g . hh = (Int -> Bool) -> ((Int -> Int) -> Int) -> (Int -> Int) -> Bool
これで、Int を2つ引数として取る、Boolを返す関数ができましたね!
……だいぶ雑だったので少しだけ細くすると、
Int -> Int -> Int
のカッコ(関数とみなした)部分が((Int -> Int) -> Int)
なのは、
(.) g
の時に、「a -> Int
の関数と組み合わさる、a -> Bool
という関数」という条件だったためです。a
が(Int -> Int)
だとしたわけですね。
それでいいの!?と思う部分もありましたが、動くのでそういうことでしょう。
終わりに
身も心も疲れ果てながら記事を書き、どうしても雑になってしまったなあと思いますが、これが限界ですはい。
ご質問あればコメントにお願いします。気力十分な私が対応するでしょう。1週間くらいは。
とはいえ、理解できた(と思っている)のは非常に満足!Codewars 8kyuでここまで学べるとは。
しつこいようですが新しい記事あります。この記事より良いものです。ぜひ。