melpon日記 - HaskellもC++もまともに扱えないへたれのページ

2011-10-31

[]ポイントフリースタイル入門 10:27 ポイントフリースタイル入門を含むブックマーク

Haskell にはポイントフリースタイルというのがあります。

例えば

foo x = f (g x)

という中の x というのが「ポイント」と言うらしいです(型を明示していないから x の型が a->b だったりする可能性もあるけどその可能性は置いといて)。要するに値のことですね。

で、このポイントを除けてプログラミングするのをポイントフリースタイルと言います。

この場合、

foo = f.g

となります。


ということで、ありとあらゆるコードをポイントフリースタイルで書けるように訓練しましょう。

基本的に、書いてれば慣れるのでどんどん書きましょう。


基本

基本的に (.) 関数を使います。

foo x = f (g x)
foo x = (f.g) x
foo = f.g

です。


また、(.) は二項演算子なので、これを関数形式で書けば、

f.g
= (.) f g

となり、更に

= (f.) g
= (.g) f

と書くこともできます。

これは単に式を変形しただけなのですが、f (g x) の形式にするためにこれを結構使います。


あと、最初の例でもこっそりやっていますが、

foo x y = f x y

こんな関数があったとき、y は左と右で両方とも右端にあるので、取り除くことができます。

foo x = f x

で、さらに x も同様に取り除けます。

foo = f

こうなります。


これだけ知ってれば結構頑張れます。


問題1

ということでいくつか解きましょう。

foo x y = f (g x y)

まずは y を除けることから考えましょう。

g' = g x と考えれば簡単に分かります。

-- g x を g' とする
foo x y = f (g' y)
  where g' = g x

-- f (g x) の形になったので . に直す
foo x = f.g'
  where g' = g x

-- where の部分を取り除く
foo x = f.g x

となります。

次に x を除けましょう。

これは

foo x = (f.) (g x)

であると考えればすぐ分かります。

-- (f.) を f' とする
foo x = f' (g x)
  where f' = (f.)

-- f (g x) の形になったので . に直す
foo = f'.g
  where f' = (f.)

-- where の部分を取り除く
foo = (f.).g

こうなります。

つまり

foo x y = f (g x y)

をポイントフリーにすると

foo = (f.).g

になります。


問題2

もうひとつぐらいやっておきましょう。

foo x y z = f x (g y z)

z から取り除きます。

-- f x を f' に、g y を g' にする
foo x y z = f' (g' z)
  where f' = f x
        g' = g y

-- f (g x) の形になったので . に直す
foo x y = f'.g'
  where f' = f x
        g' = g y

-- where の部分を元に戻す
foo x y = f x.g y

次に y です。

-- 式を変形する
foo x y = (f x.) (g y)

-- (f x.) を f' とする
foo x y = f' (g y)
  where f' = (f x.)

-- . にする
foo x = f'.g
  where f' = (f x.)

-- where を戻す
foo x = (f x.).g

最後に x を除けます。これはちょっと強敵かもしれません。

-- (f x.) を f' とする
foo x = f'.g
  where f' = (f x.)

-- 式を変形する
foo x = (.g) f'
  where f' = (f x.)

-- (f x.) を式変形する
foo x = (.g) f'
  where f' = (.) (f x)

-- f' は引数を取るようにしてみましょう
foo x = (.g) (f' x)
  where f' x = (.) (f x)

-- f' が f (g x) の形になっているので . に直す
foo x = (.g) (f' x)
  where f' = (.).f

-- foo が f (g x) の形になっているので . に直す
foo = (.g).f'
  where f' = (.).f

-- where を戻す
foo = (.g).((.).f)

-- . 演算子は右結合なので無駄な括弧を取り除く
foo = (.g).(.).f

となります。


flip 登場

ドット関数さえあれば結構頑張れるのですが、

foo x y = f y x

みたいなのになると厳しいので、flip 関数を使うことにします。

foo x y = flip f x y

となり、

foo = flip f

になります。


問題3

flip を使って自由に引数の順番を入れ替えられるようになっているといい感じです。

foo x y z = f z y x
-- f を flip して z を後ろに移動させる
foo x y z = flip f y z x
-- flip f y を flip して z を後ろに移動させる
foo x y z = flip (flip f y) x z
-- z を取り除く
foo x y = flip (flip f y) x

-- flip f y を y' とする
foo x y = flip y' x
  where y' = flip f y
-- y' を後ろにやるために flip する
foo x y = flip flip x y'
  where y' = flip f y
-- where を戻す
foo x y = flip flip x (flip f y)
-- (flip flip x) を f' に、(flip f) を g' に置き換えると f' (g' y) になるので . に直せる
foo x = flip flip x.flip f
-- あとは普通にポイントフリーにする
foo x = (.flip f) (flip flip x)
foo = (.flip f).flip flip

頑張ってみた

練習として、4引数関数の順番を全パターン網羅してみました。

data A = A
data B = B
data C = C
data D = D

test :: A -> B -> C -> D -> a
test = undefined

test1 :: A -> B -> D -> C -> a
test1 = (flip.).test

test2 :: A -> C -> B -> D -> a
test2 = flip.test

test3 :: A -> C -> D -> B -> a
test3 = (flip.).flip.test

test4 :: A -> D -> B -> C -> a
test4 = (.flip flip).flip (.).test

test5 :: A -> D -> C -> B -> a
test5 = (.flip flip).flip (.).flip.test

test6 :: B -> A -> C -> D -> a
test6 = flip test

test7 :: B -> A -> D -> C -> a
test7 = (flip.).flip test

test8 :: B -> C -> A -> D -> a
test8 = flip.flip test

test9 :: B -> C -> D -> A -> a
test9 = (flip.).flip.flip test

test10 :: B -> D -> A -> C -> a
test10 = (.flip flip).flip (.).flip test

test11 :: B -> D -> C -> A -> a
test11 = (.flip flip).flip (.).flip.flip test

test12 :: C -> A -> B -> D -> a
test12 = (.test).flip flip

test13 :: C -> A -> D -> B -> a
test13 = (flip.).(.test).flip flip

test14 :: C -> B -> A -> D -> a
test14 = (.flip test).flip flip

test15 :: C -> B -> D -> A -> a
test15 = (flip.).(.flip test).flip flip

test16 :: C -> D -> A -> B -> a
test16 = (.flip flip).flip (.).(.test).flip flip

test17 :: C -> D -> B -> A -> a
test17 = (.flip flip).flip (.).(.flip test).flip flip

test18 :: D -> A -> B -> C -> a
test18 = (.test).(.).flip flip

test19 :: D -> A -> C -> B -> a
test19 = (.flip.test).(.).flip flip

test20 :: D -> B -> A -> C -> a
test20 = (.flip test).(.).flip flip

test21 :: D -> B -> C -> A -> a
test21 = (.flip.flip test).(.).flip flip

test22 :: D -> C -> A -> B -> a
test22 = (.(.test).flip flip).(.).flip flip

test23 :: D -> C -> B -> A -> a
test23 = (.(.flip test).flip flip).(.).flip flip

main = putStrLn ""

どれも半分機械になってひたすら変形しまくりました。

もっと綺麗に簡約できるのもあるのかもしれないですけど、機械的にやるとこんな感じです。


全部説明するのは辛いので、長い test17 だけ変形の様子を見てみましょう。

test17 :: C -> D -> B -> A -> a
test17 c d b a = test a b c d

-- a
test17 c d b a = flip test b a c d
test17 c d b a = flip (flip test b) c a d
test17 c d b a = flip (flip (flip test b) c) d a
test17 c d b = flip (flip (flip test b) c) d

-- b
test17 c d b = flip flip d (flip (flip test b) c)
test17 c d b = flip flip d (flip flip c (flip test b))

test17 c d b = f' (g' b)
  where f' = flip flip d
        g' b = flip flip c (flip test b)

test17 c d = f'.g'
  where f' = flip flip d
        g' = flip flip c.flip test

test17 c d = flip flip d.flip flip c.flip test

-- d
test17 c d = (.flip flip c.flip test) (flip flip d)
test17 c = (.flip flip c.flip test).flip flip

-- c
test17 c = (.flip flip) (.flip flip c.flip test)
test17 c = (.flip flip) (flip (.) (flip flip c.flip test))
test17 c = (.flip flip) (flip (.) ((.flip test) (flip flip c)))

test17 c = f' (g' c)
  where f' = (.flip flip)
        g' c = flip (.) ((.flip test) (flip flip c))

test17 c = f' (g' c)
  where f' = (.flip flip)
        g' c = f'' (g'' c)
          where f'' = flip (.)
                g'' c = (.flip test) (flip flip c)

test17 = f'.g'
  where f' = (.flip flip)
        g' = f''.g''
          where f'' = flip (.)
                g'' = (.flip test).flip flip

test17 = (.flip flip).flip (.).(.flip test).flip flip

となります。


まとめ

これだけ変形しておきながら、f や g といった関数の具体的な意味については一切言及してません。

つまりポイントフリーにするにあたって、関数の具体的な処理なんて知る必要はありません。

それぞれの関数の意味が分からなくても、とりあえずポイントフリーにすることはできます。

ということで頑張ってどんどんポイントさんを自由にしてあげましょう。


Q.なぜポイントフリースタイルで書くのですか?

A.そこにポイントがあるから