概要
すごいH本読書会で、全くすごいH本を読み進めることなく、寄り道をしていました。とは言っても、すごいH本に関連した話題です。
要するに、すごいHな話題です。
きゃー!すごいH!!
ポイントフリースタイル
ポイントフリースタイル入門
Haskell にはポイントフリースタイルというのがあります。
例えば
haskell foo x = f (g x)
という中の x というのが「ポイント」と言うらしいです(型を明示していないから x の型が a->b だったりする可能性もあるけどその可能性は置いといて)。要するに値のことですね。
で、このポイントを除けてプログラミングするのをポイントフリースタイルと言います。
この場合、
haskell foo = f.g
となります。
とのことです。要するに、関数から関数作るときに変数なんてかかねーよ!ってスタイルのことです。たぶん。
以下、一応公式サイトを引用。
Pointfree Style
It is very common for functional programmers to write functions as a composition of other functions, never mentioning the actual arguments they will be applied to. For example, compare:
sum = foldr (+) 0
with:
sum' xs = foldr (+) 0 xs
These functions perform the same operation, however, the former is more compact, and is considered cleaner. This is closely related to function pipelines (and to unix shell scripting): it is clearer to write
let fn = f . g . h
than to writelet fn x = f (g (h x))
.
さて、これがどうすごいHに関わるかと言うと、前回の話題のうち、
filter
の述語で&&
を使うflip
を使った3引数関数への部分適用
での記述方法に関わってきます。詳細は後述。
コンビネータ
はてなキーワードさんによると、コンビネータとは自由変数を含まないλ式のことらしいです。せやな。SKIコンビネータとか有名ですよね。Lazy Kとかで有名ですよね。私は Lazy K の Hello World すら読めませんが。
SKIコンビネータについては、高階ことりちゃんと学ぶSKIコンビネータがわかりやすかったです。これを読んだの丸1年以上前なので、後で私も読み返しておきます
とりあえず例を見ましょう。以下、今回話に上がったコンビネータ。
Sコンビネータ
S x y z = x z (y z)
となるコンビネータです。3引数を取ります。Haskell ではap
*1とか<*>
*2で定義されているそうです。
Kコンビネータ
K x y = x
となるコンビネータです。2引数をとって1引数だけにしちゃいます。Haskll だとconst
になります。
Bコンビネータ
B x y z = x (y z)
となるコンビネータです。3引数を取ります。Haskell だと(.)
にあたります。
Cコンビネータ
C x y z = x z y
となるコンビネータです。3引数を取ります。Haskell だとflip
です。
Iコンビネータ
I x = x
となるコンビネータです。1引数を取ってそれをそのまま返します。Haskell だとid
というのがあるそうです。
コンビネータは他にも色々あるそうです。オレオレコンビネータを好きに定義するのも楽しいとのことです。
コンビネータは基本的に、引数を入れ替えたり消したりとか、コンビネーションな処理をしてくれる奴なんだと思います。
filter の述語で && でポイントフリー
前回、filter で && を使う際に、以下のとおり書きました。
filter (\x -> x < 15 && even x) [1..20]
それに対し、id:rst76*3 さんから以下のようにコメントをいただきました。
filterについては、import Control.Monadした上で、
haskell filter (ap ((&&) . (< 15)) even) [1..20]
とすれば動きます。
説明は別途。
説明していただきました。
目的は\x -> x < 15 && even x
の部分をもっと綺麗に(ポイントフリースタイルで)書きたいよねって感じです。
\x -> x < 15 && even x => ((< 15) x) && (even x) => (&&) ((< 15) x) (even x) => ((&&) ((< 15) x)) (even x) => ((&&) $ (< 15) x) (even x)) => (((&&).(< 15)) x) (even x)) => S ((&&).(< 15)) even x => ap ((&&).(< 15)) even x
となります。お見事!
3引数関数の flip でポイントフリー
前回私はlet flip31 f x y z = f y z x
とか定義して3引数目を先頭に持ってくるflip
を定義しましたが、これもポイントフリーでやってみようぜ、という話になりました。
Haskell はスケるよの3引数のflipという記事とほぼ同様のことかと思います。
1引数目と3引数目を入れ替えるflip
をA f x y z = f z y x
と定義してやってみました。
A f x y z = f z y x -- まず z を一番右端に! => flip f y z x => (flip f y) z x => flip (flip f y) x z -- 右端に行った! A f x y = flip (flip f y) x -- 次は y を右端に! => flip ((flip f) y) x => (flip ((flip f) y)) x => (flip $ (flip f) y) x => flip.(flip f) y x => flip (flip.flip f) x y -- x も y も出てきた!
つまり、A f
はflip (flip.flip f)
とかけるということになります。自力でデキる気が全くしない……。
さて、最後にf
も追い出してしまいましょう。
その前に、関数合成.
について一言補足です。.
も中置関数であるため、セクションにすることができます。(flip.)
と書けばflip
を.
に部分適用することができます。
余計な捕捉だったかもしれませんが、念のため。
A f = flip (flip.flip f) -- 最後に f を右端に! => flip (flip.(flip f)) => flip ((flip.)(flip f)) => flip ((flip.)(flip f)) => flip ((flip.) $ flip f) => flip (((flip.).flip) f) A = flip.(flip.).flip -- どうしてこうなった!!
最後らへん、ギブアップです。よくわかりません。
こうなのかな?
A f = flip $ ((flip.).flip) f => flip.((flip.).flip) f => flip.(flip.).flip f
でもこれ、
Prelude> let a = flip.((flip.).flip) Prelude> a f 1 2 3 [3,2,1] Prelude> let a = flip.(flip.).flip Prelude> a f 1 2 3 [3,2,1]
こう定義するとちゃんと動くけど、
Prelude> let a f = flip.((flip.).flip) f Prelude> a f 1 2 3 [2,1,3] Prelude> let a f = flip.(flip.).flip f Prelude> a f 1 2 3 <interactive>:150:3: Couldn't match type ‘[a2]’ with ‘b0 -> c’ Expected type: a2 -> a2 -> a2 -> b0 -> c Actual type: a2 -> a2 -> a2 -> [a2] Relevant bindings include it :: a2 -> c (bound at <interactive>:150:1) In the first argument of ‘a’, namely ‘f’ In the expression: a f 1 2 3
こう書くとちゃんと動かないんですよね。謎。 適用順序あたりが怪しいと思うんですがお手上げです。
助けて!すごいHな人!
scanl でフィボナッチ数列
Scan の理解度チェックということで、再度フィボナッチ数列です。
fibs = 1:scanl (+) 1 fibs
これを展開してみましょう。
- acc の初期値は
1
- fibs の1番目は
1
- fibs の2番目は
acc
の初期値 - fibs の3番目は
acc + fibsの1番目
- :
- :
要するに、すごく読みにくいですが、こうなります。
fibs = 1:acc の初期値:acc + fibs !! 1 ( = 次の acc):acc + fibs !! 2 ( = 次の acc):..
ホワイトボードに描いていただいた図がわかりやすいので、貼っておきます。
連続した四角で囲まれている数列がfibs
で、その下に丸で囲われた数字はacc
の値です。
fibs
の左に書いてある丸で囲われた数字はacc
の初期値です。
やはりフィボナッチ数列は深い……!
まとめ
括弧で括る -> $
で括弧を外す -> .
で関数合成 という手順はかなり使えそう。
ポイントフリースタイルへの道のりは険しい。