このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

Haskell の構文に惑わされているね

2月21日に、rst76さんからトラックバックをいただきました。

だいぶ遅くなってしまいましたが、口語体、つうかオシャベリ体でお応えします。

こりゃカリー化つうより、コンビネータの利用じゃね

rst76さん曰く:


Prelude> let g a b x = a * x + b
Prelude> g 3 5 7
26
Prelude> let g1 a b = (+ b) . (* a)
Prelude> g1 3 5 7
26

んーんと、これはカリー化(ラムダ抽象)と関係ないなー。確かに関数の変数(引数)が減っているように見えるんだけど、それは単にgとg1で違う書き方をした、ってだけ。g1がgのカリー化(ラムダ抽象)ということではない。

これはむしろコンビネータに関係するかな。コンビネータを使うとラムダ変数(束縛変数)を減らせて、究極的にはラムダ変数を完全になくせる*1のだけど、今のケースだと関数合成をするコンビネータ (.) を導入して内側のラムダ変数を消したことになる。

まず、事情が分かりやすくなるから、gとg1をHaskellラムダ式で書いておくと、


g = \a b x -> a*x + b
g1 = \a b -> (+ b) . (* a)

gでも(+ b)と(* a)を使っていいよね。


g = \a b x -> (+ b) ((* a) x)

\a b x -> は、\a -> \b -> \x ->、あるいは \a b -> \x -> の略記だから


g = \a b -> \x -> (+ b) ((* a) x)

g1のほうでは (.) を使っているけど、これは次のように定義されていると思っていい。


(.) = \g f -> \x -> g (f x)

\x -> g (f x) の f, g を (+ b), (* a) で置き換えたものが \x -> (+ b) ((* a) x) だから、

  • \x -> (+ b) ((* a) x) ≡ (.) (+ b) (* a)

記号≡は、左右が式として同値なこと(この同値性は超越的なものではなくて、書き換え規則のレベルで判定可能)。≡の左辺のラムダ変数xが右辺では消えている。その理由は \g f -> \x -> g (f x) というラムダ式を(.)という単一の記号で置き換えて、束縛変数を見えなくしている(閉じ込めている)から。

そういう事情で、gを次のような書き方にしても何も変わらない。


g = \a b -> (.) (+ b) (* a)

g1は、 別なスタイルの書き方をしたgに過ぎない。g1のほうが、point-freeスタイル*2に近くなっている。

今度は普通のラムダ式で書いてみよう。念のため、標準的ラムダ構文と対応するHaskellの構文をまとめておくと:

ラムダ構文 Haskell構文
λ \
. ->
(空白)

C = λg.λf.λx.(g・(f・x)) と定義する*3なら、λx.(g・(f・x)) を C・g・f と書けて、Cを使ってラムダ変数xを消せるでしょ。このCのように、自由変数を含まないラムダ式コンビネータで、CはHaskellの(.)と同じ。

Haskellのなかでカリー化を考えるなら

Haskellの関数は既にカリー化されてしまっているので、正面切ってカリー化の実験はできませんね。Haskellの世界をいくら探しても、上に二本以上ワイヤーが出た箱(オダンゴ)が全然ないんだもん、どうにもならんわ。もし、Haskellの世界(スノーグローブ)内でカリー化のミニチュア版を構成したいなら、タプルを引数とする g :: (a, b) -> c から g^ = (curry g) :: a -> (b -> c) を作り出すようなオペレータ curry :: ((a, b) -> c) -> (a -> (b -> c)) を定義することになるでしょうね。

rst76さん曰く:

別の言い方をすると、g :: Int -> Int -> Int -> Int を Int -> Int -> (Int -> Int) と解釈するか、Int -> (Int -> Int -> Int) と解釈するかの違いでしかないのでは、と思います。

いや、Int -> Int -> Int -> Int と Int -> Int -> (Int -> Int) と Int -> (Int -> Int -> Int) が同じってのは単なる括弧省略の約束であって、何ごとも主張してない。カリー化(ラムダ抽象)は、g :: (Int, Int, Int) -> Int から、(Int, Int) -> (Int -> Int) とか、Int -> (Int -> (Int -> Int)) のような関数を作り出すことです*4JavaScriptの例が多少は参考になるかな。

*1:純粋なコンビネータ項は、定数アトムと自由変数だけから作られる。

*2:point-freeって言葉はロクデモナイ用語だと思うけどね。

*3:[追記]Cはcomposeのつもりだったんですが、なぜかCじゃなくてBと書く方が多いようです。[/追記]

*4:ここいらはスノーグローブ現象の本質に関わる話。圏論的カリー化オペレータΛはホムセット(単に普通の集合)のあいだの同型を与える集合論的関数だけど、圏がベキを持つなら内部ホムが圏のなかに定義できて、ホムセット(外部ホム)の集合論的同型Λが内部ホム対象間の同型射に対応する。あああー、ややこしい。