Haskellのフクロウ ((.)$(.))

 Haskellのポイントフリー記法により, いくつか新発見があったようなのですが, そのうちの一つがHaskellのフクロウ・コンビネータなのだそうで.

Pointfree - Haskell

 次のコンビネータがそれなのですが, たしかに見ようによってはフクロウの顔に見えなくもないです.

*Main> :t ((.)$(.))
((.)$(.)) :: (a -> b -> c) -> a -> (a1 -> b) -> a1 -> c

 で, 試しに型を見てみると次のような感じ.

*Main> :t ((.)$(.))
((.)$(.)) :: (a -> b -> c) -> a -> (a1 -> b) -> a1 -> c
*Main> :t ((.)(.))
((.)(.)) :: (a -> b -> c) -> a -> (a1 -> b) -> a1 -> c
*Main> :t (.)(.)
(.)(.) :: (a -> b -> c) -> a -> (a1 -> b) -> a1 -> c

 ドルマークはgroup expressionと呼ばれ, 括弧と同等のもので, $から行末, またはその前の閉じ括弧の一つ手前までを括弧でくくる演算子です. なので, フクロウコンビネータのドル記号は実は不要(あってもなくても意味は同じ)で, さらに, 外側を囲っている括弧も(上記の例では)不要(Haskellでは, applyの優先順位が一番高いため)なので, 最終的に「フクロウ」は「見下ろす目玉」まで簡略化できました. ドット記号は, 関数合成の演算子なので, これ以上小さくすることはできません.
 しかし, こんなコンビネータどこで使うんだと思っていたのですが, pointfulに書くと,

f a b c d = a b (c d)

なのだそうで, 意外と使えるかもしれないですね. mapでは引数を二つとりますが, たいてい, 二番目の引数は, ごちゃごちゃしていますから.

*Owl> ((.)$(.)) map (* 2) reverse [1..10]
[20,18,16,14,12,10,8,6,4,2]

のように使えます.

 フクロウ・コンビネータは意味的には((.)(.))の目玉二つに相当するわけですが目玉の数を増やすと様々なコンビネータが作れます.

((.))                   :: (b -> c) -> (a -> b) -> a -> c
((.)(.))                :: (a -> b -> c) -> a -> (a1 -> b) -> a1 -> c
((.)(.)(.))             :: (b -> c) -> (a -> a1 -> b) -> a -> a1 -> c
((.)(.)(.)(.))          :: (a -> a1 -> b -> c) -> a -> a1 -> (a2 -> b) -> a2 -> c
((.)(.)(.)(.)(.))       :: (b1 -> c) -> (b -> b1) -> (a -> b) -> a -> c
((.)(.)(.)(.)(.)(.))    :: (b -> b1 -> c) -> (a -> b) -> a -> (a1 -> b1) -> a1 -> c
((.)(.)(.)(.)(.)(.)(.)) :: (a -> b -> c) -> a -> (a1 -> a2 -> b) -> a1 -> a2 -> c
((.)(.)(.)(.)(.)(.)(.)(.)):: (b -> c) -> (a -> a1 -> a2 -> b) -> a -> a1 -> a2 -> c

目玉(合成関数)の数を増やしても, 生成される関数の型に一貫性がないように見えます.
 replで試してみると以下のようになります. 二番目はフクロウ・コンビネータの使い方と同じです.

*Owl> ((.)) reverse tail [1..10]
[10,9,8,7,6,5,4,3,2]
*Owl> ((.)(.)) map (* 2) reverse [1..10]
[20,18,16,14,12,10,8,6,4,2]
*Owl> ((.)(.)(.)) reverse map (* 2) [1..10]
[20,18,16,14,12,10,8,6,4,2]
*Owl> ((.)(.)(.)(.)) foldl (+) 0 tail [1..10]
54
*Owl> ((.)(.)(.)(.)(.)) reverse reverse reverse [1..10]
[10,9,8,7,6,5,4,3,2,1]
*Owl> ((.)(.)(.)(.)(.)(.)) map (+) 2 reverse [1..10]
[12,11,10,9,8,7,6,5,4,3]

 こんな感じで5つ「目」までは使えそうです. 使う関数の名前と組み合わせによっては, 括弧で直接囲うよりも見やすくなるかもしれません. とはいえ, 素直に書いた方が手っ取り早くて安全なのは言うまでもないですが.
 mapとfilterを繰り返し使いたい時と, foldlで組み合わせたい時は, 次のように書けます.

*Owl> ((.)$(.).(.)) map (+ 2) filter (< 3) [1..10]
[3,4]
*Owl> ((.)$(.)$(.).(.)) foldl (+) 0 map (* 3) [1..10]
165

ラムダ計算のYの使い方と不動点コンビネータの違い

1.YCombinatorの使い方

ハスケルのYコンビネータ
Y　≡　(λg. (λx. g(x x)) (λx. g(x x)))

は以下のように簡約されていき、

β→  (λg. (λx. g(x x)) (λx. g(x x))) f

β→  (λx. f(x x)) (λx. f(x x)))

β→  f((λx. f(x x)) (λx. f(x x))))

β→  f(f((λx. f(x x)) (λx. f(x x)))))

で、
Y' ≡(λx. f(x x)) (λx. f(x x))
とすると、
Yf ≡ fY' ≡ ffY' ≡ fffY'
みたいな感じに増えていきます。

引数として与える関数fは、
f = λhy. if condition? then <終了時の処理など> else <再帰呼び出しなど>
のようにして書きます。

・この時、f = h(つまり、再帰呼び出し的な自分自身)だと考える。
・上のラムダ抽象の変数yは、ラムダ抽象が表す関数の引数だと考える。

再帰呼出風に書くとちゃんとループになるというわけです。

Yコンビネータは、Yf ≡ fY' ≡ ffY' ≡ fffY'みたいに増えてい来ます。
しかし、fが表すラムダ抽象は、引数をあたえられた時のβ簡約において、
hを展開させないようにすることで、fffY'のY'を切り捨てます。
結果、ループが止まります。

2.他の不動点コンビネータ

ちなみに、
A ≡(λxy. x y x) (λyx. y (x y x))

このコンビネータは、

β→  (λxy. x y x) (λyx. y (x y x)) f
β→  (λy. (λyx. y (x y x)) y (λyx. y (x y x))) f

β→  (λyx. y (x y x)) f (λyx. y (x y x))

β→  (λx. f (x f x)) (λyx. y (x y x))
β→  f ((λyx. y (x y x)) f (λyx. y (x y x)))
β→  f ((λx. f (x f x)) (λyx. y (x y x)))

β→  f (f ((λyx. y (x y x)) f (λyx. y (x y x))))

でやっぱり、

A' ≡(λyx. y (x y x)) f (λyx. y (x y x))
とすると、
A f ≡ fA' ≡ ffA' ≡ fffA'
みたいな感じに増えていきます。

Θ ≡ (λxy. y(x x y)) (λxy. y(x x y))
これは、「チューリングの不動点コンビネータ」と呼ぶようです。

β→  (λxy. y(x x y)) (λxy. y(x x y)) f

β→  (λy. y((λxy. y(x x y)) (λxy. y(x x y)) y)) f
β→  f ((λxy. y(x x y)) (λxy. y(x x y)) f)
β→  f ((λy. y((λxy. y(x x y) (λxy. y(x x y) y)) f)

β→  f ( f((λxy. y(x x y) (λxy. y(x x y) f)

でやっぱり、

A' ≡((λxy. y(x x y)) (λxy. y(x x y)) f)
とすると、
A f ≡ fA' ≡ ffA' ≡ fffA'
みたいな感じに増えていきます。

違いというか、簡約された結果だけ見ると、全部同じですね。
与えられたラムダ式fを内包して増加増幅していきます。