雀巽の日記帳

雀巽が綴る日常の記録

すごいH本読書会 〜ポイントフリースタイルへの道〜

概要

すごい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 write let fn x = f (g (h x)).

Pointfree - Haskell

さて、これがどうすごい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引数目を入れ替えるflipA 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 fflip (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):..

ホワイトボードに描いていただいた図がわかりやすいので、貼っておきます。

f:id:necojackarc:20150315034037j:plain

連続した四角で囲まれている数列がfibsで、その下に丸で囲われた数字はaccの値です。 fibsの左に書いてある丸で囲われた数字はaccの初期値です。

やはりフィボナッチ数列は深い……!

まとめ

括弧で括る -> $で括弧を外す -> .で関数合成 という手順はかなり使えそう。

ポイントフリースタイルへの道のりは険しい。

*1:Control.Monad

*2:Control.Applicative

*3:すごいH本読書会@渋谷某所における、実質講師役の素敵Haskeller